mbox series

[v7,0/7] Use introsort for qsort

Message ID 20230914183704.1386534-1-adhemerval.zanella@linaro.org
Headers show
Series Use introsort for qsort | expand

Message

Adhemerval Zanella Netto Sept. 14, 2023, 6:36 p.m. UTC 
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 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.

[1]
https://sourceware.org/pipermail/libc-alpha/2021-September/130698.html

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 -
 include/string.h      |   3 +
 manual/argp.texi      |   2 +-
 manual/locale.texi    |   3 +-
 manual/search.texi    |   7 +-
 stdlib/Makefile       |   3 +-
 stdlib/msort.c        | 309 -----------------------------------
 stdlib/qsort.c        | 315 +++++++++++++++++++++++++++---------
 stdlib/tst-qsort3.c   | 366 ++++++++++++++++++++++++++++++++++++++++++
 string/Makefile       |  13 ++
 string/memswap.c      |  41 +++++
 string/test-memswap.c | 191 ++++++++++++++++++++++
 12 files changed, 856 insertions(+), 399 deletions(-)
 delete mode 100644 stdlib/msort.c
 create mode 100644 stdlib/tst-qsort3.c
 create mode 100644 string/memswap.c
 create mode 100644 string/test-memswap.c