链接列表与数组遍历效率

Question

我知道一个数组被分配为一个连续的内存块,因此我们可以通过非常容易地计算从数组开头的字节/字偏移来访问它的元素.

我知道链接列表遍历的效率低于数组遍历,因为缓存效率低,其中分支预测不会像对阵列那样有效.但是,我还听说,由于我们使用偏移量访问数组的方式,从数组的一个元素到下一个元素的迭代比访问链表中下一个元素的指针更快.

如何在链表中访问指针比数组中的偏移访问慢？

Answer 1

缓存效率低下,分支预测不能很好地工作

这些是不同的东西.链接列表遭受缓存无效:

1. 节点通常不一定按顺序分配,这对于空间局部性是不利的.您有时可以避免这种情况,例如使用自定义分配器.使用分代垃圾收集,及时将节点紧密地分配在一起也会使它们在空间中靠得很近,但这在使用链表时实际上可能并不常见.
2. 在节点中有一个指针(以及可能的其他垃圾,如对象标题和填充)会浪费空间.浪费一大堆空间本身并不是非常糟糕,但是当触摸浪费的空间时会将其加载到缓存中.这实际上发生在这里:确实需要指向下一个节点的指针,而另一个垃圾可能在同一个缓存行中,因此它也会被拉入.这会浪费缓存空间和带宽(包括更高级别的缓存和内存),这非常糟糕.

链接列表本身并没有真正受到分支错误预测的影响.是的,如果你迭代一个,最后一个分支(退出循环的分支)有很大的机会被错误预测,但这不是链接列表特有的.

如何在链表中访问指针比数组中的偏移访问慢？

加载指针在所有的比在阵列中计算一个元素的下一个地址比较慢,无论是在等待时间方面和在吞吐量方面.为了快速比较,在现代机器上典型的是加载该点需要大约4个周期(最好!如果有高速缓存未命中,则需要更长时间)并且每个周期可以完成两次.将数组元素的大小添加到当前地址需要1个周期,每个周期可以完成4次,并且您(或编译器)可以通过一些巧妙的编码重新使用循环计数器的增量.例如,也许您可​​以使用索引寻址和循环计数器(无论如何递增)作为索引,或者您可以完全"窃取"循环计数器并将其增加一个元素的大小(相应地缩放循环结束),或者没有循环计数器,直接将当前地址与数组末尾的地址进行比较.编译器喜欢自动使用这些技巧.

它实际上比声音更糟糕,因为在链表中加载这些指针是完全串行的.是的,CPU可以在每个周期加载两个东西,但它需要4个周期,直到它知道下一个节点的位置,以便它可以开始加载下一个指针,所以实际上它每隔4个周期只能找到一个节点的地址.计算数组元素的地址没有这样的问题,也许在连续地址的计算之间会有1的延迟,但是(因为实际的循环不能比任何时候更快)只会在循环展开时受到伤害,并且如果必要的话k元素的k*sizeof(element)地址可以通过添加来计算(因此可以独立地计算多个地址,并且编译器在它们展开循环时也会这样做).

通过链表每个"步骤"执行足够的工作可以隐藏延迟问题.