数组和链表谁快?我用1000万条数据实测3遍,链表慢了114倍

上周三晚上快11点,组里刚转正的小李发消息问我:为什么咱们把消息队列从链表换成环形缓冲区之后,P99 从 340ms 掉到 21ms?业务逻辑一行没动。我说你别急,这事我 2019 年踩过,当时做日志聚合服务,被链表坑得半夜爬起来改代码。

后来我干脆在自己机器上把这事从头测了一遍。Apple M1 Pro,Go 1.21.5,1000 万个元素,同样的遍历逻辑,只换底层容器,每项跑 5 次取中位数。结果有点难看:

差 114 倍。这不是我机器的锅,2014 年 Chandler Carruth 在 CppCon 讲 Efficiency with Algorithms, Performance with Data Structures 时就下过一个暴论:链表几乎在所有场景下都是最差的选择。Stroustrup 2012 年在 GoingNative 上也演示过,插入随机整数然后排序删除,vector 比 list 快得多。可教科书还在教你链表插入是 O(1)。

差的不是算法,是物理

很多人以为这是汇编级别的微优化,不是。这是内存布局问题,严谨点说,是 CPU 取数据的最小单位问题。

CPU 从主存拿数据,一次拿的不是 8 字节的 int64,而是一条 64 字节的缓存行。数组里 8 个 int64 挨在一起,一次搬运全拿到,后面 7 个直接命中 L1。L1 命中大概 4 个周期,M1 上差不多 1.3ns。

链表呢?每个节点单独 malloc,16 字节(int64 值 + 8 字节指针),分配器把它们丢在堆里各个角落。你每跳一次指针,基本就是一次缓存行搬运,而这次搬运只用到了 16 字节里的 8 字节。剩下的 56 字节全是浪费。

更要命的是延迟。M1 上主存延迟大约 90 到 110ns,跟 L1 的 1.3ns 差了七八十倍。1000 万次随机指针跳转,即使有 30% 命中缓存,剩下的 700 万次也是实打实的访存。812ms 除以 1000 万,每次 81ns,跟主存延迟几乎对上了,说明确实在疯狂打内存。

还有个东西叫硬件预取器。它能识别 stride-1 这种连续访问模式,提前把后面十几个缓存行拉到 L2 或者 L3。数组遍历能吃到这个红利,链表这种地址跳来跳去的模式,预取器基本放弃治疗。

链表的 O(1) 是断章取义的

我倒不是说教科书错了,是它少写了前提。

链表插入 O(1) 的正确表述是:在已经持有目标节点指针的前提下,插入是 O(1)。可问题是,你哪来的指针?

如果你要往第 k 个位置插入,得先从头走 k 步找位置。这趟查找是 O(n),而且每走一步几乎一次 cache miss。相比之下,数组插入虽然要 memmove 搬后半段,但 memmove 是连续地址顺序写,带宽能跑到 20GB/s 以上,M1 上实测能到 30GB/s 左右。

我做过一个粗糙的对比:100 万个元素,在中间位置插入。数组 memmove 大概 2 到 3ms,链表找位置加插入要 90ms 往上。差了 30 多倍。所以那个 O(1) 在真实代码里,大部分时候是拿不到的。

例外确实有:你已经在遍历链表,手里正攒着当前节点指针,顺手摘掉它。Linux 内核的 list_head 就是干这个的,进程调度队列里频繁摘节点,场景高度匹配。但这是特例,不是通用规则。

真要写链表,用侵入式或者数组模拟

我给你三个我实际用过的方案,按上手难度排序。

一、侵入式链表(intrusive list)。 节点结构体直接嵌进业务对象里,不给它单独分配内存。C 里长这样:

struct task {
    int id;
    struct list_head node;   // 嵌进来,不是指向外面
};

这样从 node 反推 task 只需要一次固定偏移的地址运算,不用额外 malloc,少一次指针跳转,少一次分配器开销。Linux 的 list_entry 宏就是这套路。Go 里可以做类似的事,把 next/prev 索引直接放进结构体。

二、数组模拟链表。 开一个大 slice,节点存下标而不是指针。LeetCode 146 LRU 缓存的标准解法就是这个思路。下标访问是连续内存,预取器照样吃得开,还省了 GC 扫描指针的开销。需要删除就打个标记位,定期 compact。

三、分块数组 / 环形缓冲。 定长队列直接上 ring buffer,读写指针取模。需要中间插入的话用 chunked array,每块 512 字节或者 4KB,块内连续、块间链表。C++ 的 std::deque 就是这个结构,它的 push_front 在多数场景下比 std::list 快。Redis 的 quicklist 也是 block 化的双向链表,一个节点装几十个元素,就是为了摊薄指针跳转的成本。

我自己的 30 秒决策清单

遇到选容器的时候,我现在基本按这个顺序过一遍:

1. 元素大小小于等于 128 字节,且不需要中间频繁插入,上数组。别犹豫。
2. 只在两端增删,环形缓冲或者 deque,不要 list。
3. 需要按 key 查找还要有序,跳表或者 B+ 树,自己手搓链表是给自己找事。Redis zset 用跳表不是没道理的。
4. 确实需要频繁从中间摘节点,而且手里能长期持有节点引用,才考虑侵入式链表。
5. 任何情况下,先用数组写一版,压测出瓶颈了再换。我见过太多人一上来就 list,结果 profile 出来一半时间在追指针。

最后补一句面试相关的。如果面试官问你链表插入的时间复杂度,老老实实答 O(1),然后加一句前提是已经持有目标节点指针。这不叫抬杠,叫严谨。真有面试官因为这个扣你分,那这公司不去也罢。