为什么在一个大的std :: list上迭代这么慢？

Question

正如标题所暗示的那样,我遇到了一个我的程序问题,我使用std :: list作为堆栈,并迭代列表中的所有元素.当名单变得非常大时,该计划花了太长时间.

有没有人对此有一个很好的解释？是一些堆栈/缓存行为？

(解决了问题,将列表更改为std :: vector和std :: deque(顺便说一下,这是一个惊人的数据结构),所有内容突然变得更快)

编辑:我不是一个傻瓜,我不访问列表中间的元素.我对列表做的唯一事情就是在结尾处开始删除/添加元素并迭代列表中的所有元素.而且我总是使用迭代器迭代列表.

Answer 1

列表具有可怕的(不存在的)缓存局部性.每个节点都是一个新的内存分配,可能在任何地方.因此,每次跟踪从一个节点到下一个节点的指针时,都会跳转到内存中新的,不相关的位置.是的,这会对性能造成很大影响.高速缓存未命中可以比高速缓存命中慢两个数量级.在vector或deque中,几乎每个访问都是缓存命中.向量是一个连续的内存块,因此迭代就可以达到你想要的速度.deque是几个较小的内存块,因此它会引入偶尔的缓存未命中,但它们仍然很少见,并且迭代仍然会非常快,因为您获得的主要是缓存命中.

列表几乎都是缓存未命中.性能会很糟糕.

实际上,从性能的角度来看,链表几乎不是正确的选择.

编辑:正如评论所指出的,列表的另一个问题是数据依赖性.现代CPU喜欢重叠操作.但是如果下一条指令取决于这一条的结果,它就不能这样做.

如果你在向量上迭代,那没问题.您可以计算下一个要动态读取的地址,而无需检入内存.如果您现在正在读取地址x,那么下一个元素将位于x + sizeof(T)T是元素类型的地址.因此,那里没有依赖关系,并且CPU可以立即开始加载下一个元素或后一个元素,同时仍处理早期元素.这样,当我们需要时,数据将为我们准备好,这进一步有助于掩盖访问RAM中数据的成本.

在列表中,我们需要遵循从节点i到节点的指针i+1,直到i+1已经加载,我们甚至不知道在哪里寻找i+2.我们有数据依赖性,因此CPU被迫一次读取一个节点,并且它无法提前开始读取未来的节点,因为它还不知道它们在哪里.

如果列表并非所有缓存未命中,这不会是一个大问题,但由于我们遇到了大量缓存未命中,因此这些延迟代价很高.