c# - 为什么 .NET group by 在 buckets 数量增长时(非常)慢

Question

给定这段简单的代码和 1000 万个随机数数组:

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;
    }

我在分组上做了一些性能，所以当桶数为 10k 时，估计执行时间为 0.7s，对于 100k 桶，它是 2s，对于 1m 桶，它是 7.5s。

我想知道为什么会这样。我想如果 GroupBy 是使用 HashTable 实现的，则可能会出现冲突问题。例如，最初哈希表准备为 1000 个组工作，然后当组数增加时，它需要增加大小并进行重新哈希。如果是这种情况，我可以编写自己的分组，在其中用预期的桶数初始化 HashTable，我这样做了，但速度稍快。

所以我的问题是，为什么桶的数量对 groupBy 的性能影响那么大？

编辑: 在release模式下运行，结果分别为0.55s、1.6s、6.5s。

我还将 group.ToArray 更改为下面的一段代码，以强制执行分组:

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

数组在计时器之前初始化为适当的大小，结果几乎保持不变。

编辑2: 您可以在此处 pastebin.com/tJUYUhGL 查看来自 mellamokb 的工作代码

Answer 1

我很确定这显示了内存局部性(各种级别的缓存)和对象分配的影响。

为了验证这一点，我采取了三个步骤:

• 改进基准测试以避免不必要的部分并在测试之间收集垃圾
• 通过填充 Dictionary 删除 LINQ 部分(这实际上是 GroupBy 在幕后所做的)
• 删除偶数 Dictionary<,>并显示普通阵列的相同趋势。

为了显示数组的这一点，我需要增加输入大小，但它确实显示了相同类型的增长。

这是一个简短但完整的程序，可用于测试字典和数组端 - 只需翻转中间注释掉的那一行:

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;
    }
}

我机器上的结果:

填充字典:

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

填充数组:

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

PopulateDictionary 的早期版本使用了 Int32Holder类，并为每个桶创建一个(当字典中的查找失败时)。当有少量桶时，这更快(大概是因为我们每次迭代只通过字典查找路径一次而不是两次)但速度明显变慢，并最终耗尽内存。当然，这也会导致碎片化的内存访问。注意 PopulateDictionary指定开始的容量，以避免测试中数据复制的影响。

使用 PopulateArray 的目的方法是尽可能去掉框架代码，少留想象空间。我还没有尝试使用自定义结构数组(具有各种不同的结构大小)，但这可能也是您想要尝试的。

编辑:无论测试顺序如何，我都可以随意重现 10000000 比 100000000 慢的结果的奇怪之处。我还不明白为什么。它很可能特定于我正在使用的确切处理器和缓存...

--编辑--

10000000 比 100000000 结果慢的原因与散列的工作方式有关。更多的测试可以解释这一点。

首先，让我们看一下操作。有 Dictionary.FindEntry ，用于 []索引并在 Dictionary.TryGetValue ，还有 Dictionary.Insert ，用于 []索引并在 Dictionary.Add .如果我们只是做一个 FindEntry ，时间会像我们预期的那样上升:

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;
}

这个实现不必处理散列冲突(因为没有)，这使得行为符合我们的预期。一旦我们开始处理碰撞，时间就会开始下降。如果我们有和元素一样多的桶，那么碰撞显然会少一些……准确地说，我们可以通过以下操作计算出究竟有多少碰撞:

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;
}

结果是这样的:

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

记下“36803159”的值。这回答了为什么最后一个结果比第一个结果更快的问题:它只需要执行更少的操作——而且由于缓存无论如何都会失败，这个因素不再产生影响。