Kac*_*acy 12 arrays caching linked-list data-structures localityofreference
假设我们有一个未排序的数组和链表.搜索两个数据结构的元素时最糟糕的情况是O(n),但我的问题是:
由于在缓存中使用空间局部性,阵列是否仍然会更快,或者缓存是否会使用分支局部性,从而允许链接列表与任何阵列一样快？
我对数组的理解是,如果访问一个元素,那么该存储器块和许多周围的块将被带入高速缓存,从而允许更快的存储器访问.
我对链表的理解是,由于遍历列表所采用的路径是可预测的,因此缓存将利用它并仍然存储适当的内存块,即使列表中的节点在堆内可能相距很远.
Cra*_*son 13
您对阵列案例的理解大多是正确的.如果按顺序访问数组,许多处理器不仅会获取包含该元素的块,还会预取后续块以最小化等待缓存未命中所花费的周期.如果您使用的是Intel x86处理器,可以在Intel x86优化手册中找到有关此内容的详细信息.此外,如果数组元素足够小,则加载包含元素的块意味着下一个元素可能位于同一个块中.
不幸的是,对于链表,从处理器的角度来看,负载模式是不可预测的.在地址X处加载元素时,不知道下一个地址是(X + 8)的内容.
作为一个具体的例子,顺序数组访问的加载地址序列是好的和可预测的.例如,1000,1016,1032,1064等.
对于链表,它看起来像:1000,3048,5040,7888等.很难预测下一个地址.
| 归档时间： |
|
| 查看次数： |
7574 次 |
| 最近记录： |