82

在下面的博客中，有一个关于数组优于链表的声明：

数组具有更好的缓存局部性，可以在性能上产生相当大的差异。

这意味着什么？我不明白缓存局部性如何提供巨大的性能优势。

4

2 回答 2

125

请参阅我关于时空局部性的回答。

特别是，数组是连续的内存块，因此它们中的大块将在第一次访问时加载到缓存中。这使得访问数组的未来元素相对较快。另一方面，链表不一定位于连续的内存块中，并且可能导致更多的缓存未命中，从而增加了访问它们所需的时间。

考虑以下可能的内存布局，用于数组和大型结构的data链表l_data

Address      Contents       | Address      Contents
ffff 0000    data[0]        | ffff 1000    l_data
ffff 0040    data[1]        |   ....
ffff 0080    data[2]        | ffff 3460    l_data->next
ffff 00c0    data[3]        |   ....
ffff 0100    data[4]        | ffff 8dc0    l_data->next->next
                            | ffff 8e00    l_data->next->next->next
                            |   ....
                            | ffff 8f00    l_data->next->next->next->next

如果我们想遍历这个数组，第一次访问ffff 0000将需要我们去内存中检索（CPU 周期中的一个非常慢的操作）。但是，在第一次访问之后，数组的其余部分将在缓存中，后续访问会快得多。使用链表，第一次访问ffff 1000也需要我们去记忆。不幸的是，处理器将直接缓存该位置周围的内存，比如说一直到ffff 2000. 如您所见，这实际上并没有捕获列表的任何其他元素，这意味着当我们访问时l_data->next，我们将再次访问内存。

于 2012-08-22T03:00:10.853 回答
14

通常，在使用数组时，您会访问彼此靠近的项目。在顺序访问数组时尤其如此。

当你访问内存时，它的一部分被缓存在不同的级别。 缓存局部性是指连续操作在缓存中的可能性，因此速度更快。在数组中，您可以最大限度地提高顺序元素访问在缓存中的机会。

对于列表，作为反例，不能保证在列表中按顺序出现的项目实际上在内存中彼此靠近排列。这意味着更少的缓存命中和性能下降。

于 2012-08-22T03:01:17.630 回答