rustc SIGILL since qsort_r patches

rustc SIGILL since qsort_r patches

[Cristian Rodríguez]

[-- Attachment #1: Type: text/plain, Size: 1052 bytes --]

Hi:

After quite some head scratching I found the recent qsort_r patches
triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)

happens compiling anything in release mode with any toolchain (stable,
beta, nightly)

#0  0x000015129e40516a in int
llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void
const*, void const*) () from
/home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/
libLLVM-17-rust-1.75.0-nightly.so

#1  0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80,
total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized
out>) at qsort.c:335

#2  0x000015129e4df6e6 in
llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*,
llvm::MachineBasicBlock*, unsigned int) () from
/home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/
libLLVM-17-rust-1.75.0-nightly.so

git head == bad
2.38   == good

Main interest is to know if I am not alone and if anyone else has observed
this problem so far.
Thanks..

Re: rustc SIGILL since qsort_r patches

[Andrew Pinski]

On Sat, Nov 4, 2023 at 5:55 PM Cristian Rodríguez <cristian@rodriguez.im> wrote:
>
> Hi:
>
> After quite some head scratching I found the recent qsort_r patches triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
>
> happens compiling anything in release mode with any toolchain (stable, beta, nightly)
>
> #0  0x000015129e40516a in int llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void const*, void const*) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so
>
> #1  0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80, total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized out>) at qsort.c:335
>
> #2  0x000015129e4df6e6 in llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, unsigned int) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so
>

I think this is a bug in LLVM's
BranchFolder::MergePotentialsElt::operator< code:
See: https://llvm.org/doxygen/BranchFolding_8cpp_source.html

Specifically it has the following comment:
// _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
489 // an object with itself.
490#ifndef _GLIBCXX_DEBUG
491 llvm_unreachable("Predecessor appears twice");
492#else
493 return false;
494#endif

Well glibc's qsort implementation will also now compare with itself.

Thanks,
Andrew

> git head == bad
> 2.38   == good
>
> Main interest is to know if I am not alone and if anyone else has observed this problem so far.
> Thanks..

Re: rustc SIGILL since qsort_r patches

[Andrew Pinski]

On Sat, Nov 4, 2023 at 6:10 PM Andrew Pinski <pinskia@gmail.com> wrote:
>
> On Sat, Nov 4, 2023 at 5:55 PM Cristian Rodríguez <cristian@rodriguez.im> wrote:
> >
> > Hi:
> >
> > After quite some head scratching I found the recent qsort_r patches triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
> >
> > happens compiling anything in release mode with any toolchain (stable, beta, nightly)
> >
> > #0  0x000015129e40516a in int llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void const*, void const*) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so
> >
> > #1  0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80, total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized out>) at qsort.c:335
> >
> > #2  0x000015129e4df6e6 in llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, unsigned int) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so
> >
>
> I think this is a bug in LLVM's
> BranchFolder::MergePotentialsElt::operator< code:
> See: https://llvm.org/doxygen/BranchFolding_8cpp_source.html
>
> Specifically it has the following comment:
> // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
> 489 // an object with itself.
> 490#ifndef _GLIBCXX_DEBUG
> 491 llvm_unreachable("Predecessor appears twice");
> 492#else
> 493 return false;
> 494#endif
>
> Well glibc's qsort implementation will also now compare with itself.

Also qsort comparison is not exactly < but rather <=>  which
array_pod_sort_comparator tries to emulate but
BranchFolder::MergePotentialsElt::operator< specifically calls
unreachable if 2 are things are equal.

>
> Thanks,
> Andrew
>
> > git head == bad
> > 2.38   == good
> >
> > Main interest is to know if I am not alone and if anyone else has observed this problem so far.
> > Thanks..

Re: rustc SIGILL since qsort_r patches

[Cristian Rodríguez]

