[PATCH] stdlib: Optimize number of calls to comparison function

[Adhemerval Zanella Netto]

On 06/12/23 07:21, Florian Weimer wrote:
> * Zack Weinberg:
> 
>> On Mon, Dec 4, 2023, at 1:31 PM, Kuan-Wei Chiu wrote:
>>> On Mon, Dec 04, 2023 at 09:20:50AM +0100, Florian Weimer wrote:
>>>> I think the factor in stdlib/tst-qsort5.c needs to be adjusted:
>>>>
>>>>   /* This is an arbitrary factor which is true for the current
>>>>      implementation across a wide range of sizes.  */
>>>>   TEST_VERIFY (factor <= 4.5);
>>>
>>> It seems that the factor can be adjusted to around 3.5. I can send
>>> another patch for this adjustment or resend it as a patch series.
>>
>> Before you go any further with this patch series I think we need to
>> decide whether our backward compatibility constraints mean our qsort
>> has to be a stable sort.  If so, we should make it *always* be a
>> stable sort and write that into the documentation, and that would
>> mean junking the entire heapsort implementation.
> 
> That makes sense, although there might not exist an in-place sorting
> algorithm that takes constant extra space regardless of element count
> and element size and has reasonable performance.  Maybe we could say,
> “stable if element size is less than 1024 bytes” or something like that.
> 
> What I'm concerned about is that with the current implementation, we
> take a performance hit *and* have compatibility problems.  The
> compatibility problems would be easier to justify if we actually made
> things faster.  Not calling malloc internally is unlikely to be
> compelling to programmers.

My initial intention was to remove internal multiple sorting strategies
that has different semantics and that might eventually trigger corner
cases issues (the stable default mergesort versus the fallback quicksort),
and fix the quicksort fallback that had the long standing issue of O(n^2) 
on adversarial inputs.

However it seems that glibc qsort now become an instance on Hyrum's law,
where it does not really matter that neither POSIX nor C standard promised 
sorting stability.

So I presume it would be better to keep with mergesort for all input sizes,
along with the limited stack buffer (so there is no failure point up a 
certain input number/size); and fallback to heapsort on memory allocation
failure.  I will prepare a patch to restore it.

Other system does provide mergesort as a different symbol [1], which also
returns a failure is case memory can not be allocated.  But I don't think
it would be an improvement in this situation (no one will really adapt
their code to use mergesort if a stable allocation is required).  I also
though about adding a tunable to enable mergesort on qsort, but it would
ending up only add more complexity and required more testing.

[1] https://man.freebsd.org/cgi/man.cgi?query=mergesort&sektion=3