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

["Zack Weinberg" <zack@owlfolio.org>]

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.

I do not have a strong opinion either way, but I do think it should
either *always* or *never* be stable, i.e. not the previous state of
"whether you get a stable sort depends on the size of the input and
various other undocumented factors."  Also, I think that the
behavior should not depend on which version of glibc a program
was compiled against.

zw