Google's portable Quicksort hits 1 GB/s, 19x faster than std::sort
We've created the first vectorized Quicksort
Google open-sourced a vectorized Quicksort that sorts 1 million numbers at up to 1.1 GB/s on a single Skylake core, 9–19x faster than C++ std::sort. Using Highway's portable SIMD, it runs on six instruction sets across three architectures—including AVX2, AVX-512, and Arm NEON—and outperforms architecture-specific implementations while supporting 16- to 128-bit inputs.
Previously, sorting has been considered expensive. We are interested to see what new applications and capabilities will be unlocked by being able to sort at 1 GB/s on a single CPU core.
- zX41ZdbW
Strange to see it here, the article is quite old.
Since pdqsort, vqsort, and glide sort, the current state-of-the-art are driftsort and ipnsort.
I've integrated them into ClickHouse: https://github.com/ClickHouse/ClickHouse/pull/106650
- bee_rider
Well, it came out a while ago, so maybe we can be a bit silly:
There’s something sort of beautiful about mergesort and heapsort. Their names tell you what their main idea is, and how they work is immediately obvious.
Quicksort, on the other hand, has nothing beautiful about it and is named after it’s one redeeming feature (that it is quick for a lot of cases).
- minitech
Actual title: “Vectorized and performance-portable Quicksort” (2022).
Actual sense in which it’s first:
> Happily, modern instruction sets (Arm SVE, RISC-V V, x86 AVX-512) include a special instruction suitable for partitioning. Given a separate input of yes/no values (whether an element is less than the pivot), this "compress-store" instruction stores to consecutive memory only the elements whose corresponding input is "yes". We can then logically negate the yes/no values and apply the instruction again to write the elements to the other partition. This strategy has been used in an AVX-512-specific Quicksort. But what about other instruction sets such as AVX2 that don't have compress-store? Previous work has shown how to emulate this instruction using permute instructions.
> We build on these techniques to achieve the first vectorized Quicksort that is portable to six instruction sets across three architectures, and in fact outperforms prior architecture-specific sorts.