首个向量化 Quicksort 诞生
Vectorized and performance-portable Quicksort
我们开源了一款全新的排序算法，其速度比 C++ 标准库的 std::sort 快约 10 倍，且能超越现有针对特定架构优化的算法。该实现利用 SIMD 指令集，在保持对现代 CPU 架构广泛兼容的同时，显著提升了列式数据库场景下的排序效率。通过巧妙运用 compress-store 指令及其在 AVX2 等架构上的模拟方案，我们实现了首个跨平台的向量化 Quicksort。无论是在 Apple M1 还是 Intel Skylake 上，该算法均刷新了单核排序速度的记录，为处理大规模数据带来了前所未有的性能突破。
我们期待看到，当单 CPU 核心能够实现每秒 1GB 的排序速度时，将解锁哪些全新的应用场景与能力。
HN 评论区
29- zX41ZdbW
在这里看到这篇帖子有点奇怪，文章其实挺老了。
自从 pdqsort、vqsort 和 glide sort 出现后，目前的顶尖排序算法已经是 driftsort 和 ipnsort 了。
我已经把它们集成到了 ClickHouse 中：https://github.com/ClickHouse/ClickHouse/pull/106650
- bee_rider
好吧，它发布有一阵子了，所以我们可以稍微调皮一点：
归并排序和堆排序确实有一种美感。它们的名字就揭示了核心思想，工作原理也一目了然。
相比之下，快速排序毫无美感可言，它的名字只是源于它唯一值得称道的特点（即在大多数情况下速度很快）。
- minitech
实际标题：“向量化且性能可移植的快速排序”（2022 年）。
所谓“首个”的实际含义是：
> 令人欣慰的是，现代指令集（Arm SVE、RISC-V V、x86 AVX-512）包含一条专门用于划分的特殊指令。给定一个独立的 yes/no 值输入（表示元素是否小于枢轴），这条“压缩存储”指令仅将对应输入为“yes”的元素存储到连续的内存中。随后，我们可以对 yes/no 值进行逻辑取反，再次应用该指令，将元素写入另一个分区。这种策略已在一款针对 AVX-512 的快速排序中使用。那么，对于没有压缩存储指令的其他指令集（如 AVX2）该怎么办呢？先前的工作已经展示了如何使用置换指令来模拟这一操作。
> 我们在此基础上构建，实现了首个可移植到三大架构上六种指令集的向量化快速排序，并且实际上超越了以往针对特定架构的排序算法。