[-- Attachment #1: Type: text/plain, Size: 473 bytes --]

On Sat, Nov 4, 2023 at 10:13 PM Andrew Pinski <pinskia@gmail.com> wrote:

>
> > Well glibc's qsort implementation will also now compare with itself.
>
> Also qsort comparison is not exactly < but rather <=>  which
> array_pod_sort_comparator tries to emulate but
> BranchFolder::MergePotentialsElt::operator< specifically calls
> unreachable if 2 are things are equal.
>
>
>
Thank you, filled a bug report.
https://github.com/llvm/llvm-project/issues/71312

Re: rustc SIGILL since qsort_r patches

[Adhemerval Zanella Netto]

On 04/11/23 22:10, Andrew Pinski wrote:
> On Sat, Nov 4, 2023 at 5:55 PM Cristian Rodríguez <cristian@rodriguez.im> wrote:
>>
>> Hi:
>>
>> After quite some head scratching I found the recent qsort_r patches triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
>>
>> happens compiling anything in release mode with any toolchain (stable, beta, nightly)
>>
>> #0  0x000015129e40516a in int llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void const*, void const*) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so
>>
>> #1  0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80, total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized out>) at qsort.c:335
>>
>> #2  0x000015129e4df6e6 in llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, unsigned int) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so
>>
> 
> I think this is a bug in LLVM's
> BranchFolder::MergePotentialsElt::operator< code:
> See: https://llvm.org/doxygen/BranchFolding_8cpp_source.html
> 
> Specifically it has the following comment:
> // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
> 489 // an object with itself.
> 490#ifndef _GLIBCXX_DEBUG
> 491 llvm_unreachable("Predecessor appears twice");
> 492#else
> 493 return false;
> 494#endif
> 
> Well glibc's qsort implementation will also now compare with itself.
> 
> Thanks,
> Andrew
> 
>> git head == bad
>> 2.38   == good
>>
>> Main interest is to know if I am not alone and if anyone else has observed this problem so far.
>> Thanks..


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.  

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

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

This change is going to have annoying consequences for backwards
compatibility.

Thanks,
Florian

Re: rustc SIGILL since qsort_r patches

[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 <=>.

> 
> This change is going to have annoying consequences for backwards
> compatibility.
> 
> Thanks,
> Florian
> 

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

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

Re: rustc SIGILL since qsort_r patches

[Adhemerval Zanella Netto]

On 07/11/23 10:04, 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?

Ah right, it looks reasonable to me yes. 

> 
>   while (k <= n / 2)
>     {
>       size_t j = 2 * k;
>       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
> 

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

* Florian Weimer:

> 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;
>       if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0)
>       j++;
>
> +     if (k ==j)
> +       continue;

That should be a break, not a 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;
>     }

And I think we need it because we entire undefined terrority: we end up
calling __memswap with identical pointers.

Florian

Re: rustc SIGILL since qsort_r patches

[Adhemerval Zanella Netto]

On 07/11/23 10:13, Florian Weimer wrote:
> * Florian Weimer:
> 
>> 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;
>>       if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0)
>>       j++;
>>
>> +     if (k ==j)
>> +       continue;
> 
> That should be a break, not a 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;
>>     }
> 
> And I think we need it because we entire undefined terrority: we end up
> calling __memswap with identical pointers.

Fair enough, could you send a patch?

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

* Adhemerval Zanella Netto:

>> And I think we need it because we entire undefined terrority: we end up
>> calling __memswap with identical pointers.
>
> Fair enough, could you send a patch?

Sure, I'll send something later today.

Florian

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

* Cristian Rodríguez:

> After quite some head scratching I found the recent qsort_r patches
> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
>
> happens compiling anything in release mode with any toolchain (stable,
> beta, nightly)

Could you share more details about your environment?  I'm trying to
reproduce it to see which code paths we need to fix.

Thanks,
Florian

Re: rustc SIGILL since qsort_r patches

