c - 在缓存中存储数组

Question

我正在复习一个面试问题并与一位 friend 比较笔记，我们在 CPU 缓存方面有不同的想法。

考虑一个大数据集，比如一个大数组double，即:

double data[1024];

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

1. 允许更快的随机访问:我们都同意数组更快，因为您不必以线性方式遍历列表 (O(n))，只需提供一个索引(O(1))。
2. 比较两个相同长度的列表哪个更快:我们都决定如果它只是原始数据类型，数组将允许 memcmp()，而链表需要元素-明智的比较加上取消引用的开销。
3. 如果您多次访问同一个元素，哪个可以实现更高效的缓存？

在第 3 点，这是我们意见不同的地方。我争辩说 CPU 将尝试缓存整个数组，如果数组大得离谱，它就无法存储在缓存中，因此缓存不会带来任何好处。使用链表，可以缓存单个元素。因此，在处理大量元素时，链表比静态数组更有助于缓存“命中”。

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

谢谢!

Answer 1

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

但是，数组在按顺序访问多个元素方面比动态分配的链表有很大的优势。由于 CPU 缓存在大于一个 double 的内存块上运行，当一个数组元素在缓存中时，很可能位于相邻地址的其他几个元素也在缓存中。因此，一次(慢速)从主内存读取可以访问(快速)缓存访问多个相邻数组元素。链表则不同，因为节点可以分配在内存中的任何位置，即使是单个节点也至少具有 next 指针的开销，以减少可能被缓存的数据元素的数量同时。