为什么缓存局部性对阵列性能至关重要？

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

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

考虑以下数组的可能的内存布局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，我们将不得不再次进入内存。