Re:10x Faster sort than C++ std:sort
by janwas on Saturday June 04, 2022 @01:37AM
(#31617323)
:)
Are you thinking of ips4o (sample sort)? That's about 2-3x std::sort. There's also a pending patch to std::sort that replaces it with BlockQuicksort which would narrow that gap.
We integrate vqsort into ips4o, calling it once subarrays fit in L2. That speeds up ips4o by 2.9x (single thread) and 1.6 (parallel - bandwidth limited). More details in the paper.
I previously also worked on radix sort: https://arxiv.org/abs/1008.2849
Interestingly, that 12 year old result on dual-socket/8 cores is only about twice as fast as a single AVX-512 core today.
We integrate vqsort into ips4o, calling it once subarrays fit in L2. That speeds up ips4o by 2.9x (single thread) and 1.6 (parallel - bandwidth limited). More details in the paper.
I previously also worked on radix sort: https://arxiv.org/abs/1008.2849 Interestingly, that 12 year old result on dual-socket/8 cores is only about twice as fast as a single AVX-512 core today.