为何std::list<T>比std::vector<T*>慢这么多？

先明确测试背景：

• 测试内容：对比不同容器的迭代求和性能，基准为std::vector<int>，测试对象包括std::vector<Foo>、std::vector<Foo*>、std::list<Foo>及自定义基础链表
• Foo结构体定义（刚好占一个64字节缓存行）：

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

性能差距的核心原因在于缓存局部性和CPU的预取机制，两者在连续存储与离散存储的容器上表现天差地别：

• 指针存储的连续性决定缓存效率
  std::vector<Foo*>的指针是连续排布在内存中的，CPU加载缓存行时，一次就能把多个指针（比如64字节缓存行可容纳8个64位指针）存入L1缓存。后续迭代时，下一个指针直接从缓存读取，几乎零延迟。
  而链表的节点是在堆上离散分配的，每个节点的next指针地址完全随机。CPU每次读取下一个指针时，几乎都会触发缓存 miss，不得不从内存甚至磁盘加载数据——这部分延迟比缓存访问高几个数量级。

• 预取机制的作用差异
  CPU的预取器会根据内存访问的规律提前加载数据。std::vector<Foo*>的连续指针模式让预取器可以轻松预测后续指针的位置，提前把它们加载到缓存里，甚至能提前加载指针指向的Foo对象。
  但链表的节点地址毫无规律，预取器完全无法预测下一个节点的位置，根本没法提前加载数据，每一步迭代都要等待内存响应。

• 额外的内存访问开销
  链表迭代时，每一步要先读取当前节点的next指针，再跳转到下一个节点，相当于多了一次内存访问；而std::vector<Foo*>迭代时，只需要按顺序读取连续的指针数组，再访问对应Foo的value，内存访问路径更简洁高效。

补充一点：你会看到std::vector<Foo>的性能比vector<Foo*>略差，这是因为vector<Foo>每次读取的是64字节的完整Foo对象，但只用到其中4字节的value，缓存利用率极低；而vector<Foo*>虽然要做两次内存访问（读指针+读value），但指针的连续存储让第一次访问的缓存效率拉满，整体反而更快。

内容的提问来源于stack exchange，提问作者cmourglia