Vectorized and performance-portable Quicksort (2022)

summary

Google researchers have developed a vectorized Quicksort implementation that is up to ten times faster than the C++ standard library. This speedup is achieved by leveraging SIMD instructions to accelerate the partitioning process, which is the most time-consuming part of sorting. By using the Highway library, the implementation remains portable across various CPU architectures like x86 and Arm without requiring architecture-specific code for every platform. The resulting system supports a wide range of input sizes and outperforms previous specialized sorting algorithms.

key points

1. The core speedup comes from using SIMD instructions, specifically the compress-store operation, to partition arrays more efficiently than scalar operations. When compress-store is not available, the system emulates it using permute instructions to maintain high performance.
2. The Highway library allows a single C++ implementation to be portable across six different instruction sets. This removes the need to write thousands of lines of of architecture-specific assembly or C++ while still utilizing the best available CPU instructions.
3. Benchmark results show significant performance gains across different hardware, reaching speeds of up to 1 GB/s on a single CPU core. This outperforms not only the standard library but also prior state-of-the-art algorithms optimized for specific architectures.

who should read it

Software engineers and system architects who need to optimize high-performance data processing, particularly those working with columnar databases or large-scale numerical sorting.

discussion positive