# 无分支快速排序
来源：https://tiki.li/blog/blqsort
## 使用排序网络实现的高性能无分支快速排序（支持 C 和 C++ 接口）
性能测试结果自然取决于底层硬件。以下基准测试展示了使用不同排序实现对 5000 万个 `double` 值进行排序的执行时间。测试分别在 *Apple M1* 系统（使用 *Clang*）和 *AMD Ryzen 3 Linux* 系统（使用 *GCC*）上进行，均以 `-O3` 选项编译。
实现方式 | Apple M1 | AMD Ryzen
--- | --- | ---
std::sort | 1.33s | 5.56s
pdqsort | 1.33s | 2.81s
**blqsort**（单线程） | 0.97s | 2.06s
为了公平比较，此处使用了 `blqs` 的[单线程版本](https://github.com/chkas/blqsort/blob/main/cpp/test_double.cpp)。在 M1 上，多线程版本还能再快 3 到 4 倍。C++ 版本与 C 版本在运行时间上差异极小。
### blqsort
完整源码托管在 [Github](https://github.com/chkas/blqsort) 上。**blqsort** 共有四个实现，每个实现均以单头文件形式提供。
文件 | 描述
--- | ---
[blqs.h](https://github.com/chkas/blqsort/blob/main/cpp/blqs.h) | C++ 单线程版
[blqs\_thr.h](https://github.com/chkas/blqsort/blob/main/cpp/blqs_thr.h) | C++ 多线程版
[blqsort.h](https://github.com/chkas/blqsort/blob/main/c/blqsort.h) | C 单线程版
[blqsort\_thr.h](https://github.com/chkas/blqsort/blob/main/c/blqsort_thr.h) | C 多线程版
### 无分支编程
在现代 CPU 上，**避免分支预测失败**是加速程序的关键技术。以下无分支写法：
```
for (int i = 0; i < 1000; i++) {
small_numbers[smlen] = numbers[i];
smlen += (numbers[i] < 500);
}
```
比含条件分支的传统写法快得多：
```
for (int i = 0; i < 1000; i++) {
if (numbers[i] < 500) {
small_numbers[smlen] = numbers[i];
smlen += 1;
}
}
```
*Edelkamp* 和 *Weiß* 的[这篇论文](https://arxiv.org/abs/1604.06697)展示了如何通过避免条件分支来提升快速排序中分区操作的性能。使用辅助缓冲区进行**无分支分区**的策略受到了 [fluxsort](https://github.com/scandum/fluxsort) 的启发。这里的"辅助缓冲区"指的是一个 1024 个元素的栈数组，而非堆内存。
首先，从一侧将 1024 个元素复制到辅助缓冲区中以腾出空间。然后，以无分支方式交替向左右各复制一个 1024 元素的块。当元素小于枢轴时，左指针递增；否则右指针递增——当然，这一过程也是无分支的。
这涉及超过必要复制操作两倍以上的拷贝次数。但对于拷贝代价较低的数据类型而言，这比由此引发的分支预测失败要廉价得多。
### 枢轴策略、异常输入与排序网络
为避免因异常输入数据导致 `O(n²)` 的运行时间，程序会将相同元素归组，并在检测到分区严重不均衡时，对该部分切换为*堆排序*。程序还会检查某个分区是否已经有序。
对于较大的分区，程序采用中位数的中位数策略来寻找良好的枢轴。此外，关键分区循环被显式展开。
对于 2 到 12 个元素，算法使用自定义排序网络。该方法需要为每种大小单独设计代码路径，但通过无分支的 *sort-2* 原语，以极少的交换次数完成小规模排序。[排序网络来源](https://bertdobbelaere.github.io/sorting_networks.html)
## C++
对于拷贝代价较高且不满足 `is_trivially_copyable` 的类型（如字符串），基于缓冲区的无分支方法效率较低。在这种情况下，会改用 **BlockQuicksort**（*Edelkamp* 和 *Weiß*）变体。该变体仅以无分支方式处理元素索引，再以较少的交换次数移动实际数据。部分思路来源于 [pdqsort](https://github.com/orlp/pdqsort)。
### 使用方式
只需引入 `blqs.h`，使用方式与 *std::sort* 完全相同。
```
#include "blqs.h"
double data[SIZE];
blqs::sort(data, data + SIZE);
```
对于使用 C++ 线程的多线程变体，将 `blqs.h` 替换为 `blqs_thr.h` 即可，函数调用方式保持不变。
## C
在 C 中，通过 `#define` 生成针对特定数据类型的专用代码。
### 使用方式
```
#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "blqsort.h"
double data[SIZE];
blqsort(data, SIZE);
```
对于使用 POSIX 线程的 C 多线程变体，将 `blqsort.h` 替换为 `blqsort_thr.h` 即可，函数调用方式同样保持不变。
## 排序自定义数据结构
实际使用中，我们经常需要对自定义数据结构进行排序。这正是 *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 万个上述 `struct` 进行排序的执行时间：
实现方式 | Apple M1 | AMD Ryzen
--- | --- | ---
std::sort | 3.46s | 4.75s
pdqsort | 3.46s | 4.72s
**blqsort** | 0.96s | 2.20s
### 相关链接
[当 'if' 拖慢你的速度时，避开它。](https://tiki.li/blog/branchless)
[交互式排序演示](https://tiki.li/sorting)
---
[email protected]