RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]

[Vladimir Yaroslavskiy]

On Sun, 21 Apr 2024 04:37:45 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> Hello Vamsi (@vamsi-parasa),
>> 
>> Could you please run the new benchmarking?
>> To save time and don't patch JDK several times, I've created JavaBenchmarkHarness
>> class which is under package java.util and compares several versions of DPQS.
>> Also I prepared several versions of current sorting source from JDK to detect what is going wrong.
>> 
>> What you need is to compile and run JavaBenchmarkHarness once:
>> 
>> javac --patch-module java.base=. -d classes *.java
>> java -XX:CompileThreshold=1 -XX:-TieredCompilation --patch-module java.base=classes -cp classes java.util.JavaBenchmarkHarness
>> 
>> Find the sources there:
>> 
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java  
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_ins.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_mrg.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_piv.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_prt.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r29p.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r29p5.java
>> 
>> Thank you,
>> Vladimir
>
> Hi Vladimir (@iaroslavski),
> 
> Please see the data below:
> 
> Thanks,
> Vamsi
> 
> 
> 
> name | builder | size | mode | count | score
> -- | -- | -- | -- | -- | --
> b01 | RANDOM | 600 | avg | 325677 | 6.862
> b01 | RANDOM | 3000 | avg | 52041 | 82.233
> b01 | RANDOM | 90000 | avg | 1217 | 4456.51
> b01 | RANDOM | 400000 | avg | 242 | 22923.28
> b01 | RANDOM | 1000000 | avg | 90 | 60598.84
> b01 | REPEATED | 600 | avg | 651354 | 1.933
> b01 | REPEATED | 3000 | avg | 104083 | 13.753
> b01 | REPEATED | 90000 | avg | 2435 | 723.039
> b01 | REPEATED | 400000 | avg | 484 | 3084.416
> b01 | REPEATED | 1000000 | avg | 180 | 8234.428
> b01 | STAGGER | 600 | avg | 1954062 | 1.005
> b01 | STAGGER | 3000 | avg | 312251 | 4.945
> b01 | STAGGER | 90000 | avg | 7305 | 133.126
> b01 | STAGGER | 400000 | avg | 1453 | 592.144
> b01 | STAGGER | 1000000 | avg | 542 | 1493.876
> b01 | SHUFFLE | 600 | avg | 325677 | 5.12
> b01 | SHUFFLE | 3000 | avg | 52041 | 29.252
> b01 | SHUFFLE | 90000 | avg | 1217 | 1396.664
> b01 | SHUFFLE | 400000 | avg | 242 | 5743.489
> b01 | SHUFFLE | 1000000 | avg | 90 | 15490.81
> b01_ins | RANDOM | 600 | avg | 325677 | 7.594
> b01_ins | RANDOM | 3000 | avg | 52041 | 78.631
> b01_ins | RANDOM | 90000 | avg | 1217 | 4312.511
> b01_ins | RANDOM | 400000 | avg | 242 | 22108.18
> b01_ins | RANDOM | 1000000 | avg | 90 | 58467.16
> b01_ins | REPEATED | 600 | avg | 651354 | 1.569
> b01_ins | REPEATED | 3000 | avg | 104083 | 11.313
> b01_ins | REPEATED | 90000 | avg | 2435 | 720.838
> b01_ins | REPEATED | 400000 | avg | 484 | 3003.673
> b01_ins | REPEATED | 1000000 | avg | 180 | 8144.944
> b01_ins | STAGGER | 600 | avg | 1954062 | 0.98
> b01_ins | STAGGER | 3000 | avg | 312251 | 4.948
> b01_ins | STAGGER | 90000 | avg | 7305 | 132.909
> b01_ins | STAGGER | 400000 | avg | 1453 | 592.572
> b01_ins | STAGGER | 1000000 | avg | 542 | 1492.627
> b01_ins | SHUFFLE | 600 | avg | 325677 | 4.092
> b01_ins | SHUFFLE | 3000 | avg | 52041 | 27.138
> b01_ins | SHUFFLE | 90000 | avg | 1217 | 1304.326
> b01_ins | SHUFFLE | 400000 | avg | 242 | 5465.745
> b01_ins | SHUFFLE | 1000000 | avg | 90 | 14585.08
> b01_mrg | RANDOM | 600 | avg | 325677 | 7.139
> b01_mrg | RANDOM | 3000 | avg | 52041 | 81.01
> b01_mrg | RANDOM | 90000 | avg | 1217 | 4266.084
> b01_mrg | RANDOM | 400000 | avg | 242 | 21937.77
> b01_mrg | RANDOM | 1000000 | avg | 90 | 58177.72
> b01_mrg | REPEATED | 600 | avg | 651354 | 1.36
> b01_mrg | REPEATED | 3000 | avg | 104083 | 9.013
> b01_mrg | REPEATED | 90000 | avg | 2435 | 737.684
> b01_mrg | REPEATED | 400000 | avg | 484 | 3152.447
> b01_mrg | REPEATED | 1000000 | avg |...

Hello Vamsi (@vamsi-parasa),

Could you please run the new benchmarking to detect the best case
for Radix sort and parallel sorting?

What you need is to compile and run JavaBenchmarkHarness:

javac --patch-module java.base=. -d classes *.java
java -XX:CompileThreshold=1 -XX:-TieredCompilation --patch-module java.base=classes -cp classes java.util.JavaBenchmarkHarness

Find the sources there:

https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_a.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_11.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_12.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_13.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_14.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_21.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_23.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java

Thank you,
Vladimir

-------------

PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-2087504178