链表慢在每一次跳转

难度 ★★☆☆☆ · 前置:链表不是数组的替代品 | 一句话结论:链表慢在每一步都要先等上一跳回来才知道下一步去哪,指针本身不贵。

第一次跑,我把结论量反了

组里为一段遍历吵了两天,那时我入职刚满一年。有个同事把一份一千万条记录的切片换成了链表,理由写在 commit 里:中间插入是 O(1)。上线之后那个导出接口慢到没人愿意等,回滚,隔了两周又被提了一次,这次还附了一段从别处抄来的解释,说链表的插入删除都是常数时间。我在周会上说了一句慢在指针,被反问:指针一次就八个字节,能有多慢。会议室安静了两秒,我说不出下一句。散会之后我一直在想那句反问,它听着就不对,可我手上一个数字都没有。坐回工位我做的第一件事是翻上线前后的监控,两条曲线根本不在一个量级上,中间没改过数据量。

答不上来就得回去量。

机器还是上一组数那台,i9-14900HX,Go 1.27.2,windows/amd64,插着电,浏览器和编辑器都关了。节点长这样:

1
2
3
4
type node16 struct {
v int64
next *node16
}

一个 int64 加一个指针,16 字节,一行 64 字节的缓存正好装四个,一千万个铺下来一百六十兆。求和循环三行:

1
2
3
4
s := 0
for p := head; p != nil; p = p.next {
s += p.v
}

和塞进一个包级变量,免得编译器嫌这段没人要直接删掉。

第一版我干的事很朴素:一千万个节点老老实实建出来,拿固定种子洗一遍牌,再按洗过的顺序串成链。洗牌用的是 r.Shuffle,它交换的是 []node16 里那些结构体本身,我当时觉得这已经够随机了。

1
2
3
4
r.Shuffle(n, func(i, j int) { nodes[i], nodes[j] = nodes[j], nodes[i] })
for i := 0; i+1 < n; i++ {
nodes[i].next = &nodes[i+1]
}

三轮跑完,12591 微秒。对照组按地址顺序串接那条是 11913,两个数贴在一起。我在笔记本上写了一行:打散没用,指针不是瓶颈。

问题出在我打散的东西上。结构体在切片里换了槽位,节点地址跟着槽位走,可链条是按新下标顺序连的。遍历时每步跨 16 字节,一步都没迈出一行,还是顺着内存往下淌。我把判据定成了地址乱不乱,真正该看的是访问顺序乱不乱。

节点在切片里换了位置,链条却还沿着地址往下走。两版差不到百分之六,我却拿它当证据,认定打散不影响遍历。差的地方从头到尾不在内存里,在我写的那段循环里。

节点一个没挪,只把箭头重连了一遍

改法很短:

1
2
3
4
perm := r.Perm(n)
for i := 0; i+1 < n; i++ {
nodes[perm[i]].next = &nodes[perm[i+1]]
}

r.Perm(n) 给的是一个 0 到 n-1 的随机排列,我只拿它决定谁指向谁。一千万个节点一个都没挪过,地址还是原来的地址,变的只有 next 里存的那串值。

三轮:967816、970283、971324 微秒,九百七十毫秒。五个形态摆在一起看。

形态 三轮实测(µs)
切片顺序求和 3016 / 3350 / 3551
链表·按地址顺序串接 11584 / 12091 / 15324
数组·按下标乱序扫 13516 / 20950 / 21558
索引链·next 存 int32 16211 / 26261 / 33730
链表·指针打散 967816 / 970283 / 971324

五种形态的三轮实测,纵轴取对数,最下面一行比最上面一行高出三百多倍

最后一行跟第一行比,差三百多倍。3.0 是三轮里最小的那个数,我不拿它算三位有效数字,写三百多倍就够,再多一位也是假的。这张表的排法花了点心思:第三行是同一块连续数组按下标跳着扫,一次指针都不解;第四行把指针换成了 int32 下标;只有第一行是沿着直线走的。后面三节各拆其中一部分,拆到最后剩下的就是我们平常说的那句话。

两行代码复杂度一样,加法次数一样,求和循环一个字没改,变的只有一千万个 next 各自指向哪。同一个 O(n),只把箭头重连了一遍,差了三百多倍。

三百倍是从等待里长出来的

