链表、数组和硬件内存缓存 [英] Linked lists, arrays, and hardware memory caches

问题描述

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

While questions have been asked before about linked lists versus arrays, the answers mostly boil down to what most of us probably have already learned at some point:

• 列表擅长插入和删除
• 数组擅长随机访问

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

Now respectable people like Bjarne Stroustrup have argued that arrays practically always outperform linked lists because they make much better use of the caching architecture implemented in modern hardware. He also states that the performance advantage of arrays increases with their size.

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

While I basically understand his arguments and agree with him, I wonder if this is still true when the size of the array is significantly larger than cache size. I would say that this is the case where performance really matters.

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

推荐答案

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

Arrays perform better not only because of caching, but also because of prefetching.

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

Caching has 2 main benefits - sequential elements may reside in the same line, so you may fetch once and use the entire line multiple times (while in a linked list your next element is elsewhere so you don't enjoy the benefit). This benefit is reduced the bigger the elements become, and is gone once your element passes a line size.

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

The second benefit is more subtle - you get better utilization of the cache since it's organized in a way that benefits sequential allocation. This means that an array up to the cache size may still fit, while a randomly allocated list may have some collisions that would cause thrashing even if the list size is smaller than the cache.

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

However, aside from caching, the bigger benefit from spatially allocated structures is from prefetching. Most CPUs would automatically prefetch the next lines in a stream of accesses such as an array access, and would therefore eliminate all misses in a scenario of sequential access.

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

On the other hand, all these benefits are just optimizations, so they can only speed up the performance linearly, but can never mitigate an asymptotic complexity difference such as the O(1) insertion that the list provides. Eventually, you will need to benchmark your code to see if such cases are required and create a bottleneck - if so, a hybrid approach may be needed.

这篇关于链表、数组和硬件内存缓存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！