Branchless Quicksort：比 std::sort 和 pdqsort 更快的无分支快速排序

背景

在现代 CPU 架构中，分支预测失败（Branch Misprediction）是性能优化的主要瓶颈之一。传统的快速排序（Quicksort）实现通常依赖于条件判断（如 if 语句）来划分数据，这在数据分布不均或随机性高时会导致大量的分支预测错误，从而显著降低执行效率。

本文介绍了一种名为 blqsort（Branchless Quicksort）的算法实现，它通过消除分区过程中的条件分支，显著提升了排序速度。该实现提供了 C 和 C++ 两种 API，并在基准测试中展示了优于标准库 std::sort 以及高性能排序算法 pdqsort 的性能。其灵感部分来源于 fluxsort 和 Edelkamp 与 Weiß 的研究论文，旨在通过无分支技术优化分区性能。

核心内容

1. 性能基准与硬件环境

性能结果高度依赖于底层硬件。基准测试对 5000 万个 double 类型数据进行了排序，测试环境如下：

• Apple M1 系统：使用 Clang 编译器，开启 -O3 优化。
• AMD Ryzen 3 Linux 系统：使用 GCC 编译器，开启 -O3 优化。

为了公平比较，此处展示的是 blqs 的单线程版本。在 M1 芯片上，多线程版本的速度还能再提升 3 到 4 倍。在运行时，C++ 版本与 C 版本的性能差异极小。完整源代码已托管在 Github 上，包含四个单头文件实现的 blqsort 版本。

2. 无分支分区技术原理

现代 CPU 避免分支预测失败的关键在于消除条件分支。

传统分支版本：

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

无分支版本：

for (int i = 0; i < 1000; i++) {
    small_numbers[smlen] = numbers[i];
    smlen += (numbers[i] < 500); // 利用布尔值转整数特性
}

无分支版本通过算术运算替代条件跳转，避免了流水线停顿。

3. 算法策略与优化细节

• 辅助缓冲区策略：借鉴 fluxsort 的思路，使用一个大小为 1024 元素的栈数组（Stack Array，而非堆内存）作为辅助缓冲区。

  1. 首先从一侧复制 1024 个元素到辅助缓冲区，腾出空间。
  2. 以无分支方式交替将 1024 元素块复制到左侧或右侧。
  3. 左指针仅在元素小于基准值（Pivot）时递增，否则右指针递增。
  • 代价与收益：这种方法涉及的复制操作量是必要操作的两倍以上。但对于可廉价复制的数据类型（如基本数值类型），这种额外的拷贝成本远低于分支预测失败带来的惩罚。

• 处理最坏情况与不平衡分区：

  • 为防止坏数据导致 $O(n^2)$ 的运行时间，算法会将相同元素分组。
  • 如果在分区过程中检测到严重不平衡，算法会切换到堆排序（Heapsort）处理该部分。
  • 检查分区是否已经有序。

• 基准值选择与循环展开：

  • 对于较大数据块，使用“中位数的中位数”（Median-of-medians）策略寻找优质基准值。
  • 关键的分区循环被显式展开（Explicitly Unrolled）。

• 小数据排序网络：

  • 对于 2 到 12 个元素的情况，使用自定义的排序网络（Sorting Networks）。
  • 虽然这需要为每种大小提供独立的代码路径，但利用无分支的 sort-2 原语，可以用极少的交换次数完成小集合排序。

• 高拷贝成本类型的处理：

  • 对于 std::is_trivially_copyable 为假的高拷贝成本类型（如 std::string），基于缓冲区的无分支方法效率较低。
  • 此时采用 BlockQuicksort（Edelkamp 和 Weiß 提出的变体）：仅对元素索引进行无分支处理，随后用更少的交换次数移动实际数据。部分思路借鉴自 pdqsort。

4. API 使用示例

C++ 单线程

只需包含 blqs.h，用法与 std::sort 类似：

#include "blqs.h"
double data[SIZE];
blqs::sort(data, data + SIZE);

C++ 多线程

使用 C++ 线程，包含 blqs_thr.h：

#include "blqs_thr.h"
// 函数调用方式相同

C 单线程

通过 #define 生成针对特定数据类型的专用代码：

#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "blqsort.h"

double data[SIZE];
blqsort(data, SIZE);

C 多线程

使用 POSIX 线程，包含 blqsort_thr.h：

#include "blqsort_thr.h"
// 函数调用方式相同

5. 自定义数据结构支持

在实际工程中，经常需要对自定义结构体进行排序。虽然 SIMD 库（如 Google Highway）在处理简单数值时极快，但在使用自定义比较逻辑时变得难以适用。std::sort 或 blqsort 提供了更高的灵活性。

C++ 示例：

#include "blqs.h"
struct entry {
    int id;
    int value;
    bool operator<(const entry& other) const {
        return id < other.id;
    }
};
struct entry data[SIZE];
blqs::sort(data, data + SIZE);

C 示例：

struct entry {
    int id;
    int value;
};
#define BLQS_CMP(a, b) (((a).id) < ((b).id))
#define BLQS_TYPE struct entry
#include "blqsort.h"

struct entry data[SIZE];
blqsort(data, SIZE);

基准测试显示，对 5000 万个此类结构体进行排序时，该算法依然保持高效。

关键要点

• 无分支优势：通过消除 if 条件分支，避免 CPU 分支预测失败，显著提升基于数值类型的排序性能。
• 空间换时间：利用 1024 元素的栈辅助缓冲区进行无分支分区，虽然增加了数据拷贝次数，但对于廉价拷贝类型，整体性能优于传统分支方法。
• 混合策略：
  • 小数据（2-12 元素）：使用排序网络。
  • 大数据：使用中位数的中位数选基准。
  • 极端情况：检测到不平衡时切换至堆排序，防止 $O(n^2)$ 退化。
• 类型适应性：
  • 对于可平凡拷贝（Trivially Copyable）类型，使用基于缓冲区的无分支方法。
  • 对于高拷贝成本类型（如字符串），使用基于索引的 BlockQuicksort 变体。
• 易用性：提供 C 和 C++ 接口，API 设计简洁，支持自定义比较逻辑，兼容 std::sort 的使用习惯。
• 多线程支持：C++ 版本支持 C++ Threads，C 版本支持 POSIX Threads，多线程模式下性能可进一步提升 3-4 倍。

意义与影响

blqsort 展示了在系统级