GroupBy Performance

Looking at the performance of GroupBy in various scenarios

This project is all .NET Core 3.1, previous editions may differ due to newer .NET Core LINQ optimizations.

For each use case I will test two scenarios, each using a toy Bill class standing in for a typical thing one might group on. Scenario 1 will have ~10,000 keys each with ~10 bills, scenario 2 will have ~10 keys each with ~10,000 bills.

Aggregating by group

One thing you might use group by for is to compute some aggregate value by grouping. For instance with our bill, we might want to know the sum of the totals for each bill type. Group By provides a very concise way to do this:

return bills.GroupBy(b => b.BillType).Select(grouping => grouping.Sum(b => b.Total)).ToList();

This will return a List of the sums of all the totals or each group type.

Avoiding group by, another way we could compute the sums is like so:

 var sums = new Dictionary<int, double>();
 foreach (var bill in bills)
 {
     double total;
     if (!sums.TryGetValue(bill.BillType, out total))
     {
         sums.Add(bill.BillType, bill.Total);
     }
     else
     {                    
         sums[bill.BillType] = total + bill.Total;
     }
 }
 return sums.Values.ToList();

This is a lot more code, and we might expect this to perform worse, since we are creating a Dictionary to hold a bunch of intermediate data before we aggregate. But it turns out, so is GroupBy, let's look at a BenchmarkDotNet comparison:

Doing the aggregation as you go, if possible, saves a ton of time and GC pressure. This is because GroupBy can't perform this operation in a totally lazy manner, it is having to creating a lookup table behind the scenes, one that is filled with a collection of Bills, rather than just the current sum.

Building up a cache for later use

Another scenario we often use GroupBy for is to create caches/lookup tables for use later in our application. For instance a website may pull down data from a database on startup, and create an in memory cache to avoid hammering the database for frequently queries but rarely changed data. With this use case, there are two concerns. How long it takes to create the cache, and then how well the cache performs when using it. We will take a look at both. In our case we want some kind of lookup table that lets us get a collection of Bills when we provide the BillType. We could do that by using GroupBy, ToLookup, or by creating a Dictionary by hand:

 
public Dictionary<int, IEnumerable<Bill>> GroupBy_Cache()
{
    return bills.GroupBy(b => b.BillType).ToDictionary(g => g.Key, g => (IEnumerable<Bill>)g);
}
 
public ILookup<int,Bill> Lookup_Cache()
{
    return bills.ToLookup(b => b.BillType);
}

public Dictionary<int,List<Bill>> Dictionary_Cache()
{
    var dict = new Dictionary<int, List<Bill>>();
    foreach (var bill in bills)
    {
        List<Bill> billList;
        if (!dict.TryGetValue(bill.BillType, out billList))
        {
            billList = new List<Bill>();
            dict.Add(bill.BillType, billList);
        }
        billList.Add(bill);

    }
    return dict;
}

Here is how long these approaches take to build:

It is worth noting that the Dictionary case could be optimized further in cases when you know, or approximately know, how many groupings will be in the data ahead of time, by setting the initial Dictionary capacity.

Using the cache

The above startup times may all be roughly equivalent for many use cases, especially since they will usually be one time, or rare operations. But what about using the cache, which will be done repeatedly, and where performance is more likely to be important? Here is a test of each cache that just grabs a single BillType from each cache, and iterates over all the bills in that group to sum them up:

 [Benchmark]
 public double GroupByCache_Use()
 {          
     var bills = groupByCache[5];
     double total = 0.0;
     foreach (var bill in bills)
     {
         total += bill.Total;
     }
     return total;
 }

 [Benchmark]
 public double LookupCache_Use()
 {                        
     var bills = lookupCache[5];
     double total = 0.0;
     foreach (var bill in bills)
     {
         total += bill.Total;
     }                    
     return total;
 }

 [Benchmark]
 public double DictionaryCache_Use()
 {
     var bills = dictionaryCache[5];
     double total = 0.0;
     for(int j = 0; j < bills.Count;j++)
     {
         total += bills[j].Total;
     }
     return total;                    
 }

With the following results:

The differences here are due almost entirely to being able to leverage that the Dictionary cache has a List inside of it, allowing us to avoid the overhead and allocations used when using an IEnumerable. If you were to use .Sum() in all cases for instance, instead of a foreach or for loop to compute the sums, all 3 caches would perform very nearly the same. Also it should be noted the time to retrieve a group from the cache is very nearly the same in all 3 cases. Only the time and allocations to iterate over the groups differ.

Using GroupBy to produce Lists for each group

If you want to create a cache that is as efficient as possible when being used, you can still use GroupBy, like so:

public Dictionary<int, List<Bill>> GroupByList_Cache()
{
    return bills.GroupBy(b => b.BillType).ToDictionary(g => g.Key,g => g.ToList());
}

Unforunately while this cache will be fast to use, it takes much longer and way more allocations to create:

A real life example from work (and a large open source project)

At work we had some code running in a web framework on every single request that was a bit slow, GroupBy was being used to extract just the first element out of each group into a Dictionary. Here is an approximation of the original code and the optimized version:

 [Benchmark]
 public Dictionary<int, Bill> GroupbyFirst()
 {
     return bills.GroupBy(b => b.BillType).ToDictionary(g => g.Key, g => g.First());
 }
 [Benchmark]
 public Dictionary<int, Bill> DictionaryFirst()
 {
     var dict = new Dictionary<int, Bill>();
     foreach (var bill in bills)
     {
         if (!dict.ContainsKey(bill.BillType))
         {
             dict.Add(bill.BillType, bill);
         }
     }
     return dict;
 }

And the results:

Have your cake and eat it to?

The brevity that GroupBy affords is really nice. In many cases you can get that same brevity with better performance by writing your own generic extension methods, to turn Enumerables into grouped dictionaries:

    public static Dictionary<K, List<V>> GroupByDictionary<K, V>(this IEnumerable<V> items, Func<V, K> keySelector)
    {
        var dictionary = new Dictionary<K, List<V>>();
        foreach (var item in items)
        {
            List<V> grouping;
            var key = keySelector(item);
            if (!dictionary.TryGetValue(key, out grouping))
            {
                grouping = new List<V>(1);
                dictionary.Add(key, grouping);
            }
            grouping.Add(item);
        }
        return dictionary;
    }

    public static Dictionary<K, List<V>> GroupByDictionary<U,K, V>(this IEnumerable<U> items, Func<U, K> keySelector, Func<U,V> valueSelector)
    {
        var dictionary = new Dictionary<K, List<V>>();
        foreach (var item in items)
        {
            List<V> grouping;
            var key = keySelector(item);
            if (!dictionary.TryGetValue(key, out grouping))
            {
                grouping = new List<V>(1);
                dictionary.Add(key, grouping);
            }
            grouping.Add(valueSelector(item));
        }
        return dictionary;
    }
}