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

[Kuan-Wei Chiu <visitorckw@gmail.com>]

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.

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


Best regards,
Kuan-Wei Chiu