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

[Florian Weimer]

* Kuan-Wei Chiu:

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

Based on the paper, I would have expected a greater reduction.

>> On the other hand, the heapsort code is not really expected to run at
>> all in the current implementation because median-of-three quicksort
>> usually avoids degenerating behavior.  If this heapsort variant uses a
>> number of comparisons that is competitive to quicksort, maybe we should
>> use it instead?  And use insertion sort for short arrays only.
>> 
>
> This patch currently reduces the comparison count only in scenarios
> where deep recursion results in a fallback to heapsort. According to
> the referenced paper, beyond n >= 16000, the comparison count of
> bottom-up heapsort is lower than that of median-of-three quicksort.
> However, my concern is that quicksort typically exhibits better
> locality of reference, making it more cache-friendly, while heapsort
> lacks this advantage.

Yes, the performance numbers I posted suggest that something like that
is at play here.  Even though heapsort with your patch performs fewer
comparisons to most other implementations we have floating around
(except the historic merge sort), it is still slower than most.

Thanks,
Florian