Further improvements to quicksort implementation of qsort

[statham-arm]

llvm-libc's qsort, the Quicksort version, works but is not especially polished.

In a recent PR (#110849) @michaelrj-google observed that more of the functions in the quicksort headers should be marked with LIBC_INLINE, so that the top-level qsort function doesn't incur any internal function-call overheads except when actually recursing.

It might also be worth considering other standard optimizations commonly used in quicksort algorithms (after benchmarking to make sure they really are improvements):

• make sure we have the best choice of partitioning strategy. Currently we always pick the element in the middle, which at least behaves reasonably if the input list is already mostly sorted (better than picking the start or end element). But median of (start, middle, end) is a common choice; maybe that's better?
• consider not recursing right down to lists of size 2, but instead, stop when every remaining sublist has size at most 8 or 16 or something like that, and then finish up with a pass of insertion sort
• adopt "introsort", a variation of quicksort in which you detect when your sublists aren't getting smaller fast enough, and switch over to heapsort. That way you still keep most of quicksort's good constant factor, but remove the quadratic-time worst case, because that's the case where heapsort takes over.

[Rajveer100]

I think adding randomness would be a nice choice. We can pick a random index during the partition and then swap it with the end element, the probability of a good complexity would be pretty high, i.e, close to its best case.

Yeah, at this point intro sort is pretty much used everywhere in most standard libraries, I did see tim sort in some cases too.

What do you think of dual-pivot though?

[statham-arm]

Dual pivot is outside my experience, I'm afraid.

One downside of random pivot selection is that it can affect the output order, in the presence of elements whose keys compare equal. Quicksort is already not stable – it won't guarantee to leave equal-keyed elements in their original order – but it seems particularly bad if it doesn't even leave them in a deterministic order if you run exactly the same sort twice. You could imagine that breaking repeatability of some test case you were debugging, for example.

[Rajveer100]

It's about the chances, it's less predictable to have a really bad case.

For making it stable we could use additional O(n) space by pairing elements, like (x, i).

[llvmbot]

@llvm/issue-subscribers-libc

Author: Simon Tatham (statham-arm)

llvm-libc's `qsort`, the Quicksort version, works but is not especially polished.

In a recent PR (#110849) @michaelrj-google observed that more of the functions in the quicksort headers should be marked with LIBC_INLINE, so that the top-level qsort function doesn't incur any internal function-call overheads except when actually recursing.

It might also be worth considering other standard optimizations commonly used in quicksort algorithms (after benchmarking to make sure they really are improvements):

• make sure we have the best choice of partitioning strategy. Currently we always pick the element in the middle, which at least behaves reasonably if the input list is already mostly sorted (better than picking the start or end element). But median of (start, middle, end) is a common choice; maybe that's better?
• consider not recursing right down to lists of size 2, but instead, stop when every remaining sublist has size at most 8 or 16 or something like that, and then finish up with a pass of insertion sort
• adopt "introsort", a variation of quicksort in which you detect when your sublists aren't getting smaller fast enough, and switch over to heapsort. That way you still keep most of quicksort's good constant factor, but remove the quadratic-time worst case, because that's the case where heapsort takes over.

[Voultapher]

I've stumbled on this issue while searching the qsort PR, and I think it can be closed as the original points are nearly all addressed by #120450

• Pivot selection uses state-of-the-art recursive median selection approaching optimal sqrt quality.
• A small-sort is a powerful optimization for C++ and Rust implementations that can inline the comparison function. For qsort in my testing even with a fixed size instantiation for a fast swap, doing insertion sort is slower than branchless partitioning.
• It does introsort for worst case O(N * log(N)) but goes even further with pdqsort style equal element filtering, giving O(N * log(K)) where K is the number of distinct values.

[statham-arm]

I agree that the serious improvements seem to have been made. However the motivation for me creating this issue in the first place was @michaelrj-google asking me to raise an issue to make sure everything was marked with LIBC_INLINE. And I see one qsort-related header file where that's still not true, namely libc/src/stdlib/qsort_pivot.h which has no LIBC_INLINE to be seen anywhere.