为什么当存储桶数量增加时，.NET 分组依据(要慢得多)
本文关键字：NET 存储 增加 为什么 | 更新日期: 2023-09-27 17:56:17
给定这段简单的代码和 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.7 秒，对于 100k 桶为 2 秒，对于 1m 桶为 7.5 秒。
我想知道这是为什么。我想，如果使用HashTable实现GroupBy，则可能会出现冲突问题。例如，最初哈希表准备用于 1000 个组，然后当组数量增加时，它需要增加大小并进行重新哈希。如果是这种情况，我可以编写自己的分组，在那里我将使用预期的存储桶数初始化 HashTable，我这样做了，但它只是稍微快一点。
所以我的问题是，为什么桶的数量对组性能的影响如此之大？
编辑：在释放模式下运行，将结果分别更改为 0.55 秒、1.6 秒、6.5 秒。
我也换了小组。ToArray到下面的代码段只是为了强制执行分组：
foreach (var g in group)
array[g.Key] = 1;
其中数组在计时器之前以适当的大小初始化，结果几乎保持不变。
编辑2：你可以在这里看到mellamokb的工作代码 pastebin.com/tJUYUhGL<</p>
确定这显示了内存局部性（各种级别的缓存）和对象分配的影响。
为了验证这一点，我采取了三个步骤：
- 改进基准测试，以避免不必要的部件并在测试之间收集垃圾
- 通过填充
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"的值。这回答了为什么最后一个结果比第一个结果更快的问题：它只需要执行更少的操作 - 而且由于缓存无论如何都会失败，因此该因素不再起作用。
10k 的估计执行时间为 0.7 秒，100k 桶的估计执行时间为2 秒，1m 桶的估计执行时间为 7.5 秒。
这是分析代码时要识别的重要模式。 它是软件算法中的标准大小与执行时间关系之一。 仅通过查看行为，您就可以了解很多有关算法实现方式的信息。 当然，反过来，通过算法您可以预测预期的执行时间。 以大哦表示法注释的关系。
你能得到的最快的代码是摊销O（1），当你把问题的大小加倍时，执行时间几乎不会增加。 字典<>类的行为方式，正如约翰所演示的那样。 随着问题集变大，时间的增加是"摊销"部分。 字典必须在不断变大的存储桶中执行线性 O（n） 搜索的副作用。
一个非常常见的模式是 O（n）。 这告诉您算法中有一个循环访问集合的 for（） 循环。 O（n^2） 告诉你有两个嵌套的 for（） 循环。 O（n^3） 有三个，依此类推。
你得到的是介于两者之间的那个，O（log n）。 它是分而治之算法的标准复杂性。 换句话说，每次传递将问题一分为二，继续较小的集合。 很常见，您可以在排序算法中看到它。 二分搜索是你在教科书中找到的那个。 请注意 log₂（10） = 3.3，非常接近您在测试中看到的增量。 由于引用位置差，对于非常大的集合，Perf 开始有点下降，这是一个始终与 O（log n） 算法相关的 CPU 缓存问题。
约翰的回答表明的一件事是他的猜测不可能是正确的，GroupBy（） 当然不使用字典<>。 而且从设计上讲，字典<>无法提供有序集合是不可能的。 在必须对 GroupBy（） 进行排序的地方，它在 MSDN 库中是这样说的：
IGrouping 对象根据源中生成每个 IGrouping 的第一个密钥的元素的顺序生成。分组中的元素按它们在源中出现的顺序生成。
不必维持秩序是使字典<>快速的原因。 保持秩序总是要花费O（log n），这是教科书中的二叉树。
长话短说，如果你实际上并不关心顺序，而且你肯定不会关心随机数，那么你不想使用 GroupBy（）。 您想使用字典<>。
（至少）有两个影响因素：首先，哈希表查找仅在您具有不存在的完美哈希函数时才采用 O（1）。因此，您有哈希冲突。
不过，我想更重要的是缓存效果。现代 CPU 具有较大的缓存，因此对于较小的存储桶计数，哈希表本身可能适合缓存。由于经常访问哈希表，这可能会对性能产生很大影响。如果有更多的存储桶，则可能需要对 RAM 进行更多访问，与缓存命中相比，这很慢。
这里有几个因素在起作用。
哈希和分组
分组的工作方式是创建哈希表。然后，每个单独的组都支持"添加"操作，该操作将元素添加到添加列表中。说白了，就像Dictionary<Key, List<Value>>。
哈希表总是过度分配。如果将元素添加到哈希中，它会检查是否有足够的容量，如果没有，则重新创建具有更大容量的哈希表（确切地说：新容量 = count * 2，并计算组数）。但是，更大的容量意味着存储桶索引不再正确，这意味着您必须重新构建哈希表中的条目。Lookup<Key, Value>中的Resize()方法就是这样做的。
"小组"本身就像一个List<T>.这些也是过度分配的，但更容易重新分配。准确地说：数据被简单地复制（在Array.Resize中使用Array.Copy）并添加一个新元素。由于不涉及重新哈希或计算，因此这是一个非常快的操作。
分组的初始容量为 7。这意味着，对于 10 个元素，您需要重新分配 1 次，对于 100 个元素需要重新分配 4 次，对于 1000 个元素需要重新分配 8 次，依此类推。由于每次都必须重新哈希处理更多元素，因此每次存储桶数量增加时，代码都会变慢一些。
我认为这些过度分配是随着桶数量的增加而导致时间小幅增长的最大因素。测试此理论的最简单方法是根本不进行过度分配（测试 1），只需将计数器放在数组中即可。结果可以在下面的代码中显示FixArrayTest（或者如果你喜欢FixBucketTest更接近分组的工作方式）。如您所见，# buckets = 10...10000 的时间是相同的，根据该理论这是正确的。
缓存和随机
缓存和随机数生成器不是朋友。
我们的小测试还表明，当存储桶数量增长到某个阈值以上时，内存就会发挥作用。在我的计算机上，数组大小约为 4 MB（4 * 存储桶数）。由于数据是随机的，因此随机的RAM块将被加载和卸载到缓存中，这是一个缓慢的过程。这也是速度的大幅飞跃。要查看此操作，请将随机数更改为序列（称为"测试 2"），并且 - 由于现在可以缓存数据页 - 整体速度将保持不变。
请注意，哈希值会过度分配，因此您将在分组中有一百万个条目之前达到目标。
测试代码
static void Main(string[] args)
{
int size = 10000000;
int[] ar = new int[size];
//random number init with numbers [0,size-1]
var r = new Random();
for (var i = 0; i < size; i++)
{
ar[i] = r.Next(0, size);
//ar[i] = i; // Test 2 -> uncomment to see the effects of caching more clearly
}
Console.WriteLine("Fixed dictionary:");
for (var numBuckets = 10; numBuckets <= 1000000; numBuckets *= 10)
{
var num = (size / numBuckets);
var timing = 0L;
for (var i = 0; i < 5; i++)
{
timing += FixBucketTest(ar, num);
//timing += FixArrayTest(ar, num); // test 1
}
var avg = ((float)timing) / 5.0f;
Console.WriteLine("Avg Time: " + avg + " ms for " + numBuckets);
}
Console.WriteLine("Fixed array:");
for (var numBuckets = 10; numBuckets <= 1000000; numBuckets *= 10)
{
var num = (size / numBuckets);
var timing = 0L;
for (var i = 0; i < 5; i++)
{
timing += FixArrayTest(ar, num); // test 1
}
var avg = ((float)timing) / 5.0f;
Console.WriteLine("Avg Time: " + avg + " ms for " + numBuckets);
}
}
static long FixBucketTest(int[] ar, int num)
{
// This test shows that timings will not grow for the smaller numbers of buckets if you don't have to re-allocate
System.Diagnostics.Stopwatch s = new Stopwatch();
s.Start();
var grouping = new Dictionary<int, List<int>>(ar.Length / num + 1); // exactly the right size
foreach (var item in ar)
{
int idx = item / num;
List<int> ll;
if (!grouping.TryGetValue(idx, out ll))
{
grouping.Add(idx, ll = new List<int>());
}
//ll.Add(item); //-> this would complete a 'grouper'; however, we don't want the overallocator of List to kick in
}
s.Stop();
return s.ElapsedMilliseconds;
}
// Test with arrays
static long FixArrayTest(int[] ar, int num)
{
System.Diagnostics.Stopwatch s = new Stopwatch();
s.Start();
int[] buf = new int[(ar.Length / num + 1) * 10];
foreach (var item in ar)
{
int code = (item & 0x7FFFFFFF) % buf.Length;
buf[code]++;
}
s.Stop();
return s.ElapsedMilliseconds;
}
执行较大的计算时，计算机上可用的物理内存较少，计算存储桶的速度会越慢，内存越少，随着存储桶的消耗，内存会减少。
尝试如下操作：
int size = 2500000; //10000000 divided by 4
int[] ar = new int[size];
//random number init with numbers [0,size-1]
System.Diagnostics.Stopwatch s = new Stopwatch();
s.Start();
for (int i = 0; i<4; i++)
{
var group = ar.GroupBy(i => i / num);
//the number of expected buckets is size / num.
var l = group.ToArray();
}
s.Stop();
用较低的数字计算 4 倍。