我正在审查一个面试问题，并与朋友比较笔记，关于CPU缓存，我们有一个不同的想法。
考虑大量数据，例如的大数组double，即：
double data[1024];
考虑使用动态分配的动态链表来存储相同数量的元素。该问题要求描述一些折衷方案：
O(n)），只需提供索引（O(1)）即可。memcmp()，而链接列表则需要逐元素比较并取消引用开销。就这一点而言3，这是我们意见分歧的地方。我认为CPU将尝试缓存整个数组，并且如果数组过大，则无法将其存储在缓存中，因此不会有缓存的好处。使用链接列表，可以缓存单个元素。因此，当处理大量元素时，链表比静态数组更适合缓存“命中”。
问题是：两者中哪一个更适合缓存“命中”，现代系统是否可以缓存数组的一部分，或者它们是否需要整个数组，否则将无法尝试？我还可以使用对技术文档或标准的任何引用来提供明确的答案，这将大有帮助。
谢谢！
CPU不知道您的数据结构。它缓存或多或少的原始内存块。因此，如果您假设可以多次访问同一个元素而无需每次都遍历列表，那么链表和数组都不会比另一个具有缓存优势。
但是，与动态分配的链表相比，数组在顺序访问多个元素方面具有很大的优势。因为CPU高速缓存在大于1的内存块上运行double，所以当一个数组元素位于高速缓存中时，驻留在相邻地址中的其他几个数组元素也可能也在高速缓存中。因此，从主存储器读取一次（缓慢）可访问对多个相邻阵列元素的（快速）缓存访问。对于链表，情况并非如此，因为可以在内存中的任何位置分配节点，甚至单个节点也至少具有next指针的开销，以减少可以同时缓存的数据元素的数量。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句