rustc SIGILL since qsort_r patches

[Adhemerval Zanella Netto]

On 17/11/23 07:35, Florian Weimer wrote:
> * 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.

Indeed introsort is slower than the previous mergesort, but are you sure
is is quadratic?  Could you share the input that is triggering wrong 
behavior, I will try to improve testing to catch it.