mbox series

[v6,0/6] Use introsort for qsort

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

Message

Adhemerval Zanella Netto July 18, 2023, 2:15 p.m. UTC 
The main motivation to use introsort is to make it fully AS-Safe and
AC-Safe, with a limited stack size requirement, to remove the use
of malloc (which troublesome since it seems some program 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, rather I used a well understood introsort (used on
libstdc++, for instance) and leverage the current quicksort
implementation along with a heapsort one from Linux kernel.

Performance-wise, the introsort does fall short compare to
mergesort [1].  I have not added the benchmark because I see that
this should not be focus of this patch. I have added some simple
optimization, also used by Linux kernel heapsort.

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 (6):
  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      | 337 +++++++++++++++++++++++++++++++++-----------
 stdlib/tst-qsort3.c | 298 +++++++++++++++++++++++++++++++++++++++
 8 files changed, 562 insertions(+), 399 deletions(-)
 delete mode 100644 stdlib/msort.c
 create mode 100644 stdlib/tst-qsort3.c