Re: rustc SIGILL since qsort_r patches

[Florian Weimer <fweimer@redhat.com>]

* 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?

Thanks,
Florian