为什么caching区域对于arrays性能很重要？
在下面的博客中，有一个关于数组优于链表的说法：
数组有更好的caching局部性，可以使性能有很大的差异。
那是什么意思？ 我不明白caching区域如何提供巨大的性能优势。
看到我的答案关于空间和时间的地方 。
特别是，数组是连续的内存块，所以大量的数据块将在第一次访问时被加载到caching中。 这使得访问数组的未来元素相对较快。 另一方面，链接列表不一定在连续的内存块中，并且可能导致更多的caching未命中，这增加了访问它们所花费的时间。
考虑大型结构的数组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周期中非常慢的操作）。 但是，在第一次访问之后，数组的其余部分将在caching中，随后的访问将更快。 通过链表，第一次访问ffff 1000也需要我们去记忆。 不幸的是，处理器会直接caching这个位置的内存，比如说直到ffff 2000 。 正如你所看到的，这实际上并没有捕获列表中的任何其他元素，这意味着当我们访问l_data->next ，我们将再次访问内存。
通常，使用数组时，您可以访问彼此靠近的项目。 顺序访问数组时，尤其如此。
当你访问内存的时候，它的一些块被caching在不同的层次上。 高速caching局部性是指连续操作在高速caching中的可能性，因此速度更快。 在数组中，您可以最大化顺序元素访问在caching中的机会。
通过列表，反例，不能保证在列表中顺序出现的项目实际上被排列在彼此相邻的内存中。 这意味着更less的caching命中和性能下降。
