Why .NET group by is (much) slower when the number of buckets grows

Question

Given this simple piece of code and 10mln array of random numbers:

static int Main(string[] args)
    {
        int size = 10000000;
        int num =  10; //increase num to reduce number of buckets
        int numOfBuckets = size/num;
        int[] ar = new int[size];
        Random r = new Random(); //initialize with randum numbers
        for (int i = 0; i < size; i++)
            ar[i] = r.Next(size);

        var s = new Stopwatch();
        s.Start();
        var group = ar.GroupBy(i => i / num);
        var l = group.Count();
        s.Stop();

        Console.WriteLine(s.ElapsedMilliseconds);
        Console.ReadLine();
        return 0;
    }

I did some performance on grouping, so when the number of buckets is 10k the estimated execution time is 0.7s, for 100k buckets it is 2s, for 1m buckets it is 7.5s.

I wonder why is that. I imagine that if the GroupBy is implemented using HashTable there might be problem with collisions. For example initially the hashtable is prepard to work for let's say 1000 groups and then when the number of groups is growing it needs to increase the size and do the rehashing. If these was the case I could then write my own grouping where I would initialize the HashTable with expected number of buckets, I did that but it was only slightly faster.

So my question is, why number of buckets influences groupBy performance that much?

EDIT: running under release mode change the results to 0.55s, 1.6s, 6.5s respectively.

I also changed the group.ToArray to piece of code below just to force execution of grouping :

foreach (var g in group)
    array[g.Key] = 1;  

where array is initialized before timer with appropriate size, the results stayed almost the same.

EDIT2: You can see the working code from mellamokb in here pastebin.com/tJUYUhGL

Answer 1

I'm pretty certain this is showing the effects of memory locality (various levels of caching) and also object allocation.

To verify this, I took three steps:

• Improve the benchmarking to avoid unnecessary parts and to garbage collect between tests
• Remove the LINQ part by populating a Dictionary (which is effecively what GroupBy does behind the scenes)
• Remove even Dictionary<,> and show the same trend for plain arrays.

In order to show this for arrays, I needed to increase the input size, but it does show the same kind of growth.

Here's a short but complete program which can be used to test both the dictionary and the array side - just flip which line is commented out in the middle:

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Test
{    
    const int Size = 100000000;
    const int Iterations = 3;
    
    static void Main()
    {
        int[] input = new int[Size];
        // Use the same seed for repeatability
        var rng = new Random(0);
        for (int i = 0; i < Size; i++)
        {
            input[i] = rng.Next(Size);
        }
        
        // Switch to PopulateArray to change which method is tested
        Func<int[], int, TimeSpan> test = PopulateDictionary;
        
        for (int buckets = 10; buckets <= Size; buckets *= 10)
        {
            TimeSpan total = TimeSpan.Zero;
            for (int i = 0; i < Iterations; i++)
            {
                // Switch which line is commented to change the test
                // total += PopulateDictionary(input, buckets);
                total += PopulateArray(input, buckets);
                GC.Collect();
                GC.WaitForPendingFinalizers();
            }
            Console.WriteLine("{0,9}: {1,7}ms", buckets, (long) total.TotalMilliseconds);
        }
    }
    
    static TimeSpan PopulateDictionary(int[] input, int buckets)
    {
        int divisor = input.Length / buckets;
        var dictionary = new Dictionary<int, int>(buckets);
        var stopwatch = Stopwatch.StartNew();
        foreach (var item in input)
        {
            int key = item / divisor;
            int count;
            dictionary.TryGetValue(key, out count);
            count++;
            dictionary[key] = count;
        }
        stopwatch.Stop();
        return stopwatch.Elapsed;
    }

    static TimeSpan PopulateArray(int[] input, int buckets)
    {
        int[] output = new int[buckets];
        int divisor = input.Length / buckets;
        var stopwatch = Stopwatch.StartNew();
        foreach (var item in input)
        {
            int key = item / divisor;
            output[key]++;
        }
        stopwatch.Stop();
        return stopwatch.Elapsed;
    }
}

Results on my machine:

PopulateDictionary:

       10:   10500ms
      100:   10556ms
     1000:   10557ms
    10000:   11303ms
   100000:   15262ms
  1000000:   54037ms
 10000000:   64236ms // Why is this slower? See later.
100000000:   56753ms 

PopulateArray:

       10:    1298ms
      100:    1287ms
     1000:    1290ms
    10000:    1286ms
   100000:    1357ms
  1000000:    2717ms
 10000000:    5940ms
100000000:    7870ms

An earlier version of PopulateDictionary used an Int32Holder class, and created one for each bucket (when the lookup in the dictionary failed). This was faster when there was a small number of buckets (presumably because we were only going through the dictionary lookup path once per iteration instead of twice) but got significantly slower, and ended up running out of memory. This would contribute to fragmented memory access as well, of course. Note that PopulateDictionary specifies the capacity to start with, to avoid effects of data copying within the test.

