C#是否存储大于512长(4096字节)的数组？

Question

我使用.NET Framework中实现的集合类型做了一些基准测试.

从参考源我知道List<T>使用数组来存储内容.为避免每次插入时调整数组大小,每次可用空间用完时,数组长度都会加倍.

根据我的理解,除了需要重新分配内部数组的情况外,图表应该是严格不变的.这种行为是否有任何原因,可能与CLR或Windows内存管理/内存碎片有关？

基准测试在Windows 10/i7-3630QM机器上以64位应用程序执行(源代码如下所示).由于单个添加操作无法测量,因此我创建了1000个列表,并为每个列表大小添加了一个项目.

for (int i = 1; i <= MaxCollectionSize; i++)
{
    // Reset time measurement
    TestContainer.ResetSnapshot();

    // Enable time measurement
    TestContainer.BeginSnapshot();
    // Execute one add operation on 1000 lists each
    ProfileAction.Invoke(TestContainer);
    TestContainer.EndSnapShot();

    double elapsedMilliseconds = (TestContainer.GetElapsedMilliSeconds() / (double)Stopwatch.Frequency) * 1000;
    // ...
}

编辑:我仔细检查了我的结果,是的,它们是可重复的.我将测试的集合数量从1000增加到10000,结果现在更加平滑(见下图).现在可以清楚地看到调整内部阵列大小的尖峰.然而在图中的步骤仍然存在-这是与预期的O(1)复杂性的阵列插入应该是,如果你忽略调整大小存在分歧.

我还尝试在每次Add操作之前触发GC集合,图表保持完全相同.

关于创建委托对象的问题:我的所有委托(例如ProfileAction)都是在一个完整的测试周期中保持分配的实例属性,在这种情况下是10000个列表,每个列表有1000个添加操作.

Answer 1

C#是否存储大于512长(4096字节)的数组？

不可以.当总大小为(IIRC)84kB或更大时:使用大对象堆(不压缩或世代).

然而:

创建1000个列表,并为每个列表大小添加一个项目.

每次测试时间约为5毫秒.Windows调度程序增量大于此值(实际值已在40毫秒到100毫秒之间使用,具体取决于版本和版本).你能看到调度程序执行线程切换吗？

建议你尝试每个尺寸运行至少250毫秒,以平衡这些效果.

编辑:另外,正如Lasse对问题的评论所说:这可能是GC.为了消除时间,在尺寸循环开始时,但在开始时钟之前,强制GC.还要监视GC性能计数器.

Answer 2

好吧，我们先看一下图中简单的部分。峰值是由重新分配、复制和垃圾收集引起的——这并不奇怪。列表中的少数首次添加的异常低时间很容易通过缓存局部性来解释 - 虽然堆仍然适合整个内存，但内存访问可以是随机的，同时仍然具有非常低的延迟。一旦堆变得足够大，并且数组长度值（以及列表计数值）距离插入的值足够远，缓存局部性就会产生明显的影响 - 在我的机器上使用 32 位 x86 代码进行测试时，缓存局部性的优化将整个测试的性能提高了四倍。

然而，虽然这些效应很好地解释了尖峰本身，以及每个尖峰之后的操作比尖峰之前需要更多时间的事实，但它们并没有真正解释随后的趋势 - 没有明显的理由说明为什么插入第 600 个元素应该花费更长的时间比插入第 550 个（假设最后一次调整大小是在 512 左右）。分析很好地表明，恒定成本相当高，但没有显示出随着时间的推移而明显增加的情况。

我的测试代码被简化为最基本的内容：

var collections = new List<int>[100000];

for (var i = 0; i < collections.Length; i++)
{
  collections[i] = new List<int>();       
}

for (var i = 0; i < 1024; i++)
{
  for (var j = 0; j < collections.Length; j++)
  {
    collections[j].Add(i);
  }
}

尽管唯一剩下的抽象是其Add本身，但趋势在测试数据中仍然可见，尽管我必须指出，我的曲线远没有你的那么平滑，而且偏差很大。典型的周期可能需要大约 20 毫秒，而尖峰则高达 5 秒。

好吧，是时候看一下拆解了。我的测试代码非常简单（只是内部循环体）：

002D0532  mov         eax,dword ptr [ebp-18h]  
002D0535  mov         ecx,dword ptr [eax+esi*4+8]  
002D0539  mov         edx,ebx  
002D053B  cmp         dword ptr [ecx],ecx  
002D053D  call        7311D5F0  

