[v8,0/7] Use introsort for qsort

  The motivation for using introsort is to make it fully AS-safe and
AC-Safe, with a limited stack size requirement, to remove the use of
malloc (which is troublesome since it seems some programs do longjmp
from the callback comparison program), and keep worst-case scenario
bounded to O(n*ln(n)) (instead of potentially quadradic as for the
quicksort).

The implementation does not aim to be the state-of-the-art sort
algorithm, instead it uses used a well-understood introsort (used on
libstdc++, for instance) and leveraged the current quicksort
implementation along with a heapsort one from Linux kernel.

Performance-wise, the introsort does fall short compared to the
mergesort [1].  I have not added a benchmark because I think this should
not be the focus of this patch.

Changes from v7:
- Move __memswap to a static inline on its own header.
- Improve some comments.

Changes from v6:
- Added internal __memswap symbol.
- Improved tst-qsort3 with a reference implementation and a new
  duplicated input.

Changes from v5:
- Rewrite heapsort to a custom implementation.
- Use may_alias attribute on swap optimization.

Changes from v4
- Use enum for swap function selection.
- Simplify is_aligned.
- Renamed insertsort.

PS: this is a update for
https://sourceware.org/pipermail/libc-alpha/2023-October/151887.html
which should be ignored.

Adhemerval Zanella (7):
  string: Add internal memswap implementation
  stdlib: Optimization qsort{_r} swap implementation
  stdlib: Move insertion sort out qsort
  stdlib: qsort: Move some macros to inline function
  stdlib: Implement introsort for qsort (BZ 19305)
  stdlib: Remove use of mergesort on qsort (BZ 21719)
  stdlib: Add more qsort{_r} coverage

 include/stdlib.h          |   2 -
 manual/argp.texi          |   2 +-
 manual/locale.texi        |   3 +-
 manual/search.texi        |   7 +-
 stdlib/Makefile           |   3 +-
 stdlib/msort.c            | 309 --------------------------------
 stdlib/qsort.c            | 318 +++++++++++++++++++++++++--------
 stdlib/tst-qsort3.c       | 366 ++++++++++++++++++++++++++++++++++++++
 string/Makefile           |  12 ++
 string/test-memswap.c     | 192 ++++++++++++++++++++
 sysdeps/generic/memswap.h |  41 +++++
 11 files changed, 856 insertions(+), 399 deletions(-)
 delete mode 100644 stdlib/msort.c
 create mode 100644 stdlib/tst-qsort3.c
 create mode 100644 string/test-memswap.c
 create mode 100644 sysdeps/generic/memswap.h
  

On Tue, Oct 3, 2023 at 5:22 AM Adhemerval Zanella
<adhemerval.zanella@linaro.org> wrote:
>
> The motivation for using introsort is to make it fully AS-safe and
> AC-Safe, with a limited stack size requirement, to remove the use of
> malloc (which is troublesome since it seems some programs do longjmp
> from the callback comparison program), and keep worst-case scenario
> bounded to O(n*ln(n)) (instead of potentially quadradic as for the
> quicksort).
>
> The implementation does not aim to be the state-of-the-art sort
> algorithm, instead it uses used a well-understood introsort (used on
> libstdc++, for instance) and leveraged the current quicksort
> implementation along with a heapsort one from Linux kernel.
>
> Performance-wise, the introsort does fall short compared to the
> mergesort [1].  I have not added a benchmark because I think this should
> not be the focus of this patch.
>
> Changes from v7:
> - Move __memswap to a static inline on its own header.
> - Improve some comments.
>
> Changes from v6:
> - Added internal __memswap symbol.
> - Improved tst-qsort3 with a reference implementation and a new
>   duplicated input.
>
> Changes from v5:
> - Rewrite heapsort to a custom implementation.
> - Use may_alias attribute on swap optimization.
>
> Changes from v4
> - Use enum for swap function selection.
> - Simplify is_aligned.
> - Renamed insertsort.
>
> PS: this is a update for
> https://sourceware.org/pipermail/libc-alpha/2023-October/151887.html
> which should be ignored.
>
> Adhemerval Zanella (7):
>   string: Add internal memswap implementation
>   stdlib: Optimization qsort{_r} swap implementation
>   stdlib: Move insertion sort out qsort
>   stdlib: qsort: Move some macros to inline function
>   stdlib: Implement introsort for qsort (BZ 19305)
>   stdlib: Remove use of mergesort on qsort (BZ 21719)
>   stdlib: Add more qsort{_r} coverage
>
>  include/stdlib.h          |   2 -
>  manual/argp.texi          |   2 +-
>  manual/locale.texi        |   3 +-
>  manual/search.texi        |   7 +-
>  stdlib/Makefile           |   3 +-
>  stdlib/msort.c            | 309 --------------------------------
>  stdlib/qsort.c            | 318 +++++++++++++++++++++++++--------
>  stdlib/tst-qsort3.c       | 366 ++++++++++++++++++++++++++++++++++++++
>  string/Makefile           |  12 ++
>  string/test-memswap.c     | 192 ++++++++++++++++++++
>  sysdeps/generic/memswap.h |  41 +++++
>  11 files changed, 856 insertions(+), 399 deletions(-)
>  delete mode 100644 stdlib/msort.c
>  create mode 100644 stdlib/tst-qsort3.c
>  create mode 100644 string/test-memswap.c
>  create mode 100644 sysdeps/generic/memswap.h
>
> --
> 2.34.1
>
Minus the nit about the memswap changes, this series looks good.
  

