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

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

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>