collections引用存储在堆栈中。正如预期的那样，i和j都在寄存器中，事实上，j在 中esi，这非常方便。因此，首先我们获取对 的引用collections，添加j * 4 + 8以获取实际的列表引用，并将其存储在ecx（this在我们要调用的方法中）。i存储在 中ebx，但必须移动到edx调用Add- 不过，在两个通用寄存器之间传输值没什么大不了的:) 然后是简单的乐观空检查，最后是调用本身。

首先要注意的是，不涉及分支，因此不会出现分支错误预测。其次，我们有两次内存访问 - 第一个是在堆栈上，这几乎可以保证始终位于缓存中。第二个更糟糕 - 这就是我们遇到缓存局部性问题的地方。但是，由此产生的滞后完全取决于数组的长度（和数量），因此应该（并且确实）与数组大小调整相关。

是时候看看Add方法本身了:)记住，ecx包含列表实例，同时edx包含我们要添加的项目。

首先是通常的方法序言，没什么特别的。接下来，我们检查数组大小：

8bf1    mov esi, ecx
8bfa    mov edi, edx
8b460c  mov eax, DWORD PTR [esi+0xc]    ; Get the list size
8b5604  mov edx, DWORD PTR [esi+0x4]    ; Get the array reference
3bf204  cmp eax, DWORD PTR [edx+0x4]    ; size == array.Length?
741c    je HandleResize ; Not important for us

我们这里还有三个内存访问。前两个本质上是相同的，因为正在加载的值放置得足够近。该数组只会在第一次调整数组大小之前进行共置，这进一步提高了前几次插入的缓存性能。请注意，CPU 在这里可以并行执行的操作并不多，但是这三个内存访问仍然应该只支付一次延迟成本。分支几乎总是会被正确预测——只有当我们达到数组大小时才会采取分支，之后我们对每个列表执行一次相同的分支。

剩下两部分：添加项目本身，并更新列表的内部版本（以使列表上任何正在进行的枚举失败）：

_items[_size++] = item;
_version++;

汇编中有点啰嗦:)

8b5604  mov edx, DWORD PTR [esi+0x4]    ; get the array reference again
8b4e0c  mov ecx, DWORD PTR [esi+0xc]    ; ... and the list size
8d4101  lea eax, [ecx+0x1]  ; Funny, but the best way to get size + 1 :)
89460c  mov DWORD PTR [esi+0xc], eax    ; ... and store the new size back in the list object
3b4a04  cmp ecx, DWORD PTR [edx+0x4]    ; Array length check
7318    jae ThrowOutOfRangeException    ; If array is shorter than size, throw
897c8a08    mov DWORD PTR [edx+ecx*4+0x8], edi  ; Store item in the array
ff4610  inc DWORD PTR [esi+0x10]    ; Increase the version
; ... and the epilogue, not important

就是这样。我们有永远不会被采用的分支（假设是单线程；我们之前已经检查了数组大小）。我们有相当多的访问：四个与列表本身相关（包括两次更新），另外两个与数组相关（包括一次更新）。现在，虽然列表上没有缓存未命中的原因（它几乎总是已经加载），但由于更新而存在失效。相反，在我们的场景中，数组访问总是会导致缓存未命中，唯一的例外是在第一次调整数组大小之前。事实上，您可以看到，首先没有缓存未命中（数组和对象并置，小），然后有一次未命中（仍然并置，但项目超出了缓存行），然后是两次（长度和项目访问都超出了缓存行）。

这当然很有趣（并且可以从手动优化中受益一点： P），但它再次只为我们提供了分析数据的“阶梯”。重要的是，不涉及分配，因此没有 GC。

有了所有这些，我得出的结论是，当不需要调整数组大小时，List.Add 确实是 O(1)。对于非常小的数组（以及与其引用位于同一位置的数组），有一些额外的优化可以使速度更快，但这在这里并不重要。

因此，您在分析数据中看到的趋势必须是环境因素，或者与分析本身直接相关，或者只是平均方法选择不当。例如，如果我在 100 000 个列表上运行此命令：

1. 添加前 550 项
2. 添加另外 100 个项目
3. 还有另外 100 件商品

2 和 3 所花费的时间之间存在差异，但没有趋势 - 2 更快的可能性与 3 更快的可能性相同（在 ~400ms 的时间跨度上大约有 ~2ms 的差异，因此大约 0.5 ％ 偏差）。然而，如果我用 2100 个项目进行“热身”，则后续步骤所需的时间几乎是以前的一半。更改列表的数量不会对每个集合产生明显的影响（当然，只要所有内容都适合您的物理内存:)）。