The aim of using the PopulateArray method is to remove as much framework code as possible, leaving less to the imagination. I haven't yet tried using an array of a custom struct (with various different struct sizes) but that may be something you'd like to try too.

EDIT: I can reproduce the oddity of the slower result for 10000000 than 100000000 at will, regardless of test ordering. I don't understand why yet. It may well be specific to the exact processor and cache I'm using...

--EDIT--

The reason why 10000000 is slower than the 100000000 results has to do with the way hashing works. A few more tests explain this.

First off, let's look at the operations. There's Dictionary.FindEntry, which is used in the [] indexing and in Dictionary.TryGetValue, and there's Dictionary.Insert, which is used in the [] indexing and in Dictionary.Add. If we would just do a FindEntry, the timings would go up as we expect it:

static TimeSpan PopulateDictionary1(int[] input, int buckets)
{
    int divisor = input.Length / buckets;
    var dictionary = new Dictionary<int, int>(buckets);
    var stopwatch = Stopwatch.StartNew();
    foreach (var item in input)
    {
        int key = item / divisor;
        int count;
        dictionary.TryGetValue(key, out count);
    }
    stopwatch.Stop();
    return stopwatch.Elapsed;
}

This is implementation doesn't have to deal with hash collisions (because there are none), which makes the behavior as we expect it. Once we start dealing with collisions, the timings start to drop. If we have as much buckets as elements, there are obviously less collisions... To be exact, we can figure out exactly how many collisions there are by doing:

static TimeSpan PopulateDictionary(int[] input, int buckets)
{
    int divisor = input.Length / buckets;
    int c1, c2;
    c1 = c2 = 0;
    var dictionary = new Dictionary<int, int>(buckets);
    var stopwatch = Stopwatch.StartNew();
    foreach (var item in input)
    {
        int key = item / divisor;
        int count;
        if (!dictionary.TryGetValue(key, out count))
        {
            dictionary.Add(key, 1);
            ++c1;
        }
        else
        {
            count++;
            dictionary[key] = count;
            ++c2;
        }
    }
    stopwatch.Stop();
    Console.WriteLine("{0}:{1}", c1, c2);
    return stopwatch.Elapsed;
}

The result is something like this:

10:99999990
       10:    4683ms
100:99999900
      100:    4946ms
1000:99999000
     1000:    4732ms
10000:99990000
    10000:    4964ms
100000:99900000
   100000:    7033ms
1000000:99000000
  1000000:   22038ms
9999538:90000462       <<-
 10000000:   26104ms
63196841:36803159      <<-
100000000:   25045ms

Note the value of '36803159'. This answers the question why the last result is faster than the first result: it simply has to do less operations -- and since caching fails anyways, that factor doesn't make a difference anymore.

Answer 2

10k the estimated execution time is 0.7s, for 100k buckets it is 2s, for 1m buckets it is 7.5s.

This is an important pattern to recognize when you profile code. It is one of the standard size vs execution time relationships in software algorithms. Just from seeing the behavior, you can tell a lot about the way the algorithm was implemented. And the other way around of course, from the algorithm you can predict the expected execution time. A relationship that's annotated in the Big Oh notation.

Speediest code you can get is amortized O(1), execution time barely increases when you double the size of the problem. The Dictionary<> class behaves that way, as John demonstrated. The increases in time as the problem set gets large is the "amortized" part. A side-effect of Dictionary having to perform linear O(n) searches in buckets that keep getting bigger.

A very common pattern is O(n). That tells you that there is a single for() loop in the algorithm that iterates over the collection. O(n^2) tells you there are two nested for() loops. O(n^3) has three, etcetera.

What you got is the one in between, O(log n). It is the standard complexity of a divide-and-conquer algorithm. In other words, each pass splits the problem in two, continuing with the smaller set. Very common, you see it back in sorting algorithms. Binary search is the one you find back in your text book. Note how log₂(10) = 3.3, very close to the increment you see in your test. Perf starts to tank a bit for very large sets due to the poor locality of reference, a cpu cache problem that's always associated with O(log n) algoritms.

The one thing that John's answer demonstrates is that his guess cannot be correct, GroupBy() certainly does not use a Dictionary<>. And it is not possible by design, Dictionary<> cannot provide an ordered collection. Where GroupBy() must be ordered, it says so in the MSDN Library:

The IGrouping objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping. Elements in a grouping are yielded in the order they appear in source.

Not having to maintain order is what makes Dictionary<> fast. Keeping order always cost O(log n), a binary tree in your text book.

Long story short, if you don't actually care about order, and you surely would not for random numbers, then you don't want to use GroupBy(). You want to use a Dictionary<>.