[nostrademons]

It's not new within Google either. I remember poking through Jeff Dean's original MapReduce code (written c. 2003) and finding a SIMD-based QuickSort that was the in-memory portion of the external sort algorithm.

It looks like this algorithm is interesting in the specifics of how it works, eg. the use of a compress-store instruction for partitioning. The algorithm I mentioned above mostly focused on speeding up comparisons through the use of SIMD instructions, rather than changing the partitioning part of the QuickSort algorithm itself. Not sure how that compares to djbsort, I didn't see technical details of the algorithm on the page.

[janwas]

Interesting, I did not know that, thanks for the pointer. There is also an effort underway to update LLVM std::sort to BlockQuicksort, which can use some SIMD instructions similarly to what you describe.

[jeffbee]

The blog post does seem to be quite explicit about the fact that their contribution is in the field of portability, not novelty.

[convolvatron]

nothing happened before google

https://dl.acm.org/doi/10.1145/113379.113380

[janwas]

hah, our paper actually cites "Radix sort for vector multiprocessors" by the same author, also from 1991 :)