Google researchers publish portable Quicksort designed for faster numeric sorting
The Apache 2-licensed implementation uses portable SIMD functions across six instruction sets and three CPU architectures, with reported speeds of up to 1GB/s on one CPU core.
Google researchers have released open-source code for a vectorised Quicksort that sorts numeric arrays substantially faster than C++’s standard library algorithm, std::sort.
The implementation uses Highway’s portable SIMD functions across six instruction sets and three CPU architectures. It supports numeric inputs ranging from 16 to 128 bits, extending beyond earlier architecture-specific approaches focused on 32-bit integers.
The method applies SIMD operations to Quicksort’s partitioning stage, which accounts for much of the algorithm’s processing time. It uses compress-store instructions where available and equivalent permute instructions on other systems, while a specialised method handles arrays of up to 256 elements.
Google Research said the code is aimed at workloads using columnar data layouts, where values from individual database columns are stored together to improve filtering and sorting for SQL queries.
In reported tests, the implementation processed one million numbers at rates of up to 1,123 megabytes per second on a 3GHz Intel Skylake processor using AVX-512. On the same CPU with AVX2, it reached 798MB/s, compared with 699MB/s for a prior AVX2-optimised implementation.
Against the standard library on that AVX2 system, reported results ranged from nine to 19 times faster depending on the number type. The figures are benchmark results for specified hardware and workloads, rather than a general performance guarantee. The source code is available under the Apache 2 licence.
