mbox series

[v4,0/6] Use introsort for qsort

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

Message

Adhemerval Zanella Netto July 11, 2023, 7:07 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.

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

Adhemerval Zanella (6):
  stdlib: Optimization qsort{_r} swap implementation (BZ 19305)
  stdlib: Move insertion sort out qsort
  stdlib: qsort: Move some macros to inline function
  stdlib: Implement introsort with qsort
  stdlib: Remove use of mergesort on qsort (BZ 21719)
  stdlib: Add more qsort{_r} coverage

 manual/argp.texi    |   2 +-
 manual/locale.texi  |   3 +-
 manual/search.texi  |   7 +-
 stdlib/Makefile     |   3 +-
 stdlib/msort.c      | 309 ----------------------------------------
 stdlib/qsort.c      | 338 ++++++++++++++++++++++++++++++++++----------
 stdlib/tst-qsort3.c | 298 ++++++++++++++++++++++++++++++++++++++
 7 files changed, 566 insertions(+), 394 deletions(-)
 delete mode 100644 stdlib/msort.c
 create mode 100644 stdlib/tst-qsort3.c