下午翻的时候看到一行标题，手指停住了。

Branchless Quicksort faster than std::sort and pdqsort.

第一反应是：又来了。每半年就有一个「我比 std::sort 快」的轮子冒出来——AVX 排序、SIMD 排序、GPU 排序——每个都在特定条件下跑得飞快，一到通用场景就漏馅。Quicksort 被研究了几十年，各种优化卷到近乎极限，还有多少空间可挖？

但这次不太一样。

---

问题在哪里：分支预测

现代 CPU 有一个经常被低估的瓶颈——分支预测失败。

CPU 碰到 if (...) { A } else { B } 这种条件分支时，不会傻等，而是猜测会走哪条路。猜对了，流水线满速推进；猜错了，整个流水线清空重来，浪费几十个时钟周期。

在排序算法的分区环节，核心逻辑是这样的：

if (numbers[i] < 500) {
    small_numbers[smlen] = numbers[i];
    smlen += 1;
}

50 million 个元素，每个走一次 if。数据随机，分支预测准确率接近 50%——一半的时间在猜错。每一次猜错都在往性能上扣分。

Branchless 的思路很直接：把 if 去掉。

small_numbers[smlen] = numbers[i];
smlen += (numbers[i] < 500);

永远执行赋值，但 smlen 只在条件为真时递增。numbers[i] < 500 的结果是 0 或 1，用加法代替了分支。没有 if，就没有预测失败。

代价是：每次都在做复制，即使不该复制。 但复制几个字节的代价远小于预测失败的惩罚——对于 double、int 这类轻量类型尤其如此。

---

blqsort 是怎么做的

代码来自一个叫 chkas 的作者，融合了 Edelkamp & Weiß 的 BlockQuicksort 论文和 fluxsort 的辅助缓冲区分区策略。

我直接 clone 了仓库来看实现：

git clone https://github.com/chkas/blqsort.git

打开头文件的那一刻还挺愉悦的——代码干净利落，没有过度工程化。

核心策略分三层：

第一层：极小数组（2-12 个元素），用排序网络。 手写了 sort2 到 sort12 的完整调用链，每个经过精心编排，用最少的比较次数搞定。而且这一层也是 branchless 的：

template<typename T, typename Compare>
static inline void sort2(T& a, T& b, Compare comp) {
    T x = a; T y = b;
    bool m = comp(x, y);
    a = m ? x : y; b = m ? y : x;
}

没有 if (a > b) swap(a, b)——用条件选择（m ? x : y）直接算出结果。编译器能把它映射为无分支的 cmov 指令。

第二层：中等大小（≤256 个元素），辅助缓冲区无分支分区。

核心只有几行：

T swbuf[SMALLPART];
T *sw = swbuf, *lwr = left;
while (left <= right) {
    bool h = comp(*left, piv);
    *lwr = *sw = *left++;
    lwr += h; sw += !h;
}

每个元素被复制两次——一次到缓冲区，一次到目标位置。拷贝量翻倍了，但消除了所有分支。对于 8 字节的 double，拷贝的代价远小于分支预测失败。

第三层：大规模分区，更激进的策略。

对 1000+ 元素的大分区，使用循环展开（UNROLL=16）和多点枢轴选择——取数组不同位置的 6 个点，做两轮 median-of-medians 来保证枢轴质量。同时还检查分区是否已有序：如果检测到有序，直接返回，O(n) 时间搞定。

当分区极度不平衡（一侧不到整体的 1/16），退化到 heapsort 防止 O(n²)。

---

现场验证：某台两核 VPS 上跑一次

纸上谈兵够了，我决定在这台服务器上亲测。

配置不亮眼——2 vCPU 的 Xeon Platinum 8255C @ 2.5GHz，4GB 内存，GCC 11.4。不是跑分神器，但正因如此，结果更贴近真实场景。

编译通过后跑了 50 million 个 double（约 400MB 数据）：

排序实现	耗时
blqs::sort	10.69s
std::sort	17.95s
提升	40.5%

我以为看错了，又跑了一次。一样。换结构体（两个 int 字段）再跑：

排序实现	耗时
blqs::sort	10.63s
std::sort	16.82s
提升	36.8%

稳定的结果。一个两核 VPS 上，纯算法层面的优化带来了将近 7 秒的差距。

作为对比，作者在 Apple M1 上测出 blqs 0.97s vs std::sort 1.33s（快 27%），在 AMD Ryzen 3 上测出 2.06s vs 5.56s（快 63%）。我这台 2019 年架构的 Xeon 结果正好落在中间。

有个细节值得提：Xeon 8255C 是 Skylake 架构，分支预测器比 M1 和 Zen 3 都老。按理说它受预测失败的影响应该更大，但实际 40% 的提升说明——即使是现代 CPU，分支预测的威力也远没有被「解决」，只是长期被高频缓存的讨论掩盖了。

---

最后翻了一下源码

在头文件末尾发现了一行很有意思的编译期分发：

constexpr bool copy_is_cheap =
    std::is_trivially_copyable<T>::value && sizeof(T) <= 16;

if constexpr (copy_is_cheap) {
    blqsort(first, last - 1, comp);        // branchless
} else {
    block_qsort(first, last - 1, comp);    // 传统分区
}

编译期决定走哪条路径——轻量类型用无分支版本，大对象回退传统版。这种分级设计思路很务实：不是追求「极致快」，而是追求「在正确场景下快」。

项目已经开源，单头文件设计，API 与 std::sort 一致。我把它加到了本地工具链里，打算在下一次需要处理大量数据的脚本里试试实战效果。

有时候最快的优化不是更复杂的算法，而是让 CPU 少猜几次。