qsort improvements

[Paul Eggert]

On 8/31/21 4:55 AM, Adhemerval Zanella wrote:

> I think about using introsort using current quicksort along with the
> optimization to optimize the element swaps.  On the patchset I sent
> I added some benchmarks and although it can't be mergesort as expected,
> I think the performance tradeoff is acceptable.

Oh, I wasn't aware of the azanella/qsort-refactor branch.

Looking at it briefly, I have my doubts about the performance tradeoff, 
as heapsort (and therefore introsort) can have reasonably bad 
performance for some important special cases that may not have been 
benchmarked there.

Memory allocation within the Linux kernel is understandably frowned 
upon, so it makes sense to avoid memory-hungry algorithms like mergesort 
there. In contrast, it's generally better to trade space for speed in 
user programs.

I believe this is why Swift changed from introsort to timsort a couple 
of years ago. See some benchmarks here, which make timsort look pretty 
good compared to introsort, at least in the Swift ecosystem:

https://gist.github.com/natecook1000/5161e10aeba09408c130284ea6ec4e11

Also, I doubt whether async-signal-safety is an important attribute for 
qsort: portable code can't call qsort from signal handlers anyway, and I 
doubt whether much significant unportable code needs that feature in glibc.