arrays - 为什么缓存局部性对阵列性能很重要？

Question

如下blog有一个关于数组相对于链表的优点的说法:

Arrays have better cache locality that can make a pretty big difference in performance.

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

Answer 1

查看我的回答 about spatial and temporal locality 。

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

考虑以下可能的大型结构数组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时，我们将再次不得不访问内存。