为什么缓存局部性对数组性能很重要？

Question

在下面的博客中,有一个关于数组优于链表的优点的声明:

数组具有更好的缓存局部性,可以在性能上产生很大的差异.

那是什么意思？我不明白缓存本地如何提供巨大的性能优势.

Answer 1

请参阅我关于空间和时间局部性的答案.

特别是,数组是连续的内存块,因此在第一次访问时,它们的大块将被加载到高速缓存中.这使得访问阵列的未来元素相对较快.另一方面,链接列表不一定在连续的内存块中,并且可能导致更多的高速缓存未命中,这增加了访问它们所花费的时间.

考虑以下可能的内存布局,用于数组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,我们将再次进入内存.

Answer 2

通常,在使用阵列时,您可以访问彼此靠近的项目.在顺序访问数组时尤其如此.

当您访问内存时,它的一大块缓存在各个级别. 缓存局部性是指连续操作在缓存中的可能性,因此更快.在数组中,最大化顺序元素访问在缓存中的机会.

对于列表,通过反例,不能保证列表中按顺序出现的项目实际上在内存中彼此靠近排列.这意味着缓存命中次数减少,性能下降.