我们今天分享的开源代码排序数值数组速度约为 C++ std::sort 的10倍，且优于顶尖架构特定算法并可移植至所有现代 CPU 架构。近期列式数据库连续存储某列值而非记录行字段，过滤排序更快，故聚焦此布局。排序研究已多，10倍加速源于 SIMD/向量指令，即单指令操作多独立元素，如 AVX-512 一次处理16个 float32，或安谋（Arm） NEON 一次4个。

今天我们公开了这样一份开源代码：排序数字数组的速度约为 C++ std::sort 的十倍，超过当前针对特定架构优化的最先进算法，同时还能在所有现代 CPU 架构之间移植。下面说说我们是怎么做到的。

先说背景。近年出现了列式数据库的潮流，它把某一列的所有值连续存放，而不是先存完一条记录或「行」的所有字段再存下一条。这样过滤或排序往往更快，而这两者正是 SQL 查询的基础构件，因此我们关注这种数据布局。

排序已被研究得非常透彻，10 倍的提速从何而来？答案在 SIMD/向量指令。它用一条指令对多个相互独立的元素做运算——例如用 AVX-512 指令集一次处理 16 个 float32，用 Arm NEON 一次处理 4 个：

如果你已经熟悉 SIMD，可能听说过它被用于超级计算机、机器学习的线性代数、视频处理，或者 JPEG XL 这类图像编解码器。但既然 SIMD 运算只涉及相互独立的元素，而排序要重新排列相邻的数组元素，怎么能用它来排序？

设想我们有一种特别的方法，可以排序例如 256 个元素的数组。那么用快速排序算法处理更大的数组时，就把它划分成两个子数组：小于「基准值」（理想情况是中位数）的元素，以及其余元素；然后递归，直到某个子数组不超过 256 个元素，再用我们的特别方法排序。划分占了大部分 CPU 时间，所以只要能借助 SIMD 加速划分，就能得到快速的排序。

幸运的是，现代指令集（Arm SVE、RISC-V V、x86 AVX-512）都包含一条适合划分的指令。给定一路单独输入的「是/否」值（表示某元素是否小于基准值），这条「压缩存储」指令只把对应输入为「是」的元素连续写入内存。接着我们可以对是/否值做逻辑取反，再执行一次，把元素写入另一个分区。这一策略已被一个 AVX-512 专用的快速排序采用。但 AVX2 这类没有压缩存储的指令集怎么办？此前的工作已经展示如何用排列指令模拟它。

我们在这些技术之上，做出了第一个可移植到三种架构、六种指令集的向量化快速排序，而且实际上还超过了此前针对特定架构的排序实现。我们的实现使用 Highway 的可移植 SIMD 函数，因此不必为每个平台重写大约 3000 行 C++。Highway 在有压缩存储时使用它，否则使用等效的排列指令。此前的先进实现只支持 32 位整数，而我们支持 16 至 128 位输入。

尽管只有一份可移植实现，我们却在 AVX2、AVX-512（Intel Skylake）和 Arm NEON（Apple M1）上都达到了创纪录的速度。对一百万个 32/64/128 位数字，我们的代码在 Apple M1 上的排序输出速率为 499/471/466 MB/s；在 3 GHz 的 Skylake 配 AVX-512 上为 1123/1119/1120 MB/s。有意思的是，AVX-512 比 AVX2 快 1.4 至 1.6 倍——不用额外付出任何努力就能白得这个提速（Highway 会检测 CPU 上可用的指令并使用其中最好的）。在 AVX2 上我们测得 798 MB/s，而此前专门针对 AVX2 优化的先进实现只有 699 MB/s。作为对照，标准库在同一 CPU 上只达到 58/128/117 MB/s，也就是说按数字类型不同，我们实现了 9 到 19 倍的提速。

过去排序一直被认为很昂贵。单核就能以 1 GB/s 排序，会解锁哪些新应用和新能力，我们很期待。采用 Apache2 许可的源代码已在 GitHub 上发布（如有问题或意见，欢迎提 issue），我们的论文也对实现（包括 256 个元素的特殊情况）做了详细解释与评估。

多数读者指出该文章发表于 2022 年已显陈旧且相关技术早已普及，少数人则对只排数字的实现、命名美学及面试乱象提出调侃或质疑。

认为文章老旧且技术已非最前沿

• 多名读者对旧文被顶上首页表示困惑，指出当前最先进的排序算法已是 driftsort 和 ipnsort，且此类向量化技术早已被主流项目广泛采纳。（较多人） > 文章挺老的，自 pdqsort、vqsort 之后，目前最前沿的其实是 driftsort 和 ipnsort，我已经把它们集成进 ClickHouse 了。（@zX41ZdbW）

澄清所谓“首个”是指跨指令集可移植

• 有读者详细解释，该工作的标题实为“可向量化且性能可移植的快速排序”，其“第一”是指首个能移植到三种架构六种指令集的向量化快排，而非第一个向量化快排。（少数人） > 实际标题是“可向量化且性能可移植的快速排序”，其“第一”是指首个能在六种指令集上移植且性能优于以往特定架构实现的向量化快排。（@minitech）

向量化排数字具有实际工程价值

• 有人从直方图构建等场景出发，说明先向量化排好样本再统计会简单很多，以此回应为何要专门做向量化数字排序。（少数人） > 如果好奇为何要向量化排数字，建直方图就是个用例，先排好样本再建直方图容易得多。（@kg）

质疑仅排数字不如用基数排序及面试乱象

• 有读者认为既然实现只排数字，基数排序可能更优；另有人调侃若创业公司面试让手写向量化快排属实离谱，只有巨头和量化基金才用得上。（少数人） > 只能排数字吗？那用基数排序难道不会好很多？（@brrrrrm）

调侃快速排序命名毫无美感

• 一位评论者对比归并排序和堆排序，认为快速排序名字土且仅有快这一个优点，代表了社区对算法命名的轻松吐槽。（少数人） > 归并和堆排序名字优美且见名知意，快速排序则毫无美感，全靠快撑着。（@bee_rider）

有价值的补充

• 该实现借助 Highway 的跨平台 SIMD 函数，避免了为每个平台重写约 3000 行 C++，有人好奇如今是否会用大模型来生成这些代码。（@mixologic）
• 现代指令集如 Arm SVE、RISC-V V、x86 AVX-512 带有压缩存储指令，可根据是否小于基准值来连续存放元素，无此指令的如 AVX2 可用置换指令模拟。（@minitech）