Go 的排序换了三次实现

难度 ★☆☆☆☆ · 前置:删中间一个元素要挪多少人 | 一句话结论:选排序先看数据会不会重复、比较函数贵不贵,算法名字反而排在最后。

四段基准跑完,终端第一行写着 3.4 ms,是 sort.Ints 排一百万个随机 int 的耗时。我盯着这个数看了两秒,把它连同底下三行一起抄进笔记,还用红笔圈了一下。闭包那版七毫秒出头,算下来慢两倍,正好对上我脑子里的印象:接口和反射贵,能不用就不用。

(那天我还挺高兴,觉得自己终于学会量东西了。)

我是去年六月入的行,到这会儿七个月,写的代码一半跟数据结构打交道,一半跟测试打交道。第一次写基准是八月,为了证明一段 map 遍历比切片慢,结论是对的,过程一塌糊涂:数据建在计时区里,跑五遍取最小值,取到的其实是分配器的脾气。后来写了别猜,量一遍,把那次翻车拆开讲过一遍。我当时以为自己看懂了,其实只记住一句话,计时器要在数据躺好之后按下去。

别的都没记住。

我排的是一百万个零

第二天早上我把这段基准又跑了一遍,想换个随机种子。跑之前顺手点开 cmp_test.go,看见 init() 里那两行:data = make([]int, n),紧接着 copy(data, src)。src 是另一个文件里的包级变量。我第一反应是这行写得挺省事,第二反应才是它可能还没建好。

Go 的 init() 按文件名的字母序执行。cmp_test.go 排在 sort_test.go 前面,拷贝那段 init 先跑,源切片还是 nil,copy 从 nil 里搬了零个元素,data 于是一百万个位置上全是零,一个字节都没动过。基准跑得很认真,计时器按得也对,-count=3 老老实实跑了三轮,每一轮排的都是同一批零。更难受的是它给的结论看起来特别合理:3.4 ms,比闭包快两倍,跟我心里预设的方向一模一样。一个合我心意的数字,比一个离谱的数字危险得多,因为后者我还会回头看一遍。

零个元素被搬过来。

后面这一截是我过了一晚上才想明白的。pdqsort 碰到全等值的输入有一条专门的快路,zsortfunc.go 第 108 行:if a > 0 && !data.Less(a-1, pivot)。上一个 pivot 左边那个元素都不比它小,说明这一段很可能全是重复值,于是改用 partitionEqual_func,把等于 pivot 的一整段一次切出去。切完小的全在左边、大的全在右边、等于的那一整段原地不动,递归只剩一边,宽度直接砍掉一大块。一百万个零就是这么几毫秒排完的,连 limit 的门槛都没碰到。我原先以为快排的常数只跟实现写得好不好有关,这件事让我明白常数跟输入的形状绑得更紧。

数字本身也印证这件事。同样一百万个 int,只有一百个不同值的时候是 63.7 ms,已经比随机的 186.2 ms 快出将近三倍。

全等值比这还极端。

我把数据改到 sync.Once 里懒建,第一次调用时才填,跟文件执行顺序彻底脱钩。重跑,sort.Ints 180.6 ms,sort.Slice 276.9 ms,1.6 倍。

基准测试最贵的一次错误不是量错,是量的东西根本不是你以为的那个。我把它抄在了显示器边上。

同一批数据,四种写法

改完之后重跑的那一版,一百万个随机 int,-count=3,机器是 i9-14900HX,32 个逻辑核,Go 1.27.2 windows/amd64。数据建一次、排十遍,谁也不许碰包级变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var (
dataOnce sync.Once
data []int
)

func loadData() []int {
dataOnce.Do(func() {
r := rand.New(rand.NewSource(7))
data = make([]int, 1_000_000)
for i := range data {
data[i] = r.Intn(1_000_000)
}
})
out := make([]int, len(data))
copy(out, data)
return out
}

func BenchmarkSortInts(b *testing.B) {
for i := 0; i < b.N; i++ {
sort.Ints(loadData())
}
}