好吧，即使只是Stopwatch在发布模式下在调试器之外进行简单的运行，并且对结果数据进行简单的采样，这也是非常明显的。因此我们可以排除分析影响和统计错误。

但环境原因可能是什么？

• 除了数组大小调整之外，GC 根本不参与。没有分配，并且探查器非常清楚这样一个事实：在调整大小之间也没有发生 GC（尽管这对于并发 GC 来说价值有限:)）。调整 GC 设置会使一切变慢，但同样，只会影响调整大小峰值及其附近的环境。最重要的是，列表的数量（以及堆大小）对趋势没有任何影响，如果 GC 是原因，那将是相当令人惊讶的。
• 堆是零散的，但是非常有序。这使得重定位在内存压力下的开销较小，但同样，仅影响数组大小调整。无论如何，这并不奇怪，而且事实上有据可查。

所以，看看这一切……我不知道为什么会出现这种趋势。然而，请注意，这种趋势也绝对不是线性的——随着列表大小的增加，增长速度会迅速下降。从大约 15k 个项目开始，趋势完全消失，所以Add确实是 O(1) 不包括数组调整大小 - 它只是在某些大小下有一些奇怪的行为:)

...除非您预先分配列表。在这种情况下，结果与我仅基于缓存局部性的预测 100% 一致。这似乎表明调整大小和 GC 模式对常用缓存算法的效率有巨大影响（至少在我的 CPU 上 - 我认为这会有很大差异）。还记得我们讨论过整个操作期间发生的缓存未命中吗Add？这里有一个技巧 - 如果我们可以在两个循环之间保持足够的缓存线处于活动状态，则可以经常避免缓存未命中；如果我们假设 64 字节高速缓存行和最佳高速缓存失效算法，则列表成员访问和数组长度访问不会发生任何遗漏，每 16 次添加中每个数组只会发生一次遗漏。我们根本不需要数组的其余部分！您还需要一些其他缓存行（例如，列表实例），但数组是迄今为止最重要的。

现在，让我们算一下。十万个集合，在最坏的情况下每个集合有 2*64B 的缓存，加起来为 12 MiB，而我身上有 10 MiB 的缓存 - 我几乎可以可以在缓存中容纳所有相关的数组数据！当然，现在我不是唯一使用该缓存的应用程序（和线程），因此我们可以预期翻转点会略低于理想值 - 让我们看看更改集合数量如何改变我们的结果。

列出预先分配的 8000 个项目 (32 kB)，添加 2000 个项目、100、100

Lists   A       B   C
400     18      1   1
800     52      2   2
1600    120     6   6
3200    250     12  12
6400    506     25  25
12800   1046    52  53
25600   5821    270 270

哈！相当漂亮可见。时间随着列表计数线性增加，直到最后一个项目 - 那是我们的缓存耗尽的时候。这大约是 3-8 MiB 的缓存使用总量 - 很可能是我忽略了一些也需要缓存的重要事情的结果，或者对操作系统或 CPU 的一部分进行了一些优化以防止我占用整个缓存或其他东西:)

非常小的列表计数中的轻微非线性很可能与较低级别缓存的缓慢溢出有关 - 400 适合我的 L2 缓存，800 已经溢出了一点，1600 还多了一点当我们达到 3200 时，L2 缓存几乎可以完全忽略。

对于我们的最终检查，同样的场景，但添加了 4000 个项目而不是 2000 个：

Lists   A       B   C
400     42      1   1
800     110     3   2
1600    253     6   6
3200    502     12  12
6400    1011    25  25
12800   2091    52  53
25600   10395   250 250

正如您所看到的，项目计数对插入时间（每个项目）没有任何影响，整个趋势就消失了。

所以你有它。这种趋势是由 GC 间接引起的（通过代码中的次优分配和 GC 中破坏缓存局部性的压缩模式）和直接缓存溢出。由于项目数量较少，任何给定的所需内存块现在更有可能位于缓存中。当数组需要调整大小时，大部分缓存内存几乎毫无价值，并且会慢慢失效并被更有用的内存取代 - 但整个内存使用模式与 CPU 优化的目标相去甚远。相反，通过保持数组预先分配，我们确保一旦我们在内存中拥有列表，我们也可以看到数组长度（奖励1），并且已经指向数组末尾的缓存行对于一些循环将是有用的（奖金2）。由于没有调整数组大小，因此这些对象根本不需要在内存中移动，并且有很好的共置性。