Hi HN, this is a new implementation of the standard C qsort() function. It's faster than all other libc qsort() functions at least in my simple benchmarks.
The implementation is similar to the classic quicksort with three-way partitioning from Bentley and McIlroy (1993). It uses size specializations to get better performance: essentially there are independent implementations of quicksort for a variety of common element sizes. This allows an optimization that isn't normally possible with qsort(): the pivot is pulled out into a temporary leaving a hole in the array, and inversions are done by alternating between sides moving elements into the hole from one partition to another. This results in two thirds as many moves per inversion compared to swap.
This makes it faster than all current libc qsort() implementations: about ~7% faster than newlib which is next fastest. The downside is that the code size is larger, although that doesn't really matter for a shared libc.
These benchmarks are also interesting just for the comparisons between various qsort() implementations. The BSDs and newlib share a common base which is the classic three-way quicksort code. glibc and Wine use different mergesorts with memory allocation, musl uses smoothsort and uClibc uses shellsort.
1 comment
[ 3.9 ms ] story [ 13.6 ms ] threadThe implementation is similar to the classic quicksort with three-way partitioning from Bentley and McIlroy (1993). It uses size specializations to get better performance: essentially there are independent implementations of quicksort for a variety of common element sizes. This allows an optimization that isn't normally possible with qsort(): the pivot is pulled out into a temporary leaving a hole in the array, and inversions are done by alternating between sides moving elements into the hole from one partition to another. This results in two thirds as many moves per inversion compared to swap.
This makes it faster than all current libc qsort() implementations: about ~7% faster than newlib which is next fastest. The downside is that the code size is larger, although that doesn't really matter for a shared libc.
These benchmarks are also interesting just for the comparisons between various qsort() implementations. The BSDs and newlib share a common base which is the classic three-way quicksort code. glibc and Wine use different mergesorts with memory allocation, musl uses smoothsort and uClibc uses shellsort.