一段最新开源的代码显示，其排序速度较 C++ 标准库的 std::sort 快约十倍，性能不仅优于针对特定架构优化的最先进算法，还具备跨所有现代 CPU 架构的可移植性。
技术背景与突破点
随着列式数据库（columnar databases）的兴起，数据布局从传统的行存储转向按列连续存储。这种布局显著提升了过滤和排序效率，而这两者正是 SQL 查询的核心构建模块。鉴于排序算法已被充分研究，实现十倍性能提升的关键在于 SIMD（单指令多数据）/向量指令的应用。
SIMD 允许在单条指令中并行处理多个独立元素，例如通过 AVX-512 一次性处理 16 个 float32 数值，或在 Arm NEON 中处理四个数值。尽管 SIMD 常见于高性能计算、机器学习及图像编解码领域，但将其应用于涉及元素重排的排序任务并非易事。
向量化快速排序的实现
研究团队采用了一种混合策略：对于大规模数组，使用快速排序算法将其递归划分为小于“基准值”和大于等于“基准值”的子数组，直到子数组规模缩小至 256 个元素以内，再调用专用方法进行排序。由于分区操作占据了大部分 CPU 时间，利用 SIMD 加速该过程成为性能突破的关键。
现代指令集（如 Arm SVE、RISC-V V、x86 AVX-512）提供了“压缩存储”（compress-store）指令，可根据布尔掩码将符合条件的元素连续存入内存，从而高效完成分区。针对缺乏该指令的架构（如 AVX2），团队通过置换（permute）指令模拟了这一功能。
在此基础上，团队实现了首个支持六种指令集、跨越三个架构的可移植向量化快速排序。借助 Google 的 Highway 可移植 SIMD 库，无需为每个平台重写约 3000 行 C++ 代码。Highway 会自动检测 CPU 能力，优先使用 compress-store，否则回退至等效的置换指令。此外，该实现支持完整的 16 至 128 位输入范围，突破了此前仅限 32 位整数的局限。
性能基准测试
尽管仅维护单一可移植代码库，该算法在多种硬件平台上均刷新了速度纪录：
- Apple M1 (Arm NEON)：对一百万个 32/64/128 位数字进行排序，吞吐量分别达到 499/471/466 MB/s。
- Intel Skylake (3 GHz, AVX-512)：吞吐量分别为 1123/1119/1120 MB/s。
- Intel Skylake (AVX2)：吞吐量为 798 MB/s，高于此前专为 AVX2 优化的最先进算法（699 MB/s）。
值得注意的是，AVX-512 的性能比 AVX2 高出 1.4 至 1.6 倍，且这一提升由 Highway 库自动适配完成，无需额外开发成本。相比之下，同一 CPU 上 C++ 标准库的排序速率仅为 58/128/117 MB/s。这意味着新算法实现了 9 至 19 倍 的速度提升，具体幅度取决于数据类型。
目前，该源代码已在 Github 上以 Apache2 许可证发布，相关论文详细阐述了实现细节及评估结果。随着单核排序速度突破 1 GB/s 大关，未来有望解锁更多实时数据处理的新应用场景。