rustc SIGILL since qsort_r patches

[Florian Weimer]

* Florian Weimer:

> * Stepan Golosunov:
>
>> On Tue, Nov 07, 2023 at 02:04:09PM +0100, Florian Weimer wrote:
>>> * Adhemerval Zanella Netto:
>>> 
>>> > On 07/11/23 08:09, Florian Weimer wrote:
>>> >> * Adhemerval Zanella Netto:
>>> >> 
>>> >>> Just a side note that the quicksort implementation was also used for
>>> >>> size (number of elements times size per element) larger than the
>>> >>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or
>>> >>> whether malloc fails.  So it is a latent issue, that did not trigger
>>> >>> before by chance.  
>>> >> 
>>> >> Is it ever beneficial to call the comparison function with identical
>>> >> pointers, though?
>>> >
>>> > Afaik this how introsort works, and I am not aware of any comparison
>>> > sort with O(1) worst-case space complexity that does not require
>>> > a comparison callback that work as <=>.
>>> 
>>> I think the LLVM code will only assert if it is called with equal
>>> pointers, as the array elements are expected to be distinct (hence the
>>> assert).
>>> 
>>> My question is more along these lines: If the pointers are equal, does
>>> it make sense to perform the indirection function call?  I guess that
>>> depends on the nature of the comparison function.
>>> 
>>> I'm not sure where equal-pointers call happens, but why wouldn't
>>> something like this be an overall win?
>>> 
>>>   while (k <= n / 2)
>>>     {
>>>       size_t j = 2 * k;
>>
>> Shouldn't this be
>>
>>       size_t j = 2 * k + 1;
>>
>> instead? Looks like the existing formula is designed for base-1
>> arrays.
>
> Not sure, Adhemerval?
>
> Obtaining the parent index would need adjusting then as well, right?

I have isolated a test from stdlib/qsort.c and can confirm that
heapsort_r does not actually reliably sort.  Application-side, this does
not sort in a mis-sort because of the insertion at the end, but the
qsort is substantially slower against adversial inputs than the old
implementation because it performs many more comparisons.  It clearly
shows quadratic behavior.

I'm going to try to fix the heapsort implementation.

Thanks,
Florian