Vectorized and performance-portable Quicksort (2022)
Recorded: Sept. 17, 2026, 12:28 a.m.
| Original | Summarized |
1 opensource.google.com Menu Events Projects Programs and services Documentation About Blog Google Open Source Blog Vectorized and performance-portable Quicksort Thursday, June 2, 2022 Today we're sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort, and outperforms state of the art architecture-specific algorithms, while being portable across all modern CPU architectures. Below we discuss how we achieved this.First, some background. There is a recent trend towards columnar databases that consecutively store all values from a particular column, as opposed to storing all fields of a record or "row" before those of the next record. This can be faster to filter or sort, which are key building blocks for SQL queries; thus we focus on this data layout.Given that sorting has been heavily studied, how can we possibly find a 10x speedup? The answer lies in SIMD/vector instructions. These carry out operations on multiple independent elements in a single instruction—for example, operating on 16 float32 at once when using the AVX-512 instruction set, or four on Arm NEON:If you are already familiar with SIMD, you may have heard of it being used in supercomputers, linear algebra for machine learning applications, video processing, or image codecs such as JPEG XL. But if SIMD operations only involve independent elements, how can we sort them, which involves re-arranging adjacent array elements?Imagine we have some special way to sort, for instance 256 element arrays. Then, the Quicksort algorithm for sorting a larger array consists of partitioning it into two sub-arrays: those less than a "pivot" value (ideally the median), and all others; then recursing until a sub-array is at most 256 elements large, and using our special method for sorting those. Partitioning accounts for most of the CPU time, so if we can speed it up using SIMD, we have a fast sort. 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. Our implementation uses Highway's portable SIMD functions, so we do not have to re-implement about 3,000 lines of C++ for each platform. Highway uses compress-store when available and otherwise the equivalent permute instructions. In contrast to the previous state of the art—which was also specific to 32-bit integers—we support a full range of 16-128 bit inputs.Despite our single portable implementation, we reach record-setting speeds on both AVX2, AVX-512 (Intel Skylake) and Arm NEON (Apple M1). For one million 32/64/128-bit numbers, our code running on Apple M1 can produce sorted output at rates of 499/471/466 MB/s. On a 3 GHz Skylake with AVX-512, the speeds are 1123/1119/1120 MB/s. Interestingly, AVX-512 is 1.4-1.6 times as fast as AVX2 - a worthwhile speedup for zero additional effort (Highway checks what instructions are available on the CPU and uses the best available ones). When running on AVX2, we measure 798 MB/s, whereas the prior state of the art optimized for AVX2 only manages 699 MB/s. By comparison, the standard library reaches 58/128/117 MB/s on the same CPU, so we have managed a 9-19x speedup depending on the type of numbers.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. The Apache2-licensed source code is available on Github (feel free to open an issue if you have any questions or comments) and our paper offers a detailed explanation and evaluation of the implementation (including the special case for 256 elements).By Jan Wassenberg – Brain Computer Architecture Research Labels: SIMD , Sorting Search This Blog Popular Posts The Journey Begins: Meet the 2026 GSoC Contributors! Vectorized and performance-portable Quicksort Securing the agentic era: Introducing formal verification for CEL Shape the future with Google Summer of Code 2026! The End of an Era: Transitioning Away from Ingress NGINX Archive ► 2026 (43) ► September (1) ► August (3) ► July (2) ► June (10) ► May (3) ► April (9) ► March (5) ► February (5) ► January (5) ► 2025 (47) ► December (6) ► November (5) ► October (3) ► September (5) ► August (5) ► July (5) ► June (3) ► May (5) ► April (1) ► March (1) ► February (3) ► January (5) ► 2024 (39) ► December (4) ► November (1) ► October (1) ► September (3) ► August (4) ► July (4) ► June (4) ► May (5) ► April (4) ► March (2) ► February (6) ► January (1) ► 2023 (44) ► December (5) ► November (6) ► October (2) ► September (3) ► August (1) ► July (2) ► June (5) ► May (5) ► April (2) ► March (6) ► February (3) ► January (4) ▼ 2022 (44) ► December (4) ► November (2) ► October (7) ► September (6) ► August (2) ► July (3) ▼ June (5) Establishing new baselines: Identifying open sour... ► May (1) ► April (2) ► March (4) ► February (5) ► January (3) ► 2021 (55) ► December (3) ► November (7) ► October (4) ► September (7) ► August (5) ► June (2) ► May (2) ► April (6) ► March (6) ► February (8) ► January (5) ► 2020 (83) ► December (7) ► November (6) ► October (7) ► September (5) ► August (13) ► July (1) ► June (7) ► May (9) ► April (5) ► March (13) ► February (5) ► January (5) ► 2019 (65) ► December (6) ► November (9) ► October (8) ► September (5) ► August (3) ► July (5) ► June (4) ► May (8) ► April (3) ► March (7) ► February (4) ► January (3) ► 2018 (59) ► December (4) ► November (2) ► October (3) ► September (2) ► August (10) ► July (2) ► June (3) ► May (5) ► April (1) ► March (16) ► February (3) ► January (8) ► 2017 (73) ► December (4) ► November (5) ► October (6) ► September (7) ► August (3) ► July (3) ► June (3) ► May (5) ► April (4) ► March (13) ► February (7) ► January (13) ► 2016 (85) ► December (9) ► November (13) ► October (13) ► September (8) ► August (9) ► July (5) ► June (2) ► May (5) ► April (3) ► March (7) ► February (7) ► January (4) ► 2015 (80) ► December (5) ► November (7) ► October (6) ► September (6) ► August (4) ► July (1) ► June (6) ► May (6) ► April (10) ► March (10) ► February (11) ► January (8) ► 2014 (104) ► December (6) ► November (12) ► October (7) ► September (8) ► August (9) ► July (7) ► June (10) ► May (8) ► April (8) ► March (11) ► February (8) ► January (10) ► 2013 (100) ► December (7) ► November (10) ► October (8) ► September (9) ► August (10) ► July (7) ► June (7) ► May (8) ► April (10) ► March (9) ► February (7) ► January (8) ► 2012 (93) ► December (4) ► November (6) ► October (9) ► September (8) ► August (8) ► July (5) ► June (7) ► May (10) ► April (5) ► March (15) ► February (9) ► January (7) ► 2011 (117) ► December (7) ► November (14) ► October (13) ► September (10) ► August (6) ► July (13) ► June (11) ► May (5) ► April (11) ► March (10) ► February (10) ► January (7) ► 2010 (123) ► December (9) ► November (12) ► October (10) ► September (14) ► August (10) ► July (7) ► June (10) ► May (11) ► April (14) ► March (13) ► February (8) ► January (5) ► 2009 (124) ► December (6) ► November (5) ► October (11) ► September (11) ► August (8) ► July (13) ► June (6) ► May (11) ► April (16) ► March (17) ► February (10) ► January (10) ► 2008 (167) ► December (10) ► November (11) ► October (13) ► September (16) ► August (12) ► July (20) ► June (14) ► May (21) ► April (16) ► March (17) ► February (17) Share Google Privacy Terms . |
The presented work introduces a vectorized and performance-portable Quicksort algorithm designed to achieve significant speedups over standard sorting methods by leveraging Single Instruction, Multiple Data (SIMD) vector instructions. This optimization addresses the bottleneck inherent in sorting—particularly the partitioning phase—by employing parallel processing capabilities across multiple data elements simultaneously. The motivation stems from the trend in data management towards columnar databases, where fast sorting and filtering are critical operations, necessitating highly efficient sorting primitives. The core strategy involves applying SIMD operations, such as those found in AVX-512 or Arm NEON, to rearrange adjacent array elements. Although sorting involves re-arranging elements, the method focuses on partitioning the array into elements less than and greater than a pivot. This partitioning step, which consumes most of the CPU time, is optimized by using SIMD instructions that facilitate specialized data movement. Specifically, the method utilizes a "compress-store" instruction, which allows storing only the elements corresponding to a "yes" condition (elements less than the pivot) into consecutive memory locations. By logically negating these conditions and applying the operation again, the algorithm efficiently sorts into the two partitions. To ensure portability across diverse CPU architectures, including those with instruction sets lacking direct compress-store capabilities, the implementation relies on emulating this functionality using permute instructions. This approach allows the algorithm to maintain a unified implementation across six instruction sets across three major architectures. The developers utilized Highway's portable SIMD functions, which dynamically check for and utilize the most efficient available instructions, thereby avoiding the need to reimplement extensive C++ code for each platform. Furthermore, this implementation supports sorting arrays with 16, 128, and even 256-bit inputs, broadening its applicability beyond previous state-of-the-art methods, which were often limited to 32-bit integers. The resulting implementation demonstrates record-setting performance metrics when tested across different platforms. Running on the Apple M1, the code achieved sorting rates of approximately 499/471/466 megabytes per second for one million numbers. On an Intel Skylake processor utilizing AVX-512, speeds reached approximately 1123/1119/1120 megabytes per second. Performance evaluations indicated that the custom implementation achieved a speedup of 9 to 19 times compared to the standard library sort, depending on the numerical type. This performance level suggests that sorting at rates approaching one gigabyte per second on a single CPU core unlocks substantial new applications and capabilities. |