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

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

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 ;) ?