将数组存储在缓存中

Question

我正在审查一个面试问题并与一位朋友交换笔记，我们在 CPU 缓存方面有不同的想法。

考虑一大组数据，例如一大组double，即：

double data[1024];

考虑使用动态分配的动态链表来存储相同数量的元素。该问题要求描述一些权衡：

1. 这允许更快的随机访问：我们都同意数组更快，因为您不必以线性方式遍历列表（O(n)），只需提供索引（O(1)）。
2. 比较两个相同长度的列表更快：我们都认为，如果只是原始数据类型，则数组将允许 a memcmp()，而链表需要逐元素比较以及解引用开销。
3. 如果您多次访问同一元素，哪个可以实现更有效的缓存？

就这一点而言3，这就是我们意见分歧的地方。我认为 CPU 将尝试缓存整个数组，如果数组太大，则无法将其存储在缓存中，因此不会有缓存的好处。通过链表，可以缓存各个元素。因此，在处理大量元素时，链表比静态数组更适合缓存“命中”。

对于这个问题：这两者中哪一个更适合缓存“命中”，现代系统可以缓存数组的一部分，还是需要整个数组，或者不会尝试？我也可以用来提供明确答案的任何对技术文档或标准的参考都会有很大帮助。

谢谢！

Answer 1

CPU 不知道你的数据结构。它或多或少地缓存原始内存块。因此，如果您认为可以多次访问同一个元素，而无需每次都遍历列表，那么链表和数组都没有优于对方的缓存优势。

然而，与动态分配的链表相比，数组在按顺序访问多个元素方面具有很大的优势。由于 CPU 高速缓存在大于 1 的内存块上运行double，因此当一个数组元素位于高速缓存中时，驻留在相邻地址的其他几个元素很可能也位于高速缓存中。因此，从主存储器进行一次（慢速）读取可以访问（快速）缓存的多个相邻数组元素。对于链表来说情况并非如此，因为节点可以分配在内存中的任何位置，并且即使单个节点也至少具有指针的开销next来稀释可以同时缓存的数据元素的数量。