阵列与链接列表的地域性 [英] Arrays vs Linked Lists in terms of locality

问题描述

说我们有一个未排序的数组和链表。
当搜索两个数据结构的元素时，最糟糕的情况是O（n），但我的问题是：

数组是否仍然更快因为在缓存中使用空间局部性，还是缓存使用分支局部性，允许链表与任何数组一样快？

我的理解一个数组是如果一个元素被访问，那么这个内存块和许多周围的块然后被带入高速缓存，从而允许更快的存储器访问。

我对链表的理解是，由于将要遍历列表的路径是可预测的，因此缓存将利用该缓存并仍然存储适当的块即使列表中的节点在堆内也可以相距很远。

解决方案

正确。如果顺序访问阵列，则许多处理器不仅将获取包含该元素的块，而且还将预取后续块以最小化等待高速缓存未命中的周期。如果您使用的是Intel x86处理器，可以在Intel x86优化中找到有关详细信息 manual 。此外，如果数组元素足够小，加载包含元素的块意味着下一个元素可能在同一个块中。

不幸的是，对于链表，从处理器的角度来看，负载是不可预测的。它不知道在地址X上加载元素时下一个地址是（X + 8）的内容。

作为一个具体的例子，连续数组访问的加载地址是好的和可预测的。
例如，1000，1016，1032，1064等。

对于链接列表，它将如下所示：
1000,3048,5040 ，7888等。很难预测下一个地址。

Say we have an unsorted array and linked list. The worst case when searching for an element for both data structures would be O( n ), but my question is:

Would the array still be way faster because of the use of spatial locality within the cache, or will the cache make use of branch locality allowing linked lists to be just as fast as any array ?

My understanding for an array is that if an element is accessed, that block of memory and many of the surrounding blocks are then brought into the cache allowing for much faster memory accesses.

My understanding for a linked list is that since the path that will be taken to traverse the list is predictable, then the cache will exploit that and still store the appropriate blocks of memory even though the nodes of the list can be far apart within the heap.

解决方案

Your understanding of the the array case is mostly correct. If an array is accessed sequentially, many processors will not only fetch the block containing the element, but will also prefetch subsequent blocks to minimize cycles spent waiting on cache misses. If you are using an Intel x86 processor, you can find details about this in the Intel x86 optimization manual. Also, if the array elements are small enough, loading a block containing an element means the next element is likely in the same block.

Unfortunately, for linked lists the pattern of loads is unpredictable from the processor's point of view. It doesn't know that when loading an element at address X that the next address is the contents of (X + 8).

As a concrete example, the sequence of load addresses for a sequential array access is nice and predictable. For example, 1000, 1016, 1032, 1064, etc.

For a linked list it will look like: 1000, 3048, 5040, 7888, etc. Very hard to predict the next address.

这篇关于阵列与链接列表的地域性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！