Review of the qsort situation

[Florian Weimer]

* Adhemerval Zanella Netto:

> On 04/12/23 10:08, Florian Weimer wrote:
>> Last week, I promised to look at the qsort situation.  I see two major
>> issues.
>> 
>> (a) Compatibility impact of the new implementation
>> 
>> We saw two different kinds of breakage in LLVM, a hang in 389-ds-base
>> (the LDAP server), and a test suite failure in notmuch.  I'm pretty sure
>> this is just the surface, and there is much breakage we don't know about
>> yet.  Particularly in proprietary software.
>> 
>> So we'd probably have to retain the old implementation and add a symbol
>> version.  Not great, but manageable.
>
> Are still compatibility issues besides the sort callback being called
> with same pointer (which should be fixed yet)?

Lack of stability is the major issue, and that's also not going to be
fixable.  But if qsort were actually faster, that might be a compelling
reason to deal with the compatibility fallout.

> In any case, this still a latent issues that was not triggered before
> because the quicksort was not taken in most cases.  On a memory pressure
> situation, the quicksort will be used and we caller will face the same
> compatibility issues.

Memory pressure is not relevant to short arrays.  The issues we saw
obviously were with short arrays.

>> I can try to gather more performance numbers, but I don't think this
>> looks good.  It's slower, and there are far-ranging compatibility
>> issues.  So I don't think this is the right direction.  If quicksort was
>> actually faster than mergesort, it might be a different discussion.
>
> Yes, the quicksort performance is usually worse than mergesort and I did
> advertise it on cover letter.

But that's really counter-intuitive.  Shouldn't quicksort be faster?

What if we specialize the implementation for pointer-sized values, so
that swapping does not require indirect calls or conditional branches?

> So we can add back a compatibility symbol or even just revert this change,
> but it does not fully solve the corner case issue on what to do if malloc
> fails. Should we abort, like gcc_sort does on gcc? Should we fallback to
> heapsort (it might the best option in this case)?

That doesn't seem unreasonable—it has a fairly compact implementation.

Thanks,
Florian