一位程序员为Quicksort写了一整套排序网络:从2个元素到12个元素,各配一套compare-swap宏,配合med5取中位数、512大小的swap buffer、循环展开16次——能想到的底层技巧几乎用全了。他把这段代码实测跑了一遍:50000万个double,苹果M1,Clang,-O3优化,结果是4.39秒。而同样的任务,标准库里最普通的std::sort只用了1.33秒。
这篇文章的标题起得很诚实:《你的代码快——如果你走运的话》。这不是自嘲式的标题党,而是点破了一个圈内人心知肚明、却很少摊开讲的事实:branchless(无分支)优化到底能不能生效,很大程度不取决于你写得多聪明,而取决于编译器那一刻愿不愿意配合。
无分支partition,是为了治谁的病
Quicksort最耗时的部分是partition阶段,每次比较的走向都依赖数据本身。数据一乱,CPU的分支预测器就频繁猜错,现代深流水线处理器为此付出的代价相当可观。业界早有对策:一类叫BlockQuicksort,用缓冲区代替if分支来做无分支的compare-swap;另一类是给小规模数据配一套固定的排序网络,元素少到一定程度就完全不需要分支和循环开销。
这不是孤立发明。Clang默认的libc++标准库里,sort.h源码就藏着一个由__use_branchless_sort开关控制的无分支__sort5路径——连标准库维护者都把这类技巧当成一个可以打开也可以关闭的选项,而不是默认答案。这个细节本身就说明,这条路没有想象中那么稳。
同一类打法,两次跑分判若两人
有意思的地方在于对照。这篇文章自己的实测是4.39秒对1.33秒,优化后的代码反而慢了3.3倍。但在作者此前另一篇讲blqsort的文章里,同样M1加Clang的环境下,std::sort是1.33秒,blqsort是0.66秒,快了整整一倍;换到AMD Ryzen加GCC,std::sort要5.56秒,blqsort是1.98秒,快了2.8倍。
这两次跑分是不是同一份代码的不同版本,原文没有交代清楚。但恰恰是这个说不清,才最说明问题:哪怕是同一个作者、同一台M1、同一个Clang,写法稍微一变、版本稍微一迭代,无分支优化就可能从"碾压std::sort"滑向"反被std::sort碾压"。
"运气"到底是什么:编译器在赌哪一步
很多人以为,只要把if-else写成三元表达式a = m ? a : b,编译器就会老老实实生成无分支的cmov或select指令。真相并非如此。LLVM的Loop Vectorizer确实具备"if-conversion"能力,可以把循环体里的if语句展平成一条指令流,但这是由内部cost model驱动的判断,不是写法本身的承诺。
"谋事在人,成事在天"——这句老话放在这里再合适不过。程序员能决定的只是写法这一步,后面的降级判定,发生在一个不承诺可复现的黑箱里。所谓"Clang比GCC聪明",很多时候说的也不是编译器前端本身,而是Clang默认配的libc++和GCC默认配的libstdc++,两套std::sort实现本来就不是一回事。把平台差异简单归因成"编译器谁更聪明",是个常见的误读。
无分支不是万能药
学术界给出的真实收益区间,比直觉小得多。一篇研究BlockQuicksort的论文报告,无分支partition相对GCC的std::sort最高提速约80%;而另一篇专门研究"把排序网络嵌入quicksort小分区"的论文给出的数字要朴素得多——相对insertion-sort基线只有4.3%到6.7%的提升,相对std::sort最高也就12.7%。排序网络本身从来不是杀招,真正的大头收益来自整体的无分支partition策略。
- 风险.branchless策略吃的是"数据分布够随机"这个前提,近乎有序或大量重复值的输入下,pattern-defeating的pdqsort反而可能反超,Boost官方文档也把pdqsort系列列为std::sort更实用的替代品,而不是无分支版本。
原文和它引用的跑分,测试数据只有随机生成的double,没有覆盖近乎有序、对抗构造、重复值这几种更贴近真实业务的场景。这块空白,恰恰是判断"这段代码到底能不能抄"之前最该补上的一课。
拿到一段"别人机器上很快"的优化代码,别急着搬进自己项目。换一版编译器、换一颗CPU、换一批业务数据,结果可能从碾压std::sort变成反被std::sort碾压——这份文章自己的4.39秒,就是最现成的反面教材。
- 建议.想验证一段branchless代码是否真的生效,别只看秒表,拿
-Rpass=loop-vectorize之类的编译器诊断选项,看看if-conversion到底有没有真的发生。