Sorting is one of the most heavily studied problems in computer science, so a 10x speedup claim usually means a benchmark was chosen carefully. Jan Wassenberg’s writeup from Google Brain Computer Architecture Research makes the case that the win here is real, and that it comes from one structural observation rather than a new algorithm: in quicksort, comparisons were never the bottleneck. Partitioning is.

The mechanics:

  • SIMD operates on independent lanes, while sorting re-arranges adjacent elements — so the naive expectation is that vectorization cannot help.
  • Quicksort reduces to partitioning around a pivot, recursing, and sorting final blocks of ≤256 elements. Partitioning dominates CPU time, so that is the target.
  • Modern ISAs (AVX-512, Arm SVE, RISC-V V) include a compress-store: given a mask of yes/no values for “element is less than the pivot”, it writes only the masked-on elements to consecutive memory. Negate the mask, run it again, and the other partition is written.
  • AVX2 has no compress-store. Earlier work emulates it with permute instructions, and Highway picks compress-store where it exists and the emulation where it does not — so ~3,000 lines of C++ are not rewritten per platform.
  • The result is the first vectorized quicksort portable across six instruction sets and three architectures, and it widens coverage to 16-128 bit inputs where the previous best was 32-bit integers only.

The numbers, on one million values of 32/64/128 bits:

  • Apple M1 (Arm NEON): 499 / 471 / 466 MB/s
  • 3 GHz Skylake (AVX-512): 1123 / 1119 / 1120 MB/s
  • AVX2: 798 MB/s versus 699 MB/s for the prior AVX2-specific state of the art
  • std::sort on the same CPU: 58 / 128 / 117 MB/s — a 9-19x gap

The most interesting result is not “SIMD is fast”. It is that a single portable implementation outran hand-tuned per-architecture code. The old tradeoff — portability or peak performance — was absorbed by the abstraction layer instead of being paid by the developer, and the 1.4-1.6x jump from AVX2 to AVX-512 arrived at zero cost because the library dispatches on what the CPU actually supports at runtime.

The framing that sticks is about capability, not benchmarks. Sorting used to be expensive enough to design around; at roughly 1 GB/s on a single core it becomes a primitive you reach for without planning a workaround.