四次调用的结果摆在一起是这样:

写法 三次 相对 sort.Ints 每次分配
sort.Ints 180.6 / 188.5 / 180.7 ms 1.00× 0 次
slices.Sort 181.9 / 198.4 / 196.3 ms 1.01× 0 次
sort.Slice + 闭包 276.9 ~ 328.1 ms 1.6 ~ 1.8× 2 次,56 B
sort.SliceStable + 闭包 1011 ~ 1110 ms 5.6 ~ 6.1× 2 次,56 B

第一行和第二行其实是同一个函数。sort.Ints 在 GOROOT 里只有一行,sort.go 第 170 行:func Ints(x []int) { slices.Sort(x) }。180.6 和 181.9 中间那 1.3 毫秒不用解释,slices.Sort 那三次是 181.9、198.4、196.3,同一台机器、同一段代码、同一个二进制,抖动量级就有这么大。这也是我后来非坚持 -count=3 不可的原因,单跑一次太容易把噪声当结论。

真正要解释的是下面两行。

sort.Slice 1.6 到 1.8 倍,sort.SliceStable 5.6 到 6.1 倍,两个都多两次分配、共 56 字节。56 字节这个数看着扎眼,可它跟元素个数无关,排一百万个元素也是这两次。一次分配的价钱在百纳秒量级,两次加起来塞不进 96 毫秒的差距里。

钱不在分配上。

一百万个 int 排一遍大约两千万次比较,1e6 乘 log2(1e6),这个数是算出来的。sort.Slice 比 sort.Ints 多出来的那 96 毫秒,摊到每次比较上是四五纳秒。四五纳秒差不多正是一次不能内联的函数调用的价钱。1.6 倍的全部来源就在这儿。

四种调用方式的中位耗时与分配次数,后两行把横轴拉长了一截

四五纳秒,也就这么多。

一次比较要多绕两圈

sort.Slice 的签名是 less func(i, j int) bool,你传进去的闭包在编译期只是一个函数值,调用点上看得见指针,看不见函数体,内联断在这儿。更贵的是换位:它先调 reflectlite.Swapper(x),拿到一个 func(i, j int),内部按类型分支决定这一次要挪几个字节、怎么挪。排序里换位的次数跟比较是同一个量级,两千万次比较配几百万次换位,每一次都得走一遍这个分支。这两笔加起来,才是我当初想当然的接口和反射贵的真实位置,贵在每一次调用,不在建对象那一次。

比较一次,换位一次。

slices.Sort 那边不是这样。pdqsortOrdered 是对 []E 的泛型实例化,E 在编译期就定下来了,比较那行是个 <,换位就是两次赋值,元素大小和下标乘法都是常量。两边的算法一模一样,连 12 这个门槛都一样,差的全在每一趟比较和每一次换位上。

所以稳定版那 5.6 到 6.1 倍,也不能全记在闭包头上。SliceStable 走的是另一条路,stable_func,先把每 20 个元素插排一遍,再两两归并,归并十几轮。它一分额外内存都没花,这一点跟我原先的猜测相反,我以为稳定版总得开一块临时数组。

排好的数据比随机的快八十倍

第二组只动输入,不动调用方式,全部是 sort.Ints,一百万个 int。

输入 中位耗时
一百万个随机 int 186.2 ms
已经排好序 2.3 ms
完全倒序 3.3 ms
只有一百个不同值 63.7 ms

第一行是基准,186.2 ms。第二行 2.3 ms,输入本来就有序,partialInsertionSort_func 从头扫一遍,没有一对相邻元素是逆序的,直接 return true,整趟结束。它的 maxSteps 是 5,最多修五次,shortestShifting 是 50,长度短于 50 个元素连修都懒得修。这套东西只对基本有序的段有效,一百万个零那种全等值轮不到它,因为段早被 partitionEqual 切没了。八十倍这个数我第一次看到时以为是跑错了,重跑三次都是两毫秒出头。

扫一遍就完事。

