C中数组的大小是否会影响访问或更改数组中数据的时间

Question

标题说明了一切：

我创建并排列数组，比如 ARRAY[10000]，我设置了只需要访问 1-100 和 900-2000 数据的边界。

与将数组声明为 ARRAY[2001] 相比，以这种方式访问​​和/或更改数据的时间是否会花费更多的时间？

如果我的数组只有 1-100 和 900-2000 的数据，访问和/或更改时间会改变吗？

我看过一些关于这方面的论文，但我不清楚它们，希望我能在这里得到更简洁的答案。

Answer 1

如果不经常访问数组，则数组的大小可能不会有太大区别，因为无论如何您都会遇到缓存未命中。在这种情况下，时间将取决于 CPU 执行任何“虚拟地址到物理地址”转换以及从 RAM 中获取数据的速度。

访问数组中的内容越频繁，缓存效果就越重要。这些缓存效果在很大程度上取决于不同缓存的数量、大小和速度。

但是，这也取决于您的访问模式。例如，如果您有一个 1 GiB 数组并经常访问其中的 5 个字节，那么大小不会有太大区别，因为您经常访问的 5 个字节将在缓存中。再举一个例子，如果您使用顺序访问模式（例如“对于数组 { ... } 中的每个元素”），那么 CPU 可能会执行硬件预取，而您不会支付缓存未命中的全部成本。

对于典型的 80x86 系统，具有随机访问模式和频繁访问；大约有 5 种不同的尺寸很重要。第一个（最小的）是 L1 数据缓存大小 - 如果数组适合 L1 数据缓存，那么无论数组是 20 字节还是 20 KiB，它都会相对较快。下一个大小是 L2 数据缓存大小 - 随着数组变大，“L1 命中与 L2 命中”的比率降低并且性能变差，直到（可能是“L1 的两倍大”）L1 命中变得可以忽略不计。然后（对于某些具有 L3 缓存的 CPU），L3 缓存大小也会发生同样的情况，随着阵列变大，“L2 命中与 L3 命中”的比率会降低。

一旦大于最大缓存，“缓存命中与缓存未命中”的比率就会降低。

下一个重要的大小是 TLB 大小。大多数现代操作系统使用分页，大多数现代 CPU 将“虚拟地址到物理地址的转换”缓存在通常称为转换后备缓冲区的东西中。如果数组很大，那么您会开始遇到 TLB 未命中（除了缓存未命中），这会使性能变差（因为 CPU 在将虚拟地址转换为物理地址时无法避免额外的工作）。

最后，最后一个重要的大小是您实际拥有多少 RAM。如果您有 10 TiB 阵列、4 GiB RAM 和 20 TiB 交换空间；然后操作系统将与磁盘交换数据，磁盘 IO 的开销将主导性能。

当然，您经常为许多不同的计算机创建可执行文件（例如“64 位 80x86，从古代 Athlon 到现代 Haswell”）。在这种情况下，您无法知道大部分重要的细节（例如缓存大小），它会在猜测之间做出妥协（由于“数组太大”而导致缓存未命中的估计开销与由“数组”引起的其他事物的估计开销）太小”）。