链表与数组的遍历效率比较

Question

我知道数组被分配为一个连续的内存块，因此我们可以通过计算与数组开始的字节/字偏移量来轻松访问其元素。

我知道链接列表遍历比数组遍历低效，因为缓存效率低下，在这种情况下，分支预测无法像对数组一样有效。然而，我也听说从一个数组元素迭代到下一个元素比访问链接列表中下一个元素的指针更快，因为我们使用偏移量访问数组的方式。

链表中指针的访问为什么比数组中偏移量的访问速度慢？

- screeb

Answer 1

缓存效率低下，分支预测无法良好工作

这是两个不同的问题。链表遭受缓存效率低下：

1. 节点通常不是按顺序连续分配的，这对于空间局部性很不利。您可以使用自定义分配器来避免这种情况。使用分代垃圾收集时，紧密地在时间上分配节点也倾向于将它们靠近空间，但在使用链表时，这可能不是一个非常普遍的情况。
2. 在节点中有一个指针（和潜在的其他垃圾，如对象头和填充）浪费空间。浪费大量空间本质上并不是非常糟糕的事情，但当浪费的空间被“接触”时，它会被加载到高速缓存中。这实际上在这里发生了：指向下一个节点的指针肯定是必需的，并且其他垃圾可能在同一个高速缓存行中，因此也被拉入其中。这浪费了缓存空间和带宽（包括更高级别的缓存和内存），这非常糟糕。

链表本质上不会遭受分支错误预测的问题。是的，如果您在链表上进行迭代，则最后一个分支（退出循环的分支）有相当大的机会被错误预测，但这并不特定于链表。

为什么链表中的指针访问比数组中的偏移量访问慢？

在性能和吞吐量方面，与在数组中计算元素的下一个地址相比，加载指针总体上会更慢。对于快速比较，在现代机器上典型的情况是，加载该指针需要大约4个周期（如果存在缓存未命中，则需要更长时间），可以每周期执行两次。将数组元素的大小添加到当前地址需要1个周期，可以每个周期执行4次，并且您（或编译器）可以使用一些巧妙的编码方法来重复使用循环计数器的增量。例如，也许你可以使用索引寻址及其增量的循环计数器（无论如何都会增加）作为索引，或者可以完全“窃取”循环计数器并将其增加元素大小（相应地调整循环结束），或者没有循环计数器并直接将当前地址与数组末尾后面的地址进行比较。编译器喜欢自动使用这些技巧。

事实上，这比听起来更糟糕，因为在链接列表中加载这些指针是完全串行的。是的，CPU可以每周期加载两个东西，但要知道下一个节点的地址需要4个周期，以便它可以开始加载下一个指针，所以实际上只能每4个周期找到一个节点的地址。计算数组元素的地址没有这样的问题，也许在计算连续地址之间会有1个延迟（因为实际循环不能比这更快），但这只会在展开循环时受到伤害，如果需要，可以通过添加k*sizeof(element)来计算向前k步元素的地址（因此可以独立地计算多个地址，编译器在展开循环时也这样做）。

在链接列表中每个“步骤”执行足够的工作，可以隐藏延迟问题。

- harold

Answer 2

访问指针需要额外的内存读取（与计算相比较慢）：要读取下一个元素的值，首先需要从内存中读取指针，然后需要读取所引用地址的内容。对于数组，对于值只需要进行一次内存读取（假设在迭代期间基地址保存在寄存器中）。

- Stefan Haustein