On 03/10/23 15:13, Noah Goldstein wrote:
> On Tue, Oct 3, 2023 at 5:22 AM Adhemerval Zanella
> <adhemerval.zanella@linaro.org> wrote:
>>
>> The motivation for using introsort is to make it fully AS-safe and
>> AC-Safe, with a limited stack size requirement, to remove the use of
>> malloc (which is troublesome since it seems some programs do longjmp
>> from the callback comparison program), and keep worst-case scenario
>> bounded to O(n*ln(n)) (instead of potentially quadradic as for the
>> quicksort).
>>
>> The implementation does not aim to be the state-of-the-art sort
>> algorithm, instead it uses used a well-understood introsort (used on
>> libstdc++, for instance) and leveraged the current quicksort
>> implementation along with a heapsort one from Linux kernel.
>>
>> Performance-wise, the introsort does fall short compared to the
>> mergesort [1].  I have not added a benchmark because I think this should
>> not be the focus of this patch.
>>
>> Changes from v7:
>> - Move __memswap to a static inline on its own header.
>> - Improve some comments.
>>
>> Changes from v6:
>> - Added internal __memswap symbol.
>> - Improved tst-qsort3 with a reference implementation and a new
>>   duplicated input.
>>
>> Changes from v5:
>> - Rewrite heapsort to a custom implementation.
>> - Use may_alias attribute on swap optimization.
>>
>> Changes from v4
>> - Use enum for swap function selection.
>> - Simplify is_aligned.
>> - Renamed insertsort.
>>
>> PS: this is a update for
>> https://sourceware.org/pipermail/libc-alpha/2023-October/151887.html
>> which should be ignored.
>>
>> Adhemerval Zanella (7):
>>   string: Add internal memswap implementation
>>   stdlib: Optimization qsort{_r} swap implementation
>>   stdlib: Move insertion sort out qsort
>>   stdlib: qsort: Move some macros to inline function
>>   stdlib: Implement introsort for qsort (BZ 19305)
>>   stdlib: Remove use of mergesort on qsort (BZ 21719)
>>   stdlib: Add more qsort{_r} coverage
>>
>>  include/stdlib.h          |   2 -
>>  manual/argp.texi          |   2 +-
>>  manual/locale.texi        |   3 +-
>>  manual/search.texi        |   7 +-
>>  stdlib/Makefile           |   3 +-
>>  stdlib/msort.c            | 309 --------------------------------
>>  stdlib/qsort.c            | 318 +++++++++++++++++++++++++--------
>>  stdlib/tst-qsort3.c       | 366 ++++++++++++++++++++++++++++++++++++++
>>  string/Makefile           |  12 ++
>>  string/test-memswap.c     | 192 ++++++++++++++++++++
>>  sysdeps/generic/memswap.h |  41 +++++
>>  11 files changed, 856 insertions(+), 399 deletions(-)
>>  delete mode 100644 stdlib/msort.c
>>  create mode 100644 stdlib/tst-qsort3.c
>>  create mode 100644 string/test-memswap.c
>>  create mode 100644 sysdeps/generic/memswap.h
>>
>> --
>> 2.34.1
>>
> Minus the nit about the memswap changes, this series looks good.

