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

[Florian Weimer]

* 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.

Thanks,
Florian