std::list与std::vector的迭代

Question

据说遍历向量（即读取所有元素）比遍历链表更快，因为缓存被优化了。

是否有任何资源可以量化它对性能的影响？

此外，使用自定义的链接列表会更好，其中元素将被预先分配，以便它们在内存中连续吗？

这背后的想法是我想按一定顺序存储元素，这个顺序不会改变。我仍然需要能够在运行时快速地在中间插入一些元素，但是大多数元素仍然是连续的，因为顺序不会改变。

元素连续是否对缓存产生影响，还是因为我仍将调用list_element->next而不是++list_element，因此没有改进呢？

- 0x26res

---

还有，使用一个自定义的链表，元素预先分配，这样它们在内存中是连续的会更好吗？你的意思是向量吗？ - Luchian Grigore

std::list 的主要要求是从列表的任何位置插入和删除单个元素的时间都是常量级别。这与元素在内存中连续的要求不兼容。 - juanchopanza

首先，你是否确定你的代码中的这部分需要优化？ - Paul Manta

@LuchianGrigore 不是的。他说的是让所有列表节点都分配在一个未碎片化的内存块中。它们仍然通过“next”和“prev”指针相互引用。 - Paul Manta

@juanchopanza：他并不期望所有元素都是连续的，只是大多数元素是连续的，偶尔插入的元素会离开顺序容器并回到其中。考虑一个向量，其中元素N指向向量外部的一个元素，该元素又指回元素N+1。整个容器不是连续的，但范围[0..N]和[N..M]是连续的（N是索引向量而不是列表）。这种设计可能实际上是有意义的，但我很想知道对性能的实际影响... - David Rodríguez - dribeas

Answer 1

向量和列表的主要区别在于，向量中的元素是在预分配的缓冲区内依次构建的，而列表中的元素是逐个构建的。 因此，向量中的元素被保证占用连续的存储空间，而列表中的元素（除非有一些特定情况，比如自定义分配器可以处理这种情况）并没有被保证，它们可能会稀疏地分布在内存中。

现在，由于处理器操作的是高速缓存（可能比主 RAM 快1000倍），它重新映射了整个主内存的页面，如果元素是连续的，则极有可能它们将占用同一个存储页面，并且在迭代开始时一起移动到高速缓存中。随着迭代的进行，所有操作都发生在高速缓存中，无需进一步移动数据或访问较慢的RAM。

对于列表，由于元素随处稀疏，"去下一个"意味着必须引用可能不在其前面的同一存储页面上的地址，因此，在每个迭代步骤中需要更新高速缓存，每次迭代都会访问较慢的RAM。

性能差异很大程度上取决于处理器以及用于主 RAM 和高速缓存的内存类型，以及std::allocator（最终是operator new和malloc）的实现方式，因此无法给出通用数字。 （注：大的差异意味着RAM相对于高速缓存不好，但也可能意味着列表的实现不好）。

- Emilio Garavaglia

Answer 2

由于数据结构的紧凑表示，缓存一致性带来的效率提升可能非常显著。在向量和列表进行比较时，紧凑表示不仅对读取更好，甚至对于插入（向向量中移动元素）也可以更好，对于某些特定架构，最多可达500K个元素的顺序，如Bjarne Stroustrup在本文的图3中所示。

http://www2.research.att.com/~bs/Computer-Jan12.pdf

（发布者网站：http://www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353）

我认为，如果这对你的程序是一个关键因素，你应该在你的架构上进行性能分析。

- devil

Answer 3

我不确定我是否能够正确解释，但这是我的观点（我正在考虑下面翻译机器指令的思路）：

向量迭代器（连续内存）： 当您增加向量迭代器时，迭代器值只需添加对象的大小（在编译时已知）即可指向下一个对象。在大多数 CPU 中，这最多只需要一到三个指令。

列表迭代器（链表http://www.sgi.com/tech/stl/List.html）： 当您增加列表迭代器（所指对象）时，通过将某些数字添加到所指对象的基础上来定位前向链接的位置，然后将其作为迭代器的新值加载。这需要多次访问内存，比向量迭代操作慢。

- ManiP