在缓存中存储数组
Storing arrays in cache
我正在复习一个面试问题并与一位朋友比较笔记，我们在 CPU 缓存方面有不同的想法。
考虑一大组数据，比如double的大数组，即：
double data[1024];
考虑使用动态分配的即时链表来存储相同数量的元素。该问题要求描述一些权衡：
- 允许更快的随机访问：我们都同意数组更快，因为您不必以线性方式遍历列表 (
O(n))，只需提供一个索引 (O(1)).
- 比较两个相同长度的列表更快：我们都决定如果它只是原始数据类型，数组将允许
memcmp()，而链表需要逐元素比较加上取消引用开销。
- 如果您多次访问同一个元素，哪个允许更有效的缓存？
在3点，这是我们意见不同的地方。我争辩说 CPU 将尝试缓存整个数组，如果数组非常大，则无法将其存储在缓存中，因此缓存不会带来任何好处。使用链表，可以缓存单个元素。因此，在处理大量元素时，链表比静态数组更适合缓存 "hits"。
关于这个问题：这两者中哪一个更适合缓存 "hits"，现代系统是否可以缓存数组的一部分，或者他们是否需要整个数组或者不会尝试？我也可以用来提供明确答案的任何对技术文件或标准的参考都会有很大帮助。
谢谢！
缓存不知道数组，它们只看到内存访问并在该地址附近存储一点内存。一旦您访问了某个地址的某些内容，它应该会在缓存中停留一段时间，而不管该地址是属于数组还是链表。但是缓存控制器并不真正知道正在访问什么。
当您遍历数组时，缓存系统可能会预取数组的下一位。这通常是启发式驱动的（可能有一些编译器提示）。
一些硬件和工具链提供内部函数，让您可以控制缓存驻留（通过预取、显式刷新等）。通常你不需要这种控制，但对于像 DSP 代码、资源受限的游戏机和 OS 级别的东西需要担心缓存一致性，人们使用这个功能是很常见的。
CPU 不知道你的数据结构。它缓存或多或少的原始内存块。因此，如果你假设你可以多次访问同一个元素而无需每次遍历列表，那么链表和数组都没有缓存优势。
但是，数组在按顺序访问多个元素方面比动态分配的链表有很大的优势。因为 CPU 缓存在大于一个 double 的内存块上运行，当一个数组元素在缓存中时，很可能驻留在相邻地址的其他几个元素也在缓存中。因此，一次（慢速）从主内存读取可以访问（快速）缓存访问多个相邻数组元素。链表则不同，因为节点可以分配在内存中的任何位置，即使是单个节点也至少有一个 next 指针的开销来稀释可能同时缓存的数据元素的数量时间.
我正在复习一个面试问题并与一位朋友比较笔记，我们在 CPU 缓存方面有不同的想法。
考虑一大组数据，比如double的大数组，即：
double data[1024];
考虑使用动态分配的即时链表来存储相同数量的元素。该问题要求描述一些权衡：
- 允许更快的随机访问：我们都同意数组更快，因为您不必以线性方式遍历列表 (
O(n))，只需提供一个索引 (O(1)). - 比较两个相同长度的列表更快：我们都决定如果它只是原始数据类型，数组将允许
memcmp()，而链表需要逐元素比较加上取消引用开销。 - 如果您多次访问同一个元素，哪个允许更有效的缓存？
在3点，这是我们意见不同的地方。我争辩说 CPU 将尝试缓存整个数组，如果数组非常大，则无法将其存储在缓存中，因此缓存不会带来任何好处。使用链表，可以缓存单个元素。因此，在处理大量元素时，链表比静态数组更适合缓存 "hits"。
关于这个问题：这两者中哪一个更适合缓存 "hits"，现代系统是否可以缓存数组的一部分，或者他们是否需要整个数组或者不会尝试？我也可以用来提供明确答案的任何对技术文件或标准的参考都会有很大帮助。
谢谢！
缓存不知道数组，它们只看到内存访问并在该地址附近存储一点内存。一旦您访问了某个地址的某些内容，它应该会在缓存中停留一段时间，而不管该地址是属于数组还是链表。但是缓存控制器并不真正知道正在访问什么。
当您遍历数组时，缓存系统可能会预取数组的下一位。这通常是启发式驱动的（可能有一些编译器提示）。
一些硬件和工具链提供内部函数，让您可以控制缓存驻留（通过预取、显式刷新等）。通常你不需要这种控制，但对于像 DSP 代码、资源受限的游戏机和 OS 级别的东西需要担心缓存一致性，人们使用这个功能是很常见的。
CPU 不知道你的数据结构。它缓存或多或少的原始内存块。因此，如果你假设你可以多次访问同一个元素而无需每次遍历列表，那么链表和数组都没有缓存优势。
但是，数组在按顺序访问多个元素方面比动态分配的链表有很大的优势。因为 CPU 缓存在大于一个 double 的内存块上运行，当一个数组元素在缓存中时，很可能驻留在相邻地址的其他几个元素也在缓存中。因此，一次（慢速）从主内存读取可以访问（快速）缓存访问多个相邻数组元素。链表则不同，因为节点可以分配在内存中的任何位置，即使是单个节点也至少有一个 next 指针的开销来稀释可能同时缓存的数据元素的数量时间.