BlockQuicksort: How Branch Mispredictions don't affect Quicksort

imbalanced). Of course, skewing the pivot is not what you want to do. You should rather look at sorting algorithms which don't suffer from branch mispredictions (as much), such as pdqsort, super-scalar sample sort [1,2] or block quicksort [3] [1] excellent paper on a parallel in-place adaptation by some of my colleagues: https://arxiv.org/abs/1705.02257 - code will become available soon [2] my less sophisticated implementation: https://github.com/lorenzhs/ssssort/, I also have a version using pdqsort as base case sorter, which is faster: https://github.com/lorenzhs/ssssort/blob/pdq/speed.pdf (in that plot, ssssort = super scalar sample sort with pdqsort as base case) [3] https://arxiv.org/abs/1604.06697, implementation at https://github.com/weissan/BlockQuicksort - pdqsort uses the same technique

marry a limited number of sorting-networks, insertion sort and the bi-directional merge into one, very fast but binary size and compile time efficient package is novel. Or that with LLVM you can do 2 instead of 4 writes per loop iteration in the bi-directional merge, which Igor has now ported back to his stuff as well. Generally I'd say my work has been more about figuring out novel ways to combine existing ideas into one good cohesive package fit for a standard library sort implementation. As well as taking ideas that work in the C and C++ world and doing the legwork to adapt them for use in Rust, which requires a lot more considerations and a lot of code can't be ported straight up. I wrote a little more about that in another comment here.

unpredictable. The problem is severe to the extent that with branchful quicksort, uneven split with more recursion is faster than even split, because it makes branches more predictable! Exact penalty is hardware microarchitecture specific, but one report is 20:80 split being optimal. So... you should use branchless quicksort! The technique was pioneered by an implementation called BlockQuicksort, but pdqsort (for pattern-defeating quicksort) https://arxiv.org/abs/2106.05123 is also popular. pdqsort incorporates branchless technique and also includes other enhancements. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step (2017) https://abseil.io/blog/20180927-swisstables Hash table is the workhorse of data structures, and while improvements are possible for specific usage patterns, open addressing with linear probing is still the fastest implementation for general purpose. So called "Swiss Table" combines cache-friendly metadata layout with SIMD-enhanced probing. These two optimizations work well with each other and combination of two is particularly effective.

(https://arxiv.org/abs/1705.02257, code: https://github.com/SaschaWitt/ips4o) or for a simpler algorithm that's still much faster than quicksort in most cases, blockquicksort (https://arxiv.org/abs/1604.06697, code: https://github.com/weissan/BlockQuicksort). Note that both papers were published in the last two years :) Of course these algorithms are much more complex and error-prone to implement and use some additional memory, which may explain why they're not used in standard library implementations of popular languages.