比如数组vs链表中地区而言 [英] Arrays vs Linked Lists in terms of locality

问题描述

假设我们有一个排序的数组和链表。
对于这两个数据结构元素搜索时，最坏的情况将是为O（n），但我的问题是：

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.

我给一个链表的理解是，因为这将被带到遍历列表中的路径是predictable，那么缓存将利用这一点，仍然存储的存储器的相应的块，即使在列表中的节点可以相隔很远堆内。

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.

推荐答案

您的数组的情况下理解是正确的大部分。当一个阵列被顺序访问，许多处理器不仅将获得一个包含该元素的块，而且也会prefetch后续块，以尽量减少周期花在等待上高速缓存未命中。如果您使用的是英特尔x86处理器，你可以找到在Intel的x86优化<关于这个细节href=\"http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html\"相对=nofollow称号=手动>手动。另外，如果阵列元素是足够小，加载包含的元素的块装置的下一个元素有可能在相同的块中。

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.

不幸的是，对于链表负载的图案是从图处理器的点未predictable。它不知道在加载地址X的元素，下一个地址的内容时（X + 8）。

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).

作为一个具体的例子，加载地址为顺序数组访问的顺序是好的，predictable。
例如，1000，1016，1032，1064，等等。

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.

有关链表它看起来像：
1000，3048，5040，7888，等等很难predict下一个地址。

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

这篇关于比如数组vs链表中地区而言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！