第三行更别扭,完全倒序只要 3.3 ms。choosePivot_func 挑 pivot 的时候顺手数了一下比较里发生了多少次交换,全都得换,就说明这一段是严格递减的,返回 decreasingHint。拿到这个信号,pdqsort_func 直接 reverseRange_func 把整段反过来,再把 pivot 的下标换算成反转之后的位置,接着按升序往下走。反转一百万个 int 是五十万次交换,排好的那次是 2.3 ms,比它多出来的 1 毫秒大概就是这五十万次交换的价钱。倒序比随机快五十多倍,这条规律在教材里几乎没人写。

输入的样子,比调用方式值钱。

一百万个 int 在四种输入下的中位耗时

这几行放在一起,能看出 pdqsort 的设计取向。它不假设输入是随机的。 教科书写快排总要补一句平均 O(n log n),平均是对随机输入取的,而工程里的数据大多不随机。从库里按主键捞出来的是有序的,从上游有序结果拼出来的还是有序的,倒序更是常见,按时间倒着取回来再塞进要正序显示的地方,这种代码每个项目里都有几处。既然输入不随机,把判断做进算法里就比要求调用方先排序划算得多。

不随机才是常态。

十二个元素以下直接插入排序

主干在这儿,摘自 $(go env GOROOT)/src/sort/zsortfunc.go 第 61 行起,删掉了两路递归那几行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func pdqsort_func(data lessSwap, a, b, limit int) {
const maxInsertion = 12
for {
if b-a <= maxInsertion {
insertionSort_func(data, a, b)
return
}
if limit == 0 {
heapSort_func(data, a, b)
return
}
pivot, hint := choosePivot_func(data, a, b)
if hint == decreasingHint {
reverseRange_func(data, a, b)
pivot = (b - 1) - (pivot - a)
hint = increasingHint
}
// breakPatterns、partialInsertionSort 与两路递归略
}
}

maxInsertion = 12 是这段代码里第一个常数。递归到长度 12 以下,直接交给 insertionSort_func 然后 return,不再选 pivot、不再分割、不再压栈。理由不复杂:一段十几个元素的区间上,选 pivot 要比较三四次,分割要扫一遍再换几次位,递归还要存返回地址,这些固定开销加起来已经超过把十几个元素插排一遍。插排本身在短区间上也不丢人。内层是相邻比较,比到不该挪的就停,最坏 O(k²),k 最大 12,一百多次封顶。快排递归下去每层都要扫一遍自己那一段,一层一层摊下来,短区间上每层的固定开销比有效工作还多。

这条线划在 12。

五百个元素那次是 66 到 68 微秒,摊到每个元素 0.13 微秒,一百万个那次是 0.18 微秒。五百个 int 是 4000 字节,整个数组装得进一级缓存,递归到最后一层全是十几个元素的小段,插排在这些小段上几乎是线性的。

坏分割用完,退回堆排序

第二个常数不在函数里,是调用方传进来的。slices.Sort 传的是 bits.Len(uint(n)),一百万个元素就是 20。每做一次明显不平衡的分割,limit 减一,减到 0 就调 heapSort_func 把整段排完。这一条不是优化,是保证:快排最坏能退到 O(n²),堆排序最坏 O(n log n),闸门一关,最坏情况就被钉在那儿了,代价只是这类输入上慢一些,不会慢到没法收场。工程里能接受的往往不是最快,而是有个像样的上限。

二十次机会,用完换人。

第三个优化管的是输入里的规律。上一次分割如果不平衡,wasBalanced 就是 false,下一轮开头先跑 breakPatterns_func。它干的事很朴素:长度够 8 的话,用 xorshift 取一个伪随机数,把区间中间那三个位置挨个跟随机位置换一下。只动三个,不多不少,目的是打散那些会让 pivot 每次都挑到最边上的排列。

三个优化各自管一段输入:12 以下省递归的固定开销,breakPatterns 和 partialInsertionSort 管有规律或基本有序的输入,limit 管最坏情况。少任何一个,另外两个的效果都要打折。我一开始以为这是三份独立的补丁,后来才看出来它们在补同一件事:快排默认输入是随机的那个假设。

