4 ms·
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
by nostrademons 4y ago
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.
- jeffbee 4y agoThe blog post does seem to be quite explicit about the fact that their contribution is in the field of portability, not novelty.
- janwas 4y agoInteresting, 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.
- convolvatron 4y agonothing happened before google https://dl.acm.org/doi/10.1145/113379.113380 https://dl.acm.org/doi/10.1145/113379.113380
- janwas 4y agohah, our paper actually cites "Radix sort for vector multiprocessors" by the same author, also from 1991 :)