一行 64 字节,四个节点挤在里面。按地址顺序走的时候,每搬进来一行,后面三步都不用再碰内存,四个 next 全在这一行里躺着,读完这个节点的值顺手就把下一个地址拿到手了。打散以后不是这样:跳到第一个节点,读到它的 next,那个地址落在离这儿很远的一行上,只能等它被搬进来。搬进来之后这一行里另外三个节点用不上,它们的下一个在别的什么地方。同样一次搬运,顺序时服务四个节点,打散后只服务一个。还有一层更细的账:四个节点挤在同一行里,读完第一个的 v,它后面那三个的 next 也在同一块字节里,机器顺手就能一并取出来,连四次请求都省了;打散之后每跳一次都要重新问一次内存,上一行里那三个邻居白搬了,等下一次真碰见它们,那一行多半已经被挤出去,得从头再搬一遍。

一趟搬运服务四个还是只服务一个,上限摆在那里,值四倍。可这两条链用的是同一个结构体,16 字节,同样一千万个,求和循环都是从上一个文件里整段抄过去的,唯一动过的就是每个 next 里那个地址还挨不挨着。按四倍这个上限推,打散之后顶天慢四倍,实际差了八十多倍。多出来的那一大截不在搬运粒度上,粒度已经被这两条链按死了,动都没动过。我只能把它记成一笔还没还完的账,账上剩下的那一项是这样的:一趟搬运是自己挑好时机发出去的,还是被上一趟的结果掐着脖子才发得出去。

可同一条链,按地址串接是 11.6 到 15.3 ms,打散之后 970 ms,差了八十多倍。剩下的二十来倍在依赖上。顺着 p.next 走,下一步去哪儿这个信息不在 CPU 手里,它存在上一步刚读到的那块内存里。那个地址没回来之前,连下一步该访问哪儿都算不出来,更别说提前把请求发出去。顺序遍历没有这层债:下标是算出来的,第 i 个的地址跟第 i-1 个读到什么毫无关系,一大批访问可以同时在路上飞。指针追逐做不到这件事,一条链上永远只有一步在飞,前一步的答案不到,后一步连门都出不去。

一行搬四个省下的那点钱,跟这条串行链上等的时间比,是零头。

一行 64 字节装四个节点,顺序走一趟能服务四个,打散后一趟只服务一个

按地址顺序分配的那条链也在这串红灯里,只是没那么惨。它 11.6 到 15.3 ms,切片 3.0 到 3.5 ms,差四倍上下。一半来自字节数:一千万个节点一百六十兆,一千万个 int64 只有八十兆,搬的货翻倍。另一半来自依赖:切片的下标是算的,链表的得等上一跳把 next 递回来,机器没法提前几步一起读。货多一倍,路上还多一串红灯。

四倍是这么凑出来的,不是缓存偷懒。

一个指针都不用的版本,也慢了四五倍

上面那堆数里混着一件事:跳和指针一直没分开过。要分开,得找一个一次指针都不用的版本。

1
2
3
4
s := 0
for i := 0; i < n; i++ {
s += arr[perm[i]]
}

arr 是一千万个 int64 的连续数组,八十兆,一次 make 出来的。perm 还是那个随机排列。整个循环没有一次解引用,地址是算出来的:拿 perm[i] 乘 8,加上基址。

三轮:13516、20950、21558 微秒。

四倍到七倍。

一次指针都没解过,访问顺序一乱,时间还是翻了四五倍。它慢的地方跟链表一样,每一跳都落在没被预取到的地方,前面搬进来的整行整行作废。它没掉到九百毫秒,是因为这堆访问互相不欠着:perm[i] 顺着读出来,地址当场就算得出来,一大批访问能同时在路上,等的时间被叠在一起摊薄了。指针追逐把这些访问串成一条线,一次只有一步在飞,叠不起来。

贵的是跳,不是指针。指针本身很轻,八字节,读它一下跟读一个 int64 一下没区别。它干的事是把下一步去哪儿的答案锁进了上一次读取的结果里,一条链上谁也替不了谁。真要骂,骂的是这层锁,不是那八个字节。换句话讲,链表贵不在它的表示法,贵在它逼着你在时间上排成一列纵队:前一个节点不回来,后一个节点连地址都不知道,机器能做的只有等,而等这件事没有任何一种花活能绕过去。

同一个循环,把 perm 去掉、换回 i,时间立刻回到三毫秒。地址有没有规律,比地址用什么形式存着要紧得多。

节点撑满一行,两种排法都更慢

到这儿还有人不服:是不是节点太小,一行装四个,顺序走占了便宜。把节点撑到一行那么长再量一遍就清楚了。

1
2
3
4
5
type node64 struct {
v int64
_ [6]int64
next *node64
}

