C 中数组的大小是否会影响访问或更改数组中的一段数据的时间
Does size of array in C affect time to access or change a piece of data in the array
标题说明了一切：
我创建数组，比如 ARRAY[10000]，
我设置了边界，我只需要访问 1-100 和 900-2000 之间的数据。
与我将数组声明为 ARRAY[2001]
相比，以这种方式访问 and/or 更改一条数据所花费的时间是否会更长？
如果我有一个只有 1-100 和 900-2000 数据的数组，访问 and/or 更改时间是否会更改？
我看过一些关于这方面的论文，但我还不清楚，希望我能在这里得到更简洁的答案。
不，至少正常情况下，无论数组大小如何，访问数组中任何项目的时间都是恒定的。
如果（例如）您定义了一个大于内存的数组，这可能会改变，因此 OS（假设您正在使用一个）最终会执行一些额外的分页以支持更大的数组。在大多数情况下，即使那样也不太可能产生太大影响。
我认为不应该。
当您访问一个元素时，您将访问内存位置 0 + (element) 因此，无论大小如何，它都会同时到达相同的内存位置。
可能是，但这取决于大小。
缓存大小
访问范围的大小会改变延迟。
int ARRAY[10000] 适合一级缓存(32KB)
适合 L1 缓存（32KB）的非常小的访问，haswell 需要 4 个时钟。
但是L2缓存访问需要12个时钟。
在此处查看详细信息
http://www.7-cpu.com/cpu/Haswell.html
缓存冲突
它CPU的另一个核心修改数组中的一些数据，本地缓存行状态将被修改为Invalid状态。
Invalid 表示缓存行的延迟要高得多。
NUMA
一些主板上有多个CPU插槽的环境，称为non-uniform memory access环境。
那可能有巨大的内存容量，但是内存的某些地址可能驻留在CPU1，其他内存地址可能驻留在CPU2.
int huge_array[SOME_FUGE_SIZE]; // it strides multiple CPU's DIMM
// suppose that entire huge_array is out of cache.
huge_array[ADDRESS_OF_CPU1] = 1; // maybe fast for CPU1
huge_array[ADDRESS_OF_CPU2] = 1; // maybe slow for CPU2
但我想知道巨大的数组跨越多个 CPU 的内存。
巨大数组的分配可能会简单地失败。
这取决于 OS.
如果不经常访问数组，那么数组的大小可能不会产生太大影响，因为无论如何都会出现缓存未命中。在这种情况下，时间将取决于 CPU 进行任何 "virtual address to physical address" 转换并从 RAM 中获取数据的速度。
访问数组中的内容越频繁，缓存效果就越重要。这些缓存效果在很大程度上取决于不同缓存的数量、大小和速度。
但是，这也取决于您的访问模式。例如，如果您有一个 1 GiB 的数组并且经常访问其中的 5 个字节，那么大小不会有太大差异，因为您经常访问的 5 个字节将在缓存中。再举一个例子，如果您使用顺序访问模式（例如 "for each element in array { ... }"），那么 CPU 可能会进行硬件预取，您不会支付缓存未命中的全部成本。
典型的80x86系统，访问模式随机，访问频繁；大约有 5 种不同的尺寸很重要。第一个（最小的）是 L1 数据缓存大小——如果数组适合 L1 数据缓存，那么无论数组是 20 字节还是 20 KiB，它都会相对较快。下一个大小是 L2 数据缓存大小——随着数组变大，"L1 hits to L2 hits" 的比率降低并且性能变得更差，直到（可能 "twice as large than L1"）L1 命中变得可以忽略不计。然后（对于某些确实具有 L3 缓存的 CPUs）L3 缓存大小也会发生同样的情况，其中随着数组变大，"L2 hits to L3 hits" 的比率会降低。
一旦超过最大缓存，"cache hits to cache misses" 的比率就会降低。
下一个重要的大小是 TLB 大小。大多数现代操作系统都使用分页，并且大多数现代 CPUs 缓存 "virtual address to physical address conversions" 在通常称为转换后备缓冲区的东西中。如果数组很大，那么您会开始出现 TLB 未命中（除了高速缓存未命中），这会使性能变差（因为 CPU 在将虚拟地址转换为物理地址时无法避免额外的工作）。
最后，最后一个重要的大小是您实际拥有多少 RAM。如果您有一个 10 TiB 的阵列、4 GiB 的 RAM 和 20 TiB 的交换空间 space；然后 OS 将交换数据 to/from 磁盘，磁盘 IO 的开销将主导性能。
当然，您经常会为许多不同的计算机创建可执行文件（例如“64 位 80x86，从古老的 Athlon 到现代的 Haswell”）。在那种情况下，您无法知道大部分重要的细节（例如缓存大小），并且它成为猜测之间的折衷（由于 "array too large" 导致的缓存未命中的估计开销与由 [= 引起的其他事情的估计开销） 34=]).
在信息理论中，正如其他人所说，数组访问是恒定的，因此不会根据数组大小而增加或减少成本。不过，这个问题似乎是关于 真实现场表演 的，数组大小肯定很重要。 @Brendan 接受的答案很好地解释了这是怎么回事。
实践中需要考虑的事项：
* 你的数组元素有多大：bool[1000]、MyStruct[1000]和MyStruct*[1000]在访问性能上可能会有很大差异
* 尝试为两种方式编写代码，一次使用大数组，一次将所需数据保存在较小的数组中。然后 运行 目标硬件上的代码，并比较性能。您经常会惊讶地发现，优化尝试会使性能变差，并且在此过程中您了解了很多有关硬件及其怪癖的知识。
标题说明了一切：
我创建数组，比如 ARRAY[10000]， 我设置了边界，我只需要访问 1-100 和 900-2000 之间的数据。
与我将数组声明为 ARRAY[2001]
相比，以这种方式访问 and/or 更改一条数据所花费的时间是否会更长？如果我有一个只有 1-100 和 900-2000 数据的数组，访问 and/or 更改时间是否会更改？
我看过一些关于这方面的论文，但我还不清楚，希望我能在这里得到更简洁的答案。
不，至少正常情况下，无论数组大小如何，访问数组中任何项目的时间都是恒定的。
如果（例如）您定义了一个大于内存的数组，这可能会改变，因此 OS（假设您正在使用一个）最终会执行一些额外的分页以支持更大的数组。在大多数情况下，即使那样也不太可能产生太大影响。
我认为不应该。
当您访问一个元素时，您将访问内存位置 0 + (element) 因此，无论大小如何，它都会同时到达相同的内存位置。
可能是，但这取决于大小。
缓存大小
访问范围的大小会改变延迟。
int ARRAY[10000] 适合一级缓存(32KB)
适合 L1 缓存（32KB）的非常小的访问，haswell 需要 4 个时钟。
但是L2缓存访问需要12个时钟。
在此处查看详细信息 http://www.7-cpu.com/cpu/Haswell.html
缓存冲突
它CPU的另一个核心修改数组中的一些数据，本地缓存行状态将被修改为Invalid状态。
Invalid 表示缓存行的延迟要高得多。
NUMA
一些主板上有多个CPU插槽的环境，称为non-uniform memory access环境。
那可能有巨大的内存容量，但是内存的某些地址可能驻留在CPU1，其他内存地址可能驻留在CPU2.
int huge_array[SOME_FUGE_SIZE]; // it strides multiple CPU's DIMM
// suppose that entire huge_array is out of cache.
huge_array[ADDRESS_OF_CPU1] = 1; // maybe fast for CPU1
huge_array[ADDRESS_OF_CPU2] = 1; // maybe slow for CPU2
但我想知道巨大的数组跨越多个 CPU 的内存。 巨大数组的分配可能会简单地失败。 这取决于 OS.
如果不经常访问数组，那么数组的大小可能不会产生太大影响，因为无论如何都会出现缓存未命中。在这种情况下，时间将取决于 CPU 进行任何 "virtual address to physical address" 转换并从 RAM 中获取数据的速度。
访问数组中的内容越频繁，缓存效果就越重要。这些缓存效果在很大程度上取决于不同缓存的数量、大小和速度。
但是，这也取决于您的访问模式。例如，如果您有一个 1 GiB 的数组并且经常访问其中的 5 个字节，那么大小不会有太大差异，因为您经常访问的 5 个字节将在缓存中。再举一个例子，如果您使用顺序访问模式（例如 "for each element in array { ... }"），那么 CPU 可能会进行硬件预取，您不会支付缓存未命中的全部成本。
典型的80x86系统，访问模式随机，访问频繁；大约有 5 种不同的尺寸很重要。第一个（最小的）是 L1 数据缓存大小——如果数组适合 L1 数据缓存，那么无论数组是 20 字节还是 20 KiB，它都会相对较快。下一个大小是 L2 数据缓存大小——随着数组变大，"L1 hits to L2 hits" 的比率降低并且性能变得更差，直到（可能 "twice as large than L1"）L1 命中变得可以忽略不计。然后（对于某些确实具有 L3 缓存的 CPUs）L3 缓存大小也会发生同样的情况，其中随着数组变大，"L2 hits to L3 hits" 的比率会降低。
一旦超过最大缓存，"cache hits to cache misses" 的比率就会降低。
下一个重要的大小是 TLB 大小。大多数现代操作系统都使用分页，并且大多数现代 CPUs 缓存 "virtual address to physical address conversions" 在通常称为转换后备缓冲区的东西中。如果数组很大，那么您会开始出现 TLB 未命中（除了高速缓存未命中），这会使性能变差（因为 CPU 在将虚拟地址转换为物理地址时无法避免额外的工作）。
最后，最后一个重要的大小是您实际拥有多少 RAM。如果您有一个 10 TiB 的阵列、4 GiB 的 RAM 和 20 TiB 的交换空间 space；然后 OS 将交换数据 to/from 磁盘，磁盘 IO 的开销将主导性能。
当然，您经常会为许多不同的计算机创建可执行文件（例如“64 位 80x86，从古老的 Athlon 到现代的 Haswell”）。在那种情况下，您无法知道大部分重要的细节（例如缓存大小），并且它成为猜测之间的折衷（由于 "array too large" 导致的缓存未命中的估计开销与由 [= 引起的其他事情的估计开销） 34=]).
在信息理论中，正如其他人所说，数组访问是恒定的，因此不会根据数组大小而增加或减少成本。不过，这个问题似乎是关于 真实现场表演 的，数组大小肯定很重要。 @Brendan 接受的答案很好地解释了这是怎么回事。
实践中需要考虑的事项：
* 你的数组元素有多大：bool[1000]、MyStruct[1000]和MyStruct*[1000]在访问性能上可能会有很大差异
* 尝试为两种方式编写代码，一次使用大数组，一次将所需数据保存在较小的数组中。然后 运行 目标硬件上的代码，并比较性能。您经常会惊讶地发现，优化尝试会使性能变差，并且在此过程中您了解了很多有关硬件及其怪癖的知识。