Re: rustc SIGILL since qsort_r patches

[Stepan Golosunov <stepan@golosunov.pp.ru>]

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.


>       if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0)
> 	j++;
> 
> +     if (k ==j)
> +      continue;
>       if (cmp (base + (k * size), base + (j * size), arg) >= 0)
> 	break;
> 
>       do_swap (base + (size * j), base + (k * size), size, swap_type);
>       k = j;
>     }
> 
> 
> Thanks,
> Florian
>