链表为什么比数组慢？一次真实的压测复盘，从 CPU 缓存行说到 B+ 树

起因

去年帮朋友看一套行情回放的工具，卡得莫名其妙。回放 500 万条逐笔委托，内存里维护一个按价格排序的订单簿，用的是 std::map<double, std::list<Order>>，跑一次要一分半。我看了一眼，觉得这结构挺标准的，很多教程就这么写。我说先别动逻辑，把 std::list 换成 std::vector 试试。

跑完 12 秒。

不是快了 12%，是从 90 秒降到 12 秒，7 倍多。我当时有点懵，因为这两个容器在大 O 复杂度上明明是一样的——只要拿到迭代器，插入删除都是 O(1)，遍历都是 O(n)。凭啥差这么多。

后来花了两个晚上把这个事想明白，顺手写了个小压测脚本。结论比我想的狠：在现代 CPU 上，链表那点理论优势基本是假的。

缓存行才是真正的裁判

现代 x86 的 cache line 是 64 字节，这个数字十几年没变过。L1 一般 32KB，L2 每核 256KB 到 1MB，L3 几 MB 到几十 MB。延迟大致是 L1 命中 4 到 5 个周期，L2 十二三个，L3 三四十，一旦掉到主存就是 200 到 300 个周期。换算成 3GHz 的 CPU，一次 cache miss 够你算一百条简单指令。

关键在于 CPU 是按 cache line 拿数据的，不是按你需要的那 4 个字节。一个 vector<int>，64 字节能装 16 个元素，你访问 a[0] 的时候 a[1] 到 a[15] 已经躺在 L1 里了。而 list<int> 的一个节点，64 位机器上大概 24 字节（两个指针加数据再加对齐），一个 cache line 只装得下两三个，而且这几个节点在内存里还是东一个西一个——malloc 从来不保证相邻两次分配挨着。

所以遍历 1000 万个 int，vector 大概需要 1000万×4÷64 ≈ 62.5 万次内存事务，list 需要 1000 万次左右。差 16 倍，实测往往差得更多，因为 TLB 也扛不住这种乱跳。

还有个因素是硬件预取器。Intel 和 AMD 的顺序预取器对步长固定的访问极其敏感，你顺序走数组，它能把后面几 KB 提前拉进 L2。链表这种指针追逐，预取器基本瞎了，它没法预测下一个地址在哪。

已经有人测过，而且说得很直白

Bjarne Stroustrup 在 2012 年 GoingNative 大会上做过一个演示：往有序容器里插入并保持有序，vector 用 lower_bound 找位置再 insert，list 做线性查找。结果是 vector 全面胜出，连中间插入 O(n) 这个劣势都被 memmove 的速度和缓存友好性吃掉了。memmove 是高度优化的，一次挪几 MB 比你在链上跳几百次快得多。

Chandler Carruth 在 CppCon 2014 那个叫《Efficiency with Algorithms, Performance with Data Structures》的演讲里更直接，说链表是性能杀手，苹果 libc++ 团队内部基本把 std::list 当禁用品。

我自己机器上（R7 5800X，DDR4-3600，单线程）顺序遍历 1000 万个 int 的结果：

• vector<int>：约 12 ms
• deque<int>：约 26 ms
• vector<unique_ptr<int>>：约 150 ms
• list<int>：约 480 ms

注意倒数第二行。如果你真需要指针语义（多态、共享所有权），用 vector<unique_ptr<T>>，元素本体还是连续存着的，比 list<T*> 快三倍以上。这个替代方案知道的人不多，但改造成本极低。

做存储的人早就不信这套了

有意思的是，搞数据库的人几十年前就绕开了链表和二叉平衡树。MySQL InnoDB 默认页大小 16KB，一个非叶子节点存的是一条条 (key, 页号) 对。主键是 bigint 的话，8 字节 key 加 6 字节页号，算上记录头，16KB 大概能放 1170 个指针。

三层 B+ 树能挂 1170 × 1170 ≈ 136 万个叶子页，每页 16KB，假设一行 1KB 就是 16 行，那大概能存 2000 万行。查一条记录最多 3 次磁盘 IO，而且根节点和第二层常年驻留 buffer pool，实际往往只剩 1 次。

换成红黑树呢？树高上界是 2log₂(N)，N 取 2000 万，log₂ 约 24.3，树高接近 49。最坏情况 49 次随机 IO。这不是差几倍，是差能不能用的问题。

Redis 的 zset 选了跳表而不是红黑树，antirez 在 GitHub 上解释过：范围查询方便（底层挂了个双向链表）、实现比平衡树简单得多、并发场景好改、内存占用也差不多。跳表期望高度是 log_(1/p)(N)，Redis 里 p 取 0.25，2000 万元素期望高度大概 12 层，最大层数硬编码限制在 32。

你看，这两个选择表面上是链表和树的取舍，实际上都在回答同一个问题：怎么让一次内存访问尽可能多地带回有用的东西。

那链表到底还有没有用

有，但场景比教科书写的窄得多。我自己总结下来大概这几类：

1. 单个节点本身很大，几百字节到几 KB，16 字节的指针开销被摊薄了。
2. 你长期持有迭代器，插入删除是纯 O(1)，且插入频率远高于遍历。LRU 缓存是典型，但工业实现也基本都是哈希表加侵入式双向链表，节点从内存池预分配。
3. 结构本身就是链式的，比如无锁队列里的 Michael-Scott 算法，还有 Linux 内核那个 list_head。
4. 需要 O(1) 拼接（splice），且规模不大。

Linux 内核的 list_head 设计我一直觉得挺妙——它不是节点里装数据，而是数据里嵌节点。一个结构体能同时挂在好几条链表上，内存由调用方负责，没有额外的 malloc。这套思路后来被无数高性能 C++ 代码抄来抄去。

我的实践建议很土：先用 vector，压测，真不行再换。换的时候优先考虑 deque、vector<unique_ptr<T>>、boost::container::flat_map 这种连续或半连续结构，别一上来就 std::list。

一个我还没完全搞清的细节

GCC 的 libstdc++ 里，std::list 的节点是 _List_node<T>，内容是 _List_node_base（前后两个指针）加上数据，sizeof 一般 24 字节（对齐后）。你用 std::list<int> 开 -O2，编译器也没法帮你把节点合并起来，分配器是自己的，一次 malloc 一个节点。

我试过换成 pool allocator，cache miss 大概从九成降到六成，性能提升差不多一倍，但还是打不过 vector。改善的只是同一批节点的局部性，跨节点跳转该 miss 还是 miss。

这块我没测得很细，有更细的数据欢迎拍我。