C# 是否以不同方式存储大于 512 长（4096 字节）的数组？
Does C# store arrays larger than 512 longs (4096 bytes) differently?
我对 .NET Framework 中实现的集合类型进行了一些基准测试。
从参考资料中我知道 List<T> 使用数组来存储内容。为避免在每次插入时调整数组大小，array length gets doubled 每次可用 space 用完。
现在我的基准测试会将随机 long 值插入到 List 中（有关大小 - 时间 - 图表，请参见上图）。在列表大小如 128 或 256 中有明显的 "lag spikes" 必须重新分配内部数组。但是在 512（和 128，虽然？）的大小下，似乎有很大的延迟，并且插入一项所需的时间持续增加。
在我的理解中，除了内部数组需要重新分配的情况外，图形应该是严格不变的。这种行为是否有任何原因，可能与 CLR 或 Windows 内存管理/内存碎片有关？
基准测试作为 64 位应用程序在 Windows 10 / i7-3630QM 机器上执行（源代码如下所示）。因为单个添加操作无法测量，所以我创建了 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 个添加操作。
Does C# store arrays larger than 512 longs (4096 bytes) differently?
没有。它在总大小为 (IIRC) 84kB 或更大时执行：使用大对象堆（不压缩或分代）。
但是：
create 1000 lists and add one item each for every list size.
每次测试的时间约为 5 毫秒。 Windows scheduler delta 大于该值（实际值从 40ms 到 100ms，具体取决于版本和版本）。您能看到调度程序正在执行线程切换吗？
建议您尝试将每个尺寸设为 运行 至少 250 毫秒，以平衡此类效果。
编辑：另外，正如 Lasse 对问题注释的评论：这可能是 GC。要从您的计时中消除它，请在大小循环开始时，但在启动时钟之前，强制执行 GC。同时监控 GC 性能计数器。
好了，我们先看图片中简单的部分。尖峰是由重新分配、复制和垃圾引起的 collection - 这没什么大惊奇的。第一次添加到列表的异常低的时间很容易用缓存局部性来解释——虽然堆仍然适合整个内存，内存访问可以是 运行dom，同时仍然是非常低的延迟。一旦堆变得足够大，并且数组长度值（以及列表计数值）距离插入的值足够远，缓存局部性就会产生明显的影响——在我的机器上用 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 - 没什么大不了的 t运行 在两个通用寄存器之间传递一个值，虽然 :) 然后是简单的乐观空值检查，最后是调用本身。
首先要注意的是没有b运行ching，所以没有b运行ching mis-predictions。其次，我们有两个内存访问 - 第一个是在堆栈上，这几乎保证 运行teed 总是在缓存中。第二个更糟——这就是我们遇到缓存局部性问题的地方。但是，由此产生的滞后完全取决于数组的长度（和数量），因此应该（并且确实）与数组大小调整相关。
是时候看看 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 在这里可以并行执行的操作并不多，但是三个内存访问应该仍然只支付一次延迟成本。 b运行ch 几乎总是会被正确预测——只有在我们达到数组大小时才会进行预测，之后我们对每个列表执行一次相同的 b运行ch。
剩下两部分：添加项目本身，并更新列表的内部版本（使列表中任何正在进行的枚举失败）：
_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
就是这样。我们有永远不会被采用的 b运行ch（假设 single-threaded；我们之前已经检查了数组大小）。我们有很多访问：四个与列表本身相关（包括两个更新），还有两个数组（包括一个更新）。现在，虽然列表中没有缓存未命中的原因（它几乎总是已经加载），但由于更新而导致失效。相反，在我们的场景中，数组访问总是会导致缓存未命中，唯一的例外是在第一次调整数组大小之前。实际上，您可以看到首先没有缓存未命中（数组和 object 并置，小），然后是一次未命中（仍然并置，但项目超出了缓存行），然后是两次（长度和项目访问都超出了缓存行）缓存行）。
这当然很有趣（并且可以从手动优化中受益 tiny :P），但它再次只给我们提供了分析数据的 "stairs" .重要的是，没有涉及分配，所以没有 GC。
有了所有这些，我得出结论，当不需要调整数组大小时，List.Add 确实是 O(1)。对于非常小的数组（以及与其引用位于同一位置的数组），有一些额外的优化可以使事情变得更快，但这不是impo在这里。
因此，您在分析数据中看到的趋势必须是环境因素，或者与分析本身直接相关，或者只是选择了错误的平均方法。例如，如果我 运行 在 100 000 个列表中这样做：
- 添加前 550 项
- 再添加 100 项
- 还有另外 100 项
时间 2 和 3 之间存在差异，但没有趋势 - 2 更快和 3 更快的可能性一样大（在 ~ 的时间跨度上相差约 2 毫秒） 400ms，所以大约有 0.5% 的偏差）。然而，如果我改为使用 2100 个项目执行 "warmup"，则后续步骤的时间几乎是之前的一半。更改列表的数量不会产生明显的影响 per-collection（当然，只要一切都适合您的物理内存:)）。
好吧，即使在发布模式下仅在调试器外部进行简单的 Stopwatch 运行ning，并且对结果数据进行简单采样，这也是非常明显的。所以我们可以排除分析效果和统计错误。
但环境原因可能是什么？
- 除了数组大小调整之外，GC 根本不参与。没有分配，分析器非常清楚在调整大小之间也没有发生 GC 的事实（尽管这对于并发 GC 的价值有限 :)）。调整 GC 设置会使一切变得更慢，但同样只会影响调整大小峰值及其附近的环境。最重要的是，列表的数量（以及堆大小）对趋势没有任何影响，如果 GC 是原因，这将是非常令人惊讶的。
- 堆是碎片化的，但非常有序。这使得重定位在内存压力下的开销较小，但同样，只会影响数组大小调整。无论如何，这不足为奇，事实上有据可查。
所以，看着这一切......我不知道为什么存在这种趋势。但是，请注意，这种趋势肯定也不是线性的——随着列表大小的增加，增长会迅速下降。从大约 15k 项开始，趋势完全消失，所以 Add 确实是 O(1)，不包括数组调整大小 - 它只是在某些大小下有一些奇怪的行为:)
...除非您 pre-allocate 列表。在这种情况下，结果与我仅基于缓存位置的预测 100% 一致。这似乎表明调整大小和 GCing 模式对常用缓存算法的效率有巨大影响（至少在我的 CPU 上 - 这会有很大差异，我侦察）。还记得我们谈到在整个 Add 操作期间发生的缓存未命中吗？有一个诀窍——如果我们可以在两个循环之间保持足够的缓存行，缓存未命中将经常被避免；如果我们假设 64 字节缓存行和最佳缓存失效算法，您将不会错过 List 成员访问和数组长度访问，每个数组在 16 次添加中只有一次未命中。我们根本不需要数组的其余部分！您还需要一些其他缓存行（例如，列表实例），但数组是迄今为止最大的交易。
现在，让我们计算一下。十万 collections，2*64B 的缓存每个在最坏的情况下加起来是 12 MiB，而我有 10 MiB 的缓存 - 我可以 几乎 适合缓存中的所有相关数组数据！现在，当然，我不是唯一使用该缓存的应用程序（和线程），因此我们可以预期 flip-over 点略低于理想值 - 让我们看看如何更改 collection 的数量s 改变了我们的结果。
列出 pre-allocated 到 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 的缓存使用总量 - 很可能是我忽略了一些也需要缓存的重要事情的结果，或者对 OS 或 CPU 的一部分进行了一些优化以防止我占用整个缓存或其他东西:)
非常小的列表计数中的轻微 un-linearity 很可能与 lower-level 缓存的缓慢溢出有关 - 400 适合我的二级缓存，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 间接引起的（通过代码中的 sub-optimal 分配和 GC 中破坏缓存局部性的压缩模式）和 cache-overflow 直接引起的。对于较小的项目计数，任何给定的所需内存片现在更有可能在缓存中。当数组需要重新加载时ed，大部分缓存内存几乎没有价值，并且会慢慢失效并被更有用的内存取代 - 但整个内存使用模式与 CPU 优化的目标相去甚远。相反，通过保持数组的预分配，我们确保一旦我们在内存中有了列表，我们也能看到数组长度（奖励 1），并且已经指向数组末尾的缓存行将对一些循环有用（奖金 2）。由于没有调整数组大小，因此 none 个 object 根本需要在内存中移动，并且有很好的托管。
我对 .NET Framework 中实现的集合类型进行了一些基准测试。
从参考资料中我知道 List<T> 使用数组来存储内容。为避免在每次插入时调整数组大小，array length gets doubled 每次可用 space 用完。
现在我的基准测试会将随机 long 值插入到 List 中（有关大小 - 时间 - 图表，请参见上图）。在列表大小如 128 或 256 中有明显的 "lag spikes" 必须重新分配内部数组。但是在 512（和 128，虽然？）的大小下，似乎有很大的延迟，并且插入一项所需的时间持续增加。
在我的理解中，除了内部数组需要重新分配的情况外，图形应该是严格不变的。这种行为是否有任何原因，可能与 CLR 或 Windows 内存管理/内存碎片有关？
基准测试作为 64 位应用程序在 Windows 10 / i7-3630QM 机器上执行（源代码如下所示）。因为单个添加操作无法测量，所以我创建了 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 个添加操作。
Does C# store arrays larger than 512 longs (4096 bytes) differently?
没有。它在总大小为 (IIRC) 84kB 或更大时执行：使用大对象堆（不压缩或分代）。
但是：
create 1000 lists and add one item each for every list size.
每次测试的时间约为 5 毫秒。 Windows scheduler delta 大于该值（实际值从 40ms 到 100ms，具体取决于版本和版本）。您能看到调度程序正在执行线程切换吗？
建议您尝试将每个尺寸设为 运行 至少 250 毫秒，以平衡此类效果。
编辑：另外，正如 Lasse 对问题注释的评论：这可能是 GC。要从您的计时中消除它，请在大小循环开始时，但在启动时钟之前，强制执行 GC。同时监控 GC 性能计数器。
好了，我们先看图片中简单的部分。尖峰是由重新分配、复制和垃圾引起的 collection - 这没什么大惊奇的。第一次添加到列表的异常低的时间很容易用缓存局部性来解释——虽然堆仍然适合整个内存，内存访问可以是 运行dom，同时仍然是非常低的延迟。一旦堆变得足够大，并且数组长度值（以及列表计数值）距离插入的值足够远，缓存局部性就会产生明显的影响——在我的机器上用 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 - 没什么大不了的 t运行 在两个通用寄存器之间传递一个值，虽然 :) 然后是简单的乐观空值检查，最后是调用本身。
首先要注意的是没有b运行ching，所以没有b运行ching mis-predictions。其次，我们有两个内存访问 - 第一个是在堆栈上，这几乎保证 运行teed 总是在缓存中。第二个更糟——这就是我们遇到缓存局部性问题的地方。但是，由此产生的滞后完全取决于数组的长度（和数量），因此应该（并且确实）与数组大小调整相关。
是时候看看 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 在这里可以并行执行的操作并不多，但是三个内存访问应该仍然只支付一次延迟成本。 b运行ch 几乎总是会被正确预测——只有在我们达到数组大小时才会进行预测，之后我们对每个列表执行一次相同的 b运行ch。
剩下两部分：添加项目本身，并更新列表的内部版本（使列表中任何正在进行的枚举失败）：
_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
就是这样。我们有永远不会被采用的 b运行ch（假设 single-threaded；我们之前已经检查了数组大小）。我们有很多访问：四个与列表本身相关（包括两个更新），还有两个数组（包括一个更新）。现在，虽然列表中没有缓存未命中的原因（它几乎总是已经加载），但由于更新而导致失效。相反，在我们的场景中，数组访问总是会导致缓存未命中，唯一的例外是在第一次调整数组大小之前。实际上，您可以看到首先没有缓存未命中（数组和 object 并置，小），然后是一次未命中（仍然并置，但项目超出了缓存行），然后是两次（长度和项目访问都超出了缓存行）缓存行）。
这当然很有趣（并且可以从手动优化中受益 tiny :P），但它再次只给我们提供了分析数据的 "stairs" .重要的是，没有涉及分配，所以没有 GC。
有了所有这些，我得出结论，当不需要调整数组大小时，List.Add 确实是 O(1)。对于非常小的数组（以及与其引用位于同一位置的数组），有一些额外的优化可以使事情变得更快，但这不是impo在这里。
因此，您在分析数据中看到的趋势必须是环境因素，或者与分析本身直接相关，或者只是选择了错误的平均方法。例如，如果我 运行 在 100 000 个列表中这样做：
- 添加前 550 项
- 再添加 100 项
- 还有另外 100 项
时间 2 和 3 之间存在差异，但没有趋势 - 2 更快和 3 更快的可能性一样大（在 ~ 的时间跨度上相差约 2 毫秒） 400ms，所以大约有 0.5% 的偏差）。然而，如果我改为使用 2100 个项目执行 "warmup"，则后续步骤的时间几乎是之前的一半。更改列表的数量不会产生明显的影响 per-collection（当然，只要一切都适合您的物理内存:)）。
好吧，即使在发布模式下仅在调试器外部进行简单的 Stopwatch 运行ning，并且对结果数据进行简单采样，这也是非常明显的。所以我们可以排除分析效果和统计错误。
但环境原因可能是什么？
- 除了数组大小调整之外，GC 根本不参与。没有分配，分析器非常清楚在调整大小之间也没有发生 GC 的事实（尽管这对于并发 GC 的价值有限 :)）。调整 GC 设置会使一切变得更慢，但同样只会影响调整大小峰值及其附近的环境。最重要的是，列表的数量（以及堆大小）对趋势没有任何影响，如果 GC 是原因，这将是非常令人惊讶的。
- 堆是碎片化的，但非常有序。这使得重定位在内存压力下的开销较小，但同样，只会影响数组大小调整。无论如何，这不足为奇，事实上有据可查。
所以，看着这一切......我不知道为什么存在这种趋势。但是，请注意，这种趋势肯定也不是线性的——随着列表大小的增加，增长会迅速下降。从大约 15k 项开始，趋势完全消失，所以 Add 确实是 O(1)，不包括数组调整大小 - 它只是在某些大小下有一些奇怪的行为:)
...除非您 pre-allocate 列表。在这种情况下，结果与我仅基于缓存位置的预测 100% 一致。这似乎表明调整大小和 GCing 模式对常用缓存算法的效率有巨大影响（至少在我的 CPU 上 - 这会有很大差异，我侦察）。还记得我们谈到在整个 Add 操作期间发生的缓存未命中吗？有一个诀窍——如果我们可以在两个循环之间保持足够的缓存行，缓存未命中将经常被避免；如果我们假设 64 字节缓存行和最佳缓存失效算法，您将不会错过 List 成员访问和数组长度访问，每个数组在 16 次添加中只有一次未命中。我们根本不需要数组的其余部分！您还需要一些其他缓存行（例如，列表实例），但数组是迄今为止最大的交易。
现在，让我们计算一下。十万 collections，2*64B 的缓存每个在最坏的情况下加起来是 12 MiB，而我有 10 MiB 的缓存 - 我可以 几乎 适合缓存中的所有相关数组数据！现在，当然，我不是唯一使用该缓存的应用程序（和线程），因此我们可以预期 flip-over 点略低于理想值 - 让我们看看如何更改 collection 的数量s 改变了我们的结果。
列出 pre-allocated 到 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 的缓存使用总量 - 很可能是我忽略了一些也需要缓存的重要事情的结果，或者对 OS 或 CPU 的一部分进行了一些优化以防止我占用整个缓存或其他东西:)
非常小的列表计数中的轻微 un-linearity 很可能与 lower-level 缓存的缓慢溢出有关 - 400 适合我的二级缓存，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 间接引起的（通过代码中的 sub-optimal 分配和 GC 中破坏缓存局部性的压缩模式）和 cache-overflow 直接引起的。对于较小的项目计数，任何给定的所需内存片现在更有可能在缓存中。当数组需要重新加载时ed，大部分缓存内存几乎没有价值，并且会慢慢失效并被更有用的内存取代 - 但整个内存使用模式与 CPU 优化的目标相去甚远。相反，通过保持数组的预分配，我们确保一旦我们在内存中有了列表，我们也能看到数组长度（奖励 1），并且已经指向数组末尾的缓存行将对一些循环有用（奖金 2）。由于没有调整数组大小，因此 none 个 object 根本需要在内存中移动，并且有很好的托管。