主干这些年换过三次。最初是朴素快排,中间那版是 introsort 那一路,小切片交给 shell sort,Go 1.19 起换成 pdqsort,改动记在 golang/go#50154。pdqsort 的思路来自 Orson Peters 的论文,arxiv 2106.05123,C++ 实现是 orlp/pdqsort。Go 这一版没有照搬论文里的全部内容,zsortfunc.go 第 56 行的注释写得很直白:without the optimizations from BlockQuicksort。我第一次读这句还以为看错了,翻回论文才发现那部分确实被整段拿掉。

(写这段之前我又打开那个文件看了一眼,行号还停在原处。)

稳定的价格是十二倍

第三组换数据形态,三十万条记录,每条一个 key 加几个字段,按 key 排。

写法 中位耗时 相对不稳定
sort.Slice 72.8 ms 1.00×
sort.SliceStable 864.2 ms 11.87×

11.87 倍,这个差距跟比较函数没关系,两边传的都是闭包,同一个 less,唯一的区别是 Slice 和 SliceStable。多出来的八百毫秒全是算法本身的账:归并每一轮都要把元素搬来搬去,symMerge 每次合并前得先二分找位置,搬动次数比快排多一个量级。

稳定性到底改了什么,计时说不清楚,计数能说清楚。二十条记录,只有三个不同的 key,排之前给每条记下原始下标,排完扫一遍,同一个 key 的两条如果下标大的跑到了前面,就计一个逆序对。逆序对是定义,跟机器、跟缓存、跟 GC 都没有关系,9 和 0 之间没有噪声。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type rec struct {
key int
idx int // 原始下标
}

func inversions(a []rec) int {
n := 0
for i := 0; i < len(a); i++ {
for j := i + 1; j < len(a); j++ {
if a[i].key == a[j].key && a[i].idx > a[j].idx {
n++
}
}
}
return n
}

sort.Slice 排出来 9 个,sort.SliceStable 是 0 个。

九个对零个。

业务上稳定常常不是性能选项,是语义要求。同一个用户的两条订单时间一样,先提交的那条该排在前面;分页查询里两条记录的排序键相等,稳不稳定决定了翻到第二页会不会又看见第一条。这类要求写不进比较函数,只能靠算法保证,所以真到这一步,11.87 倍是必须付的。付之前还是值得问一句有没有更便宜的走法。稳定排序要的是相等元素保持原序,把原始下标塞进比较函数当第二关键字,不稳定的排序也能给出同样的结果,key 相等就比下标,小的在前。代价只落在相等的那一对上,多一次比较。这条改法我这篇没量,不敢给数。

(十二倍这个数我一直记着,比 864 毫秒好记。)

三个问题,顺序不能换

顺序反过来了。以前先想用哪个函数,现在先问三个问题。第一个,这批数据里会不会出现相等的键,相等的时候业务有没有要求保持原序,有要求就得上稳定,没要求就别付那十二倍。第二个,比较函数有多贵:能拿到 []int、[]string 这种有序类型的,slices.Sort 一行解决;结构体按字段排,slices.SortFunc,泛型实例化,没有 reflect.Swapper 那层;只有排 []any 或者迁就老接口的时候才轮到 sort.Slice。

第三个,数据从哪儿来。从库里按主键捞的、从上游有序结果拼的、倒序拿回来又要正序用的,这些都不用作任何预处理,pdqsort 自己认得出。代码里要是已经写了 sort.SliceIsSorted 先判一遍再决定排不排,那次扫描是白送的:slices.Sort 进去第一趟干的就是这件事,判完发现有序直接返回,一分钱不多花。

先问稳定,再问比较函数的价钱,最后才轮到算法名字。(那本笔记后来被我翻得起了毛边。)

那个写错的基准我还留着,sort_test.go,sync.Once 没删,数据懒建。每次跑之前先 -count=3,跑完盯着第一行,确认它不是三毫秒。