C中使用链表的CPU缓存缺点

Question

我想知道与 C 中的连续数组相比，链表的优点和缺点是什么。因此，我阅读了一篇关于链表的维基百科文章。 https://en.wikipedia.org/wiki/Linked_list#Disadvantages

根据这篇文章，缺点如下:

• They use more memory than arrays because of the storage used by their pointers.
• Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.

• Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating.

• Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.

我理解前三点，但我很难理解最后一点:

节点存储不连续，大大增加了访问列表中单个元素所需的时间，尤其是在有 CPU 缓存的情况下。

关于 CPU Cache 的文章没有提到任何关于非连续内存阵列的内容。据我所知，CPU 缓存仅缓存频繁使用的地址，总共有 10^-6 次缓存未命中。

因此，我不明白为什么当涉及到非连续内存阵列时，CPU 缓存的效率应该较低。

Answer 1

CPU 缓存实际上做了两件事。

你说的是缓存最近使用的内存。

然而，另一个是预测在不久的将来将使用哪个内存。该算法通常非常简单 - 它假设程序处理大量数据，并且每当它访问一些内存时，它都会预取后面的几个字节。

这不适用于链表，因为节点是随机放置在内存中的。

此外，CPU 加载更大的内存块(64、128 字节)。同样，对于单次读取的 int64 数组，它具有用于处理 8 或 16 个元素的数据。对于链表，它读取一个 block ，其余的可能会被浪费，因为下一个节点可能位于完全不同的内存块中。

最后但同样重要的是，与上一节相关 - 链表需要更多内存用于其管理，最简单的版本至少需要额外的 sizeof(pointer) 字节用于指向下一个节点的指针。但它不再与 CPU 缓存有关。