Improvement of Dual-Pivot Quicksort (Radix sort)

[Vladimir Yaroslavskiy]

Hi,
 
I’d like to share new improvement of Dual-Pivot Quicksort: new algorithm of sorting, Radix sort,
is suggested. Also performance was improved in case of corner merging of runs. The changes are:
 
Sorting:
- adopt radix sort for sequential and parallel sorts on int/long/float/double arrays (almost random and length > 6K)
- fix tryMergeRuns() to better handle case when the last run is a single element
- minor javadoc and comment changes
Testing:
- add new data inputs in tests for sorting
- add min/max/infinity values to float/double testing
- add tests for radix sort
 
See related JDB and PR
https://bugs.openjdk.java.net/browse/JDK-8266431
https://github.com/openjdk/jdk/pull/3938
 
Laurent Bourges has tested new version of Dual-Pivot Quicksort, it shows better performance.
 
--- STATS ---
Comparing sorters SYSTEM vs NEW_DPQS_REF
winners : 75 / 197
avg (%): 125.5317
stats (%): [360: µ=146.05562 σ=106.212036 rms=252.26765 min=29.021154 max=618.46735]
Stats per keys:
IDENT_____:SPIRAL stats (%): [12: µ=146.85367 σ=67.929474 rms=214.78313 min=81.47126 max=301.9469]
IDENT_____:STAGGER stats (%): [12: µ=124.82189 σ=85.498825 rms=210.32072 min=81.963005 max=395.48715]
IDENT_____:SAWTOTH stats (%): [12: µ=121.015236 σ=48.471672 rms=169.48691 min=92.21825 max=227.12547]
IDENT_____:_RANDOM stats (%): [12: µ=235.53735 σ=204.9386 rms=440.47595 min=84.627625 max=613.981]
IDENT_____:PLATEAU stats (%): [12: µ=99.05677 σ=1.7938316 rms=100.85061 min=95.937035 max=100.65806]
IDENT_____:SHUFFLE stats (%): [12: µ=91.41511 σ=19.296474 rms=110.71158 min=57.53845 max=117.839775]
REVERSE___:SPIRAL stats (%): [12: µ=214.24744 σ=86.17577 rms=300.42322 min=90.77709 max=355.51056]
REVERSE___:STAGGER stats (%): [12: µ=127.6578 σ=87.32062 rms=214.97841 min=94.24164 max=404.43817]
REVERSE___:SAWTOTH stats (%): [12: µ=121.37123 σ=39.691704 rms=161.06294 min=95.34109 max=209.51929]
REVERSE___:_RANDOM stats (%): [12: µ=251.44595 σ=221.17654 rms=472.6225 min=86.738144 max=618.46735]
REVERSE___:PLATEAU stats (%): [12: µ=104.74188 σ=6.7017303 rms=111.44361 min=97.345634 max=120.3795]
REVERSE___:SHUFFLE stats (%): [12: µ=100.18308 σ=19.42561 rms=119.608696 min=69.78542 max=135.48901]
DITHER____:SPIRAL stats (%): [12: µ=183.42812 σ=64.67034 rms=248.09845 min=99.713776 max=268.3382]
DITHER____:STAGGER stats (%): [12: µ=174.41586 σ=123.18825 rms=297.60413 min=99.123314 max=459.56564]
DITHER____:SAWTOTH stats (%): [12: µ=187.5975 σ=110.62237 rms=298.21988 min=97.2715 max=367.14056]
DITHER____:_RANDOM stats (%): [12: µ=185.65709 σ=129.0605 rms=314.7176 min=70.168724 max=434.8079]
DITHER____:PLATEAU stats (%): [12: µ=100.72014 σ=3.9355173 rms=104.655655 min=94.559074 max=107.78911]
DITHER____:SHUFFLE stats (%): [12: µ=86.45017 σ=42.46921 rms=128.91939 min=29.021154 max=171.31981]
REVERSE_BA:SPIRAL stats (%): [12: µ=177.85292 σ=85.1786 rms=263.03152 min=94.477264 max=315.87576]
REVERSE_BA:STAGGER stats (%): [12: µ=132.4794 σ=103.280464 rms=235.75987 min=97.76542 max=460.07227]
REVERSE_BA:SAWTOTH stats (%): [12: µ=110.42876 σ=23.894398 rms=134.32315 min=98.04496 max=182.87247]
REVERSE_BA:_RANDOM stats (%): [12: µ=223.70018 σ=185.21355 rms=408.91373 min=86.62554 max=618.0156]
REVERSE_BA:PLATEAU stats (%): [12: µ=99.096275 σ=1.8192571 rms=100.91553 min=95.90717 max=100.805466]
REVERSE_BA:SHUFFLE stats (%): [12: µ=101.3669 σ=22.24021 rms=123.60711 min=65.73001 max=144.21266]
REVERSE_FR:SPIRAL stats (%): [12: µ=190.94035 σ=74.251236 rms=265.1916 min=97.7578 max=358.39563]
REVERSE_FR:STAGGER stats (%): [12: µ=134.06009 σ=104.719696 rms=238.77979 min=98.797386 max=466.2626]
REVERSE_FR:SAWTOTH stats (%): [12: µ=110.6682 σ=27.3231 rms=137.9913 min=94.27639 max=195.0114]
REVERSE_FR:_RANDOM stats (%): [12: µ=248.0682 σ=201.4303 rms=449.4985 min=97.789764 max=614.1303]
REVERSE_FR:PLATEAU stats (%): [12: µ=99.416336 σ=7.2677627 rms=106.6841 min=87.80682 max=115.78382]
REVERSE_FR:SHUFFLE stats (%): [12: µ=96.97448 σ=18.399363 rms=115.37385 min=64.20668 max=130.8938]
 
https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/2021/2105-final
 
Radix Sort benchmark
https://github.com/bourgesl/radix-sort-benchmark/blob/main/results/2021-ref/cmp-16-1M-global-final-2.log
 
Thank you,
Vladimir