Re: [PATCH v8 0/7] Use introsort for qsort

[Noah Goldstein <goldstein.w.n@gmail.com>]

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.