链接列表,数组和硬件内存缓存

Question

虽然之前已经提出了关于链表和数组的问题,但答案大多归结为我们大多数人在某些时候可能已经学到的东西:

现在像Bjarne Stroustrup这样受人尊敬的人认为,数组实际上总是优于链表,因为它们更好地利用了现代硬件中实现的缓存架构.他还指出,阵列的性能优势随着它们的大小而增加.

虽然我基本上理解他的论点并同意他,但我想知道当数组的大小远大于缓存大小时,这是否仍然是正确的.我会说,性能真的很重要.

总结一下:在大多数情况下,数组仍然比列表表现更好,即使它们的大小比缓存大小大得多,并且大部分操作都是插入或删除吗？如果是,如何解释？

Answer 1

数组的性能更好不仅因为缓存，还因为预取。

缓存有两个主要好处 - 顺序元素可能驻留在同一行中，因此您可以获取一次并多次使用整行（而在链接列表中，您的下一个元素位于其他位置，因此您无法享受到这种好处）。元素变得越大，这种好处就会减少，并且一旦元素超过线条尺寸，这种好处就会消失。

第二个好处更加微妙 - 您可以更好地利用缓存，因为它的组织方式有利于顺序分配。这意味着达到缓存大小的数组可能仍然适合，而随机分配的列表可能会存在一些冲突，即使列表大小小于缓存，也会导致颠簸。

然而，除了缓存之外，空间分配结构的更大好处是预取。大多数 CPU 会自动预取访问流（例如数组访问）中的下一行，因此会消除顺序访问场景中的所有未命中。

另一方面，所有这些好处都只是优化，因此它们只能线性加速性能，但永远无法减轻渐近复杂度差异，例如列表提供的 O(1) 插入。最终，您需要对代码进行基准测试，看看是否需要这种情况并产生瓶颈 - 如果是这样，可能需要采用混合方法。