值加六个空位加指针,正好 64 字节,一行装一个,一千万个六百四十兆。按地址顺序串接,三轮 99836、111765 微秒,一百毫秒上下,比 16 字节那版的 11.6 到 15.3 ms 慢了七八倍。

字节数是四倍,时间是七八倍。多出来的那一截我没拆干净,一行装一个以后,每次搬运只用得着其中 16 字节,剩下 48 字节陪跑,这个账按理只值四倍,剩下那一倍多我到现在也说不准是预取更难跟还是地址翻译更吃力,只把它记成没量明白的部分。

打散的版本,1466623 到 1858538 微秒。

一秒半到一秒九。

把它跟 16 字节打散的九百七十毫秒摆一起:字节翻了四倍,时间只多了一倍上下。这条反过来把前面那句话坐实了,打散以后瓶颈是等,每一跳都要等一趟,一趟要多久跟节点是 16 字节还是 64 字节关系不大。多出来的那点,大概是六百四十兆比一百六十兆更难被缓冲和地址翻译兜住,这一条同样只是推断。

等是固定的,搬是按字节加的。

所以节点大小这件事,顺序走的时候值钱,打散以后不值钱。手上那条链要是注定了散着走,压缩节点尺寸救不了耗时,只能救内存占用。反过来,一条能顺序走的链,节点每胖一倍,账就再贵一截。

精度不够的时候,我只敢报区间

上面那些微秒,有一半我不敢信到最后一位。这台机器上 time.Now 走得很慢,半毫秒左右才动一格。我拿一段循环连读了 12826970 次,值只变了 133 次。相邻两次变化之间,最小 441600 纳秒,中位 555500,最大 1735300。

start := time.Now()
for time.Since(start) < 100*time.Millisecond {
    if now := time.Now().UnixNano(); now != last {
        last, changes = now, changes+1
    }
}
```这意味着什么,值得单独说一遍,因为它决定了我后面每一个数能报到哪一位。这台机器上 `time.Now` 一次读的粒度大约半毫秒,也就是说任何小于半毫秒的差别,用这个接口量出来都是噪声,最多只能拿最小值当个下界报。3.0 到 3.5 ms 那一组,三个数之间隔的距离还不到半格钟,我写 3016 微秒就是假精度,改成 3.0 ms 反而老实。九百七十毫秒那组跨了几千格,报到个位勉强有意义,意义也不大,换台机器全变。钟的刻度比要量的东西还粗,量出来的就是噪声。更早我吃过这个亏:固定三十轮量单次插入、单次删除,每一个都量出 0。这些操作不花时间是不可能的,它们的耗时整块落在两格钟之间,一格都没跳到。后来改成一个循环里重复做两百次,拿总时间除,才看见数。

现在报数的规矩是:能跨过几百格钟的量,报到毫秒;只跨几格的,写区间;一格都跨不过去的,直接写量不出来,别硬报。真要量单次的,把重复操作塞进循环再拿总数除,别用掐头去尾的 `time.Now`。

## 跳几次,跳多远

这套东西量完,改掉的不是知识,是习惯。现在拿到一段遍历,我先问三句:一共跳几次,每次跳多远,跳的时候有没有别的访问能一起在路上。

表里还有一行我没讲圆:`next` 存 int32 下标不存指针,三轮 16211、26261、33730 微秒。它比指针打散的九百七十毫秒差了将近三十倍,比数组乱序扫的十三到二十一毫秒只慢一点。按这个数,换小整数下标好像能把局面救回来。可这三轮之间差了一倍,我复现两遍也没把这笔账对上,所以只报数,不下结论。

能顺序分配就顺序分配。一千万个节点一个个 `new` 出来,地址撒得到处都是;顺序分配的链表至少让分配顺序和遍历顺序对上,这是唯一不用改数据结构就能拿到的好处。

真要用链表,就一次走完。同一条链扫两遍,第二遍基本等于重新等一遍,除非它短到能整个待在缓存里。节点超过一行的时候,把热字段挪到第一行里,别让一次内存访问只为读一个 int64 就整行搬进来。

那两条 commit 最后是同事自己回滚的,我没再说什么。我把周会上没答上来的那句话补成了一页笔记:链表慢在每一次跳转,一次跳转要等一趟内存回来才知道下一次往哪儿跳,指针只是把这串等待写进了内存里。

现在写遍历之前我会先做一件事:把要用的字段抠出来,先拿一个连续数组过一遍,过完再决定要不要碰那条链。抠不动的,比如节点里存着别人的指针、字段有的读有的不读,那就老老实实一次走完,别在链上来回扫。顺着的用它,要跳的先量。