[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.


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

Re: rustc SIGILL since qsort_r patches

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

Thanks,
Florian

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

* Florian Weimer:

> * Cristian Rodríguez:
>
>> After quite some head scratching I found the recent qsort_r patches
>> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
>>
>> happens compiling anything in release mode with any toolchain (stable,
>> beta, nightly)
>
> Could you share more details about your environment?  I'm trying to
> reproduce it to see which code paths we need to fix.

I have just pushed what I think is a workaround.  Would you please check
if it fixes your LLVM/rustc issue?

Thanks,
Florian

Re: rustc SIGILL since qsort_r patches

[Cristian Rodríguez]

[-- Attachment #1: Type: text/plain, Size: 763 bytes --]

On Wed, Nov 8, 2023 at 11:19 AM Florian Weimer <fweimer@redhat.com> wrote:

> * Florian Weimer:
>
> > * Cristian Rodríguez:
> >
> >> After quite some head scratching I found the recent qsort_r patches
> >> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
> >>
> >> happens compiling anything in release mode with any toolchain (stable,
> >> beta, nightly)
> >
> > Could you share more details about your environment?  I'm trying to
> > reproduce it to see which code paths we need to fix.
>
> I have just pushed what I think is a workaround.  Would you please check
> if it fixes your LLVM/rustc issue?
>
> Thanks,
> Florian
>
> I will try it in the environment when it hits the build pipes and report
back.
Thanks.

Re: rustc SIGILL since qsort_r patches

[Cristian Rodríguez]

[-- Attachment #1: Type: text/plain, Size: 988 bytes --]

On Wed, Nov 8, 2023 at 4:56 PM Cristian Rodríguez <cristian@rodriguez.im>
wrote:

>
>
> On Wed, Nov 8, 2023 at 11:19 AM Florian Weimer <fweimer@redhat.com> wrote:
>
>> * Florian Weimer:
>>
>> > * Cristian Rodríguez:
>> >
>> >> After quite some head scratching I found the recent qsort_r patches
>> >> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
>> >>
>> >> happens compiling anything in release mode with any toolchain (stable,
>> >> beta, nightly)
>> >
>> > Could you share more details about your environment?  I'm trying to
>> > reproduce it to see which code paths we need to fix.
>>
>> I have just pushed what I think is a workaround.  Would you please check
>> if it fixes your LLVM/rustc issue?
>>
>> Thanks,
>> Florian
>>
>> I will try it in the environment when it hits the build pipes and report
> back.
> Thanks.
>

It successfully papers over llvm's bug..which has since also been fixed.
Thank you and keep up !

Re: rustc SIGILL since qsort_r patches

[Adhemerval Zanella Netto]

On 09/11/23 08:49, Cristian Rodríguez wrote:
> 
> 
> On Wed, Nov 8, 2023 at 4:56 PM Cristian Rodríguez <cristian@rodriguez.im <mailto:cristian@rodriguez.im>> wrote:
> 
> 
> 
>     On Wed, Nov 8, 2023 at 11:19 AM Florian Weimer <fweimer@redhat.com <mailto:fweimer@redhat.com>> wrote:
> 
>         * Florian Weimer:
> 
>         > * Cristian Rodríguez:
>         >
>         >> After quite some head scratching I found the recent qsort_r patches
>         >> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2)
>         >>
>         >> happens compiling anything in release mode with any toolchain (stable,
>         >> beta, nightly)
>         >
>         > Could you share more details about your environment?  I'm trying to
>         > reproduce it to see which code paths we need to fix.
> 
>         I have just pushed what I think is a workaround.  Would you please check
>         if it fixes your LLVM/rustc issue?
> 
>         Thanks,
>         Florian
> 
>     I will try it in the environment when it hits the build pipes and report back.
>     Thanks. 
> 
> 
> It successfully papers over llvm's bug..which has since also been fixed.
> Thank you and keep up !
> 
>  


Thanks for brings this up as well.

Re: 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

Re: 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.

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

* Adhemerval Zanella Netto:

> 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.

Try this input array:

0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18,
58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36,
82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13,
15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49,
51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85,
87, 89, 91, 93, 95, 97, 98, 99

I count 2645 comparisons.

This is unrelated to the heapsort bugs, for which I have a fix.  The
heapsort function isn't even called.

The bulk of the comparisons happen before the insertion sort phase,
which looks correct, so the handover to heapsort for adversarial input
isn't happening.

Thanks,
Florian

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

* Florian Weimer:

> * Adhemerval Zanella Netto:
>
>> 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.
>
> Try this input array:
>
> 0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18,
> 58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36,
> 82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13,
> 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49,
> 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85,
> 87, 89, 91, 93, 95, 97, 98, 99
>
> I count 2645 comparisons.
>
> This is unrelated to the heapsort bugs, for which I have a fix.  The
> heapsort function isn't even called.
>
> The bulk of the comparisons happen before the insertion sort phase,
> which looks correct, so the handover to heapsort for adversarial input
> isn't happening.

Depth decrement is missing when descending into the companion partition
of a small partition.

Fixing that exposes more heap sort problems unfortunately.  Looking …

Thanks,
Florian

Re: rustc SIGILL since qsort_r patches

[Florian Weimer]

* Florian Weimer:

> * Florian Weimer:
>
>> * Adhemerval Zanella Netto:
>>
>>> 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.
>>
>> Try this input array:
>>
>> 0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18,
>> 58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36,
>> 82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13,
>> 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49,
>> 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85,
>> 87, 89, 91, 93, 95, 97, 98, 99
>>
>> I count 2645 comparisons.
>>
>> This is unrelated to the heapsort bugs, for which I have a fix.  The
>> heapsort function isn't even called.
>>
>> The bulk of the comparisons happen before the insertion sort phase,
>> which looks correct, so the handover to heapsort for adversarial input
>> isn't happening.
>
> Depth decrement is missing when descending into the companion partition
> of a small partition.
>
> Fixing that exposes more heap sort problems unfortunately.  Looking …

I think I found all the issues.  Need to write up the tests still.

Thanks,
Florian

Re: rustc SIGILL since qsort_r patches

[Adhemerval Zanella]

> On 17 Nov 2023, at 13:17, Florian Weimer <fweimer@redhat.com> wrote:
> 
> * Florian Weimer:
> 
>> * Florian Weimer:
>> 
>>> * Adhemerval Zanella Netto:
>>> 
>>>> 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.
>>> 
>>> Try this input array:
>>> 
>>> 0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18,
>>> 58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36,
>>> 82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13,
>>> 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49,
>>> 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85,
>>> 87, 89, 91, 93, 95, 97, 98, 99
>>> 
>>> I count 2645 comparisons.
>>> 
>>> This is unrelated to the heapsort bugs, for which I have a fix.  The
>>> heapsort function isn't even called.
>>> 
>>> The bulk of the comparisons happen before the insertion sort phase,
>>> which looks correct, so the handover to heapsort for adversarial input
>>> isn't happening.
>> 
>> Depth decrement is missing when descending into the companion partition
>> of a small partition.
>> 
>> Fixing that exposes more heap sort problems unfortunately.  Looking …
> 
> I think I found all the issues.  Need to write up the tests still.
> 
> Thanks,
> Florian

Thanks for working on this!