为什么在一个大的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被迫一次读取一个节点，并且它不能提前开始读取未来的节点，因为它还不知道它们在哪里。

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

Answer 2

这是由于您在使用列表时遇到大量缓存未命中。使用向量，周围的元素存储在处理器高速缓存中。

Answer 3

请查看以下 stackoverflow主题。

Answer 4

是缓存问题：向量中的所有数据都存储在一个连续的块中，每个列表元素都是单独分配的，可能恰好存储在相当随机的内存位置，这导致更多缓存未命中。但是，我打赌你会遇到其他答案中描述的问题之一。

Answer 5

简单的答案是因为对向量的迭代根本不是迭代，它只是从数组的基础开始并逐个读取元素。

我看到它标记为C ++，而不是C，但由于它们在封面下做同样的事情，所以值得指出你可以通过任意大量地分配数组到数组的开头和结尾，并且realloc（）当你用完房间时，在2个伴随阵列之间进行和memmove（）。很快。

向数组的开头添加元素的技巧是通过在开始时将指针前进到数组中来偏置数组的逻辑起点，然后在前面添加元素时将其备份。 （也是实现堆栈的方式）

以完全相同的方式，可以使C支持负下标。

C ++使用向量STL类为您完成所有这些，但仍然值得记住正在进行的内容。

Answer 6

[编辑：我纠正了。 std :: list没有operator []。遗憾。]

很难从你的描述中看出来，但我怀疑你是在试图随机访问这些项目（即通过索引）：

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

而不是使用迭代器：

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

两者都是“载体”。 ＆安培; ＆QUOT;双端队列＆QUOT;擅长随机访问，因此要么对这些类型都适当地执行---两种情况下都是O（1）。但是“列表”不善于随机访问。按索引访问列表需要O（n ^ 2）时间，而使用迭代器则需要O（1）。