链接列表，数组和硬件内存缓存 [英] 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屋！