arrays - 链表、数组和硬件内存缓存

Question

虽然之前有人问过关于链表与数组的问题，但答案大多归结为我们大多数人在某个时候可能已经学到的东西:

列表擅长插入和删除

数组擅长随机访问

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

虽然我基本上理解他的论点并同意他的观点，但我想知道当数组的大小明显大于缓存大小时，这是否仍然正确。我会说这是性能真正重要的情况。

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

Answer 1

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

缓存有两个主要好处 - 顺序元素可能驻留在同一行中，因此您可以获取一次并多次使用整行(而在链表中，您的下一个元素在其他地方，因此您无法享受好处)。这种好处随着元素变得越大而减少，并且一旦您的元素超过行大小就消失了。

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

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

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