Google发布首个向量化快速排序开源实现

Google推出了首个向量化快速排序的开源实现，通过利用SIMD指令集技术在数组排序中取得显著性能提升1。这一实现比C++标准库的std::sort快9至19倍，具体速度差异取决于数字类型1。在AVX2指令集下，新实现可达798 MB/s的排序速度，超过了之前最优实现的699 MB/s1。使用AVX-512指令集时，32位、64位和128位数字的排序速度分别达到1123、1119和1120 MB/s1。在Apple M1芯片上，相应速度为499、471和466 MB/s1。

该实现支持16至128位的输入数据范围，相比之前仅支持32位整数的方案实现了重大改进1。技术方面，该实现采用了Highway库的可移植SIMD函数，支持AVX2、AVX-512和Arm NEON等六种指令集的跨架构兼容性1。在单核CPU上，该算法可达约1GB/s的排序速度1。这一开源项目已按Apache 2.0协议在Github上发布1。

Google has unveiled an open-source vectorized Quicksort implementation that leverages SIMD instruction sets to dramatically accelerate array sorting operations 1. The new algorithm achieves approximately tenfold performance improvement over standard approaches and runs 9 to 19 times faster than C++ std::sort, depending on the numeric data type being processed 1.

The implementation demonstrates substantial speed gains across multiple processor architectures 1. On AVX2 instruction sets, it reaches 798 MB/s, surpassing the previous best-performing solution at 699 MB/s 1. AVX-512 systems achieve between 1,119 and 1,123 MB/s for 32, 64, and 128-bit integers respectively, while Apple M1 processors attain speeds ranging from 466 to 499 MB/s across the same data widths 1. The solution can sustain sorting throughput of up to 1 GB/s on a single CPU core 1.

A key advancement over prior implementations is the expanded data type support, now handling 16 to 128-bit inputs compared to previous solutions limited to 32-bit integers 1. The vectorized Quicksort uses portable SIMD functions from the Highway library, enabling compatibility across six instruction set variants spanning three different processor architectures 1. Released under the Apache 2 license, the code is available on GitHub 1.