今天我们分享开源代码，它可以对数字数组进行排序，速度约为C++ std::sort的十倍，并且优于最先进的特定架构算法，同时可移植到所有现代CPU架构。下面我们讨论如何实现这一点。

首先，一些背景。最近出现了一种趋势，即列式数据库连续存储某一列的所有值，而不是先存储一条记录或“行”的所有字段，再存储下一条记录的字段。这在过滤或排序时可能更快，而过滤和排序是SQL查询的关键构建块；因此我们关注这种数据布局。

鉴于排序已被大量研究，我们怎么可能找到10倍的加速？答案在于SIMD/向量指令。这些指令在单条指令中对多个独立元素执行操作——例如，使用AVX-512指令集时一次操作16个float32，或在Arm NEON上操作四个。

如果您已经熟悉SIMD，您可能听说过它被用于超级计算机、机器学习应用的线性代数、视频处理，或JPEG XL等图像编解码器。但是，如果SIMD操作只涉及独立元素，我们如何对它们排序，而排序涉及重新排列相邻数组元素？想象我们有一种特殊的方式来排序，例如256个元素的数组。然后，用于排序更大数组的快速排序算法包括将其划分为两个子数组：小于“枢轴”值（理想情况下是中位数）的元素，以及所有其他元素；然后递归，直到子数组最多为256个元素大，并使用我们的特殊方法对这些元素进行排序。分区占用了大部分CPU时间，因此如果我们能使用SIMD加速它，我们就有了快速排序。

幸运的是，现代指令集（Arm SVE、RISC-V V、x86 AVX-512）包含一条适合分区的特殊指令。给定一个单独的yes/no值输入（元素是否小于枢轴），这条“压缩存储”指令仅将对应输入为“yes”的元素存储到连续内存中。然后我们可以对yes/no值进行逻辑取反，并再次应用该指令，将元素写入另一个分区。这种策略已被用于AVX-512专用的快速排序。但是，其他没有压缩存储的指令集（如AVX2）呢？先前的工作已经展示了如何使用置换指令来模拟这条指令。我们基于这些技术，实现了第一个可移植到三种架构的六种指令集的向量化快速排序，并且实际上优于先前的特定架构排序。

我们的实现使用Highway的可移植SIMD函数，因此我们不必为每个平台重新实现约3,000行C++代码。Highway在可用时使用压缩存储，否则使用等效的置换指令。与先前的最高水平——它也特定于32位整数——相比，我们支持16-128位输入的完整范围。尽管我们只有单一的可移植实现，但我们在AVX2、AVX-512（Intel Skylake）和Arm NEON（Apple M1）上都达到了创纪录的速度。对于一百万个32/64/128位数字，我们的代码在Apple M1上运行，可以以499/471/466 MB/s的速率生成排序输出。在配备AVX-512的3 GHz Skylake上，速度为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倍的加速。

以前，排序一直被认为是昂贵的。我们很感兴趣看到，能够在单个CPU核心上以1 GB/s的速度排序，将解锁哪些新的应用和能力。Apache2许可的源代码……