Fwd: Re: Re[2]: Adaptive insertion sort in DualPivot Quicksort

[Vladimir Yaroslavskiy]

Hi Vladimir,

I performed lots of benchmarks:

1. I updated my own sort-bench (jmh based) and run many tests (all distributions + permutations) on integer arrays for sizes = 50, 100, 150, 200, 500, 1000, 2000:

In this benchmark, the metric is (minimum + stddev) and it gives the overall score: in average, the new DPQS is 7% faster
Comparing sorters DPQ_19_05_01 vs DPQ_19_08_09
winners  : 349 / 321
stats (%): [1115: µ=107.99222 σ=45.746456 rms=153.73868 min=62.684937 max=524.28424]

Full results are available:
https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/2019.08/sort-50-2000-stats.out

2. I ran Vladimir's test (from  https://github.com/iaroslavski/sorting ):

Before (07/24):
# Data type = int, Sorting type = sequential, Length = 150
test_name;jdk_time;dpqs_time;gain
random;1867.00;2074.00;-0.11
equal;224.00;98.00;0.56
ascending;476.00;112.00;0.76
descending;1185.00;260.00;0.78
period[4];564.00;782.00;-0.39
period[5];610.00;1076.00;-0.76
period[6];710.00;1028.00;-0.45
stagger[15];1788.00;2316.00;-0.30
stagger[24];709.00;1028.00;-0.45
stagger[33];2020.00;1934.00;0.04
shuffle[6];1624.00;1218.00;0.25
shuffle[7];1347.00;1189.00;0.12
shuffle[8];1345.00;1085.00;0.19
TOTAL;14469.00;14200.00;0.02

Patched (08/14):
# Data type = int, Sorting type = sequential, Length = 150
test_name;jdk_time;dpqs_time;gain
random;1881.00;1860.00;0.01
equal;223.00;98.00;0.56
ascending;478.00;111.00;0.77
descending;1192.00;262.00;0.78
period[4];564.00;660.00;-0.17
period[5];613.00;1014.00;-0.65
period[6];713.00;968.00;-0.36
stagger[15];1787.00;1893.00;-0.06
stagger[24];712.00;969.00;-0.36
stagger[33];2021.00;1890.00;0.06
shuffle[6];1618.00;1185.00;0.27
shuffle[7];1361.00;1129.00;0.17
shuffle[8];1341.00;1094.00;0.18
TOTAL;14504.00;13133.00;0.09

In conclusion, I confirm Vladimir's gain on my laptop (Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz):
size = 150, char, was: 0.02 -> new: 0.09

Finally both benchmarks agree 7% gain !

Cheers,
Laurent