就局部性而言，数组与链表 [英] 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.

我对链表的理解是，由于遍历链表的路径是可预测的，所以缓存将利用它并仍然存储适当的内存块，即使链表的节点可能相距很远堆内.

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.

推荐答案

你对数组案例的理解大多是正确的.如果按顺序访问数组，许多处理器不仅会获取包含该元素的块，还会预取后续块以最大程度地减少等待缓存未命中所花费的周期.如果您使用的是 Intel x86 处理器，您可以在 Intel x86 optimization 手册.此外，如果数组元素足够小，加载包含元素的块意味着下一个元素可能在同一块中.

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.

不幸的是，对于链表，从处理器的角度来看，加载模式是不可预测的.它不知道在地址 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).

作为一个具体的例子，顺序数组访问的加载地址序列很好且可预测.例如 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等，很难预测下一个地址.

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

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