为什么列表<T>比向量<T*>慢这么多？

Question

有一天，我正在玩这个快速台：https://quick-bench.com/q/fwF5nkc4ORmYwSXSoVy2d-ekN5U

基本上，代码只是测量不同情况下迭代和求和所需的时间：

std::vector<int>

（参考点）、

std::vector<Foo>

、

std::vector<Foo*>

、

std::list<Foo>

以及列表的自定义基本实现。

Foo

结构只是开头的一个值，然后是一些垃圾，使其达到缓存行的大小。

struct Foo {
  int value;
  int garbage[15];
};

结果如下所示：

虽然我理解参考案例（

std::vector<int>

）和其他案例之间的差异，但我对向量std::list...）之间的差异与

std::vector<Foo*>

案例相比如此缓慢感到有点惊讶。

为什么跟随随机指针与取消引用相同的随机指针相比要慢得多，主要区别（我认为）是地址连续存储在内存中（但地址本身应该与列表地址一样随机）？

Answer 1

为什么跟随随机指针要慢得多

因为访问随机分布的内存是计算机程序中最慢的事情。

仅此而已；你的处理器获得一个内存地址，需要获取该内存，而获取内存需要花费大量时间。由于列表的顺序性质，当当前节点仍在获取时，CPU 无法根据下一个节点执行任何操作，因此链表数据结构在内存/缓存方面非常接近最坏情况的访问范例带宽，以及 CPU 管道。

主要区别（我认为）是地址连续存储在内存中

如果下一步并不本质上依赖于前一步的结果，CPU（以及编译器）可以重新排序。因此，您的 CPU 可以通过在等待第一个内存位置被检索时开始查找下一个内存位置（实际上可能是多个）来隐藏大量内存延迟。

对于列表，这是不可能的，因为在获取当前请求的内存之前，不知道要获取的下一个内存位置，并且知道指向下一个节点的指针。

原始的

std::vector<int>

当然没有这样的问题，并且由于值在内存中是连续的，您还可以最小化内存带宽（您只获取实际需要的数据，并且您通常使用每个缓存行的所有内容） 64 B，这是获取内存的粒度）。该提取的优点是直接按正确的顺序进行提取：这使得编译器可以直接将内存提取到 SIMD 寄存器中，一次执行多个加法（如果您的处理器有 AVX2，则可以进行 8 个加法）一条指令，使用 AVX512，每条指令最多 16 个加法（如果您有一台 x86 PC，您几乎肯定有 AVX2，如果您有一个现代 AMD CPU，AVX512 将非常快）。

为什么你的自定义列表比 std::list 更快，我真的不知道，但我的猜测是额外的健全性检查。您可能想要构建（使用调试符号，但经过优化）在计算机上本地运行代码并对其进行分析（例如，如果您使用的是 Linux，则使用

perf

）。