Thanks for the review, may I get reviewed-by ;) ?
  

On Fri, Oct 27, 2023 at 3:25 PM Adhemerval Zanella Netto
<adhemerval.zanella@linaro.org> wrote:
>
>
>
> On 03/10/23 15:13, Noah Goldstein wrote:
> > On Tue, Oct 3, 2023 at 5:22 AM Adhemerval Zanella
> > <adhemerval.zanella@linaro.org> wrote:
> >>
> >> The motivation for using introsort is to make it fully AS-safe and
> >> AC-Safe, with a limited stack size requirement, to remove the use of
> >> malloc (which is troublesome since it seems some programs do longjmp
> >> from the callback comparison program), and keep worst-case scenario
> >> bounded to O(n*ln(n)) (instead of potentially quadradic as for the
> >> quicksort).
> >>
> >> The implementation does not aim to be the state-of-the-art sort
> >> algorithm, instead it uses used a well-understood introsort (used on
> >> libstdc++, for instance) and leveraged the current quicksort
> >> implementation along with a heapsort one from Linux kernel.
> >>
> >> Performance-wise, the introsort does fall short compared to the
> >> mergesort [1].  I have not added a benchmark because I think this should
> >> not be the focus of this patch.
> >>
> >> Changes from v7:
> >> - Move __memswap to a static inline on its own header.
> >> - Improve some comments.
> >>
> >> Changes from v6:
> >> - Added internal __memswap symbol.
> >> - Improved tst-qsort3 with a reference implementation and a new
> >>   duplicated input.
> >>
> >> Changes from v5:
> >> - Rewrite heapsort to a custom implementation.
> >> - Use may_alias attribute on swap optimization.
> >>
> >> Changes from v4
> >> - Use enum for swap function selection.
> >> - Simplify is_aligned.
> >> - Renamed insertsort.
> >>
> >> PS: this is a update for
> >> https://sourceware.org/pipermail/libc-alpha/2023-October/151887.html
> >> which should be ignored.
> >>
> >> Adhemerval Zanella (7):
> >>   string: Add internal memswap implementation
> >>   stdlib: Optimization qsort{_r} swap implementation
> >>   stdlib: Move insertion sort out qsort
> >>   stdlib: qsort: Move some macros to inline function
> >>   stdlib: Implement introsort for qsort (BZ 19305)
> >>   stdlib: Remove use of mergesort on qsort (BZ 21719)
> >>   stdlib: Add more qsort{_r} coverage
> >>
> >>  include/stdlib.h          |   2 -
> >>  manual/argp.texi          |   2 +-
> >>  manual/locale.texi        |   3 +-
> >>  manual/search.texi        |   7 +-
> >>  stdlib/Makefile           |   3 +-
> >>  stdlib/msort.c            | 309 --------------------------------
> >>  stdlib/qsort.c            | 318 +++++++++++++++++++++++++--------
> >>  stdlib/tst-qsort3.c       | 366 ++++++++++++++++++++++++++++++++++++++
> >>  string/Makefile           |  12 ++
> >>  string/test-memswap.c     | 192 ++++++++++++++++++++
> >>  sysdeps/generic/memswap.h |  41 +++++
> >>  11 files changed, 856 insertions(+), 399 deletions(-)
> >>  delete mode 100644 stdlib/msort.c
> >>  create mode 100644 stdlib/tst-qsort3.c
> >>  create mode 100644 string/test-memswap.c
> >>  create mode 100644 sysdeps/generic/memswap.h
> >>
> >> --
> >> 2.34.1
> >>
> > Minus the nit about the memswap changes, this series looks good.
>
> Thanks for the review, may I get reviewed-by ;) ?

LGTM with nit about memswap tests.

Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>