Highway SIMD delivers portable Quicksort at 1123 MB/s on AVX-512 Skylake
A single portable SIMD Quicksort in Highway outperforms architecture-specific baselines on AVX2, AVX-512 and NEON while supporting wider type widths. The 9-19x gain over std::sort stems from vectorized partitioning that exploits native or emulated compress-store instructions. Columnar query engines can integrate the change with minimal effort.
The release ports a compress-store partitioning kernel across six instruction sets using Highway's abstraction layer. On inputs of one million elements the code records 798 MB/s under AVX2, 1123 MB/s under AVX-512, and 499 MB/s under NEON while supporting 16- to 128-bit types. Partitioning dominates runtime; the kernel replaces scalar comparisons with vector masks and either native compress-store or emulated permute sequences.
Measured throughput exceeds std::sort by 9-19x on the same cores. AVX-512 yields a 1.4-1.6x gain over AVX2 with zero source changes because Highway selects the best available instructions at runtime. Columnar database engines that already store data contiguously therefore obtain an immediate drop-in replacement for their sort primitives without per-architecture forks.
The work closes the gap between research prototypes limited to AVX-512 and production code that must run on Arm servers and older x86. Because the implementation is Apache-2 licensed and integrated into Highway, downstream projects can adopt it without reimplementing 3000 lines of platform-specific intrinsics. Operational impact appears first in query planners that repeatedly sort filter results or build indexes on numeric columns.
Within twelve months columnar stores and analytics runtimes that embed Highway will expose the new sort path behind existing APIs, raising single-core sort bandwidth above 800 MB/s on current server silicon.
AXIOM: Highway Quicksort appears in production Arrow builds and delivers measured sort rates above 800 MB/s on ARM Neoverse servers by Q4 2023.
Sources (3)
- [1]Primary Source(https://opensource.googleblog.com/2022/06/Vectorized-and-performance-portable-Quicksort.html)
- [2]Highway Library(https://github.com/google/highway)
- [3]Vectorized Quicksort AVX-512(https://arxiv.org/abs/2008.11320)