[PATCH v3 0/7] Use introsort for qsort

Adhemerval Zanella adhemerval.zanella@linaro.org
Fri Sep 3 17:11:37 GMT 2021


This is respin from my previous attempt to fix and improve qsort() [1].
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 (along with the system memory checks), and keeping Worst-case
performance on 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 and simple on ((introsort,
used on libstdc++) and leverage the current quicksort implementation
along with a heapsort one from Linux kernel.

The resulting implementation has bounded stack requirement (about 1.8k
on x86_64), and results in an simplified code and binary:

# master
$ size stdlib/qsort.o stdlib/msort.o
   text    data     bss     dec     hex filename
   1316       0       0    1316     524 stdlib/qsort.o
   2045       0      12    2057     809 stdlib/msort.o

# patched
$ size stdlib/qsort.os
   text    data     bss     dec     hex filename
   2373       0       0    2373     945 stdlib/qsort.os

The performance difference with the provided benchmark clearly show the
tradeoff of using a instrosort over a mergesort.  The results are on
a Ryzen 9 with gcc 11 ran with --nelem 49152:786432:8388608 (to simulate
the L1/L2/L3 of this CPU used):

SORTED
  elements=    49152 (size= 4): %52.47% (master=3654381.0 patches=5571774.0)
  elements=   786432 (size= 4): %57.39% (master=73067211.0 patches=115003964.0)
  elements=  8388608 (size= 4): %49.71% (master=1005357374.0 patches=1505144332.0)
  elements=    49152 (size= 8): %48.98% (master=3796489.0 patches=5656023.0)
  elements=   786432 (size= 8): %52.34% (master=75809561.0 patches=115491584.0)
  elements=  8388608 (size= 8): %49.97% (master=1004201712.0 patches=1506017512.0)
  elements=    49152 (size=32): %-2.69% (master=11191649.0 patches=10891084.0)
  elements=   786432 (size=32): %-12.16% (master=238870746.0 patches=209822358.0)
  elements=  8388608 (size=32): %-23.33% (master=3323248933.0 patches=2547848399.0)
MOSTLYSORTED
  elements=    49152 (size= 4): %66.47% (master=6915979.0 patches=11512945.0)
  elements=   786432 (size= 4): %66.48% (master=143188170.0 patches=238379284.0)
  elements=  8388608 (size= 4): %70.90% (master=1805703842.0 patches=3086011963.0)
  elements=    49152 (size= 8): %78.11% (master=6836231.0 patches=12176330.0)
  elements=   786432 (size= 8): %77.79% (master=138851879.0 patches=246867806.0)
  elements=  8388608 (size= 8): %77.70% (master=1773884617.0 patches=3152112348.0)
  elements=    49152 (size=32): %-6.44% (master=13766992.0 patches=12880888.0)
  elements=   786432 (size=32): %-15.19% (master=287590899.0 patches=243919593.0)
  elements=  8388608 (size=32): %-25.63% (master=3852042869.0 patches=2864641676.0)
RANDOM
  elements=    49152 (size= 4): %9.54% (master=15078260.0 patches=16516457.0)
  elements=   786432 (size= 4): %5.64% (master=305805587.0 patches=323043450.0)
  elements=  8388608 (size= 4): %2.78% (master=3838340458.0 patches=3945202718.0)
  elements=    49152 (size= 8): %13.75% (master=14676586.0 patches=16694499.0)
  elements=   786432 (size= 8): %10.71% (master=295583560.0 patches=327252646.0)
  elements=  8388608 (size= 8): %7.67% (master=3722946692.0 patches=4008563091.0)
  elements=    49152 (size=32): %-8.34% (master=20944462.0 patches=19196696.0)
  elements=   786432 (size=32): %-14.31% (master=425822838.0 patches=364896701.0)
  elements=  8388608 (size=32): %-19.86% (master=5534217212.0 patches=4435276362.0)
REPEATED
  elements=    49152 (size= 4): %9.18% (master=14051610.0 patches=15341610.0)
  elements=   786432 (size= 4): %6.01% (master=282787457.0 patches=299777700.0)
  elements=  8388608 (size= 4): %4.19% (master=3539279291.0 patches=3687517777.0)
  elements=    49152 (size= 8): %12.37% (master=13659340.0 patches=15349336.0)
  elements=   786432 (size= 8): %11.11% (master=273070595.0 patches=303413116.0)
  elements=  8388608 (size= 8): %8.46% (master=3424739041.0 patches=3714521094.0)
  elements=    49152 (size=32): %-11.21% (master=19826230.0 patches=17603795.0)
  elements=   786432 (size=32): %-16.73% (master=405322605.0 patches=337501658.0)
  elements=  8388608 (size=32): %-21.93% (master=5261140329.0 patches=4107591456.0)
BITONIC
  elements=    49152 (size= 4): %405.43% (master=4632011.0 patches=23411611.0)
  elements=   786432 (size= 4): %493.28% (master=92649410.0 patches=549674361.0)
  elements=  8388608 (size= 4): %609.03% (master=1095591416.0 patches=7768102251.0)
  elements=    49152 (size= 8): %402.05% (master=4672695.0 patches=23459484.0)
  elements=   786432 (size= 8): %480.60% (master=94419035.0 patches=548197066.0)
  elements=  8388608 (size= 8): %596.41% (master=1116631167.0 patches=7776333333.0)
  elements=    49152 (size=32): %-6.92% (master=11545720.0 patches=10747100.0)
  elements=   786432 (size=32): %-14.97% (master=245037969.0 patches=208357373.0)
  elements=  8388608 (size=32): %-24.14% (master=3357712042.0 patches=2547221807.0)

With the bitonic and sorted showing the biggest hit.  Even though, I
think the tradeoff is acceptable.  The improvements over sizes larger
than 8 is mostly due the optimization done on swap operations.

[1] https://sourceware.org/pipermail/libc-alpha/2018-August/096981.html

Adhemerval Zanella (7):
  benchtests: Add bench-qsort
  support: Fix getopt_long with CMDLINE_OPTIONS
  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)

 benchtests/Makefile         |   2 +-
 benchtests/bench-qsort.c    | 195 +++++++++++++++++++++
 manual/argp.texi            |   2 +-
 manual/locale.texi          |   3 +-
 manual/search.texi          |   7 +-
 stdlib/Makefile             |   3 +-
 stdlib/msort.c              | 310 ---------------------------------
 stdlib/qsort.c              | 333 ++++++++++++++++++++++++++++--------
 support/support_test_main.c |   1 -
 support/test-driver.h       |   1 +
 10 files changed, 460 insertions(+), 397 deletions(-)
 create mode 100644 benchtests/bench-qsort.c
 delete mode 100644 stdlib/msort.c

-- 
2.30.2



More information about the Libc-alpha mailing list