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

[Vladimir Yaroslavskiy]

On Mon, 6 May 2024 23:26:49 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> 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_5.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
>
> Hi Vladimir (@iaroslavski),
> 
> Please see the data below.
> 
> Thanks,
> Vamsi
> 
> name | builder | size | mode | count | score
> -- | -- | -- | -- | -- | --
> b01 | RANDOM | 600 | avg | 325677 | 6.764
> b01 | RANDOM | 3000 | avg | 52041 | 77.742
> b01 | RANDOM | 90000 | avg | 1217 | 4449.668
> b01 | RANDOM | 400000 | avg | 242 | 22764.05
> b01 | RANDOM | 1000000 | avg | 90 | 60737.71
> b01 | REPEATED | 600 | avg | 651354 | 1.723
> b01 | REPEATED | 3000 | avg | 104083 | 12.383
> b01 | REPEATED | 90000 | avg | 2435 | 714.451
> b01 | REPEATED | 400000 | avg | 484 | 3039.447
> b01 | REPEATED | 1000000 | avg | 180 | 8114.503
> b01 | SAWTOOTH | 600 | avg | 1954062 | 1.009
> b01 | SAWTOOTH | 3000 | avg | 312251 | 4.94
> b01 | SAWTOOTH | 90000 | avg | 7305 | 133.192
> b01 | SAWTOOTH | 400000 | avg | 1453 | 591.854
> b01 | SAWTOOTH | 1000000 | avg | 542 | 1494.252
> b01 | STAGGER | 600 | avg | 1954062 | 8.252
> b01 | STAGGER | 3000 | avg | 312251 | 10.449
> b01 | STAGGER | 90000 | avg | 7305 | 287.811
> b01 | STAGGER | 400000 | avg | 1453 | 1288.92
> b01 | STAGGER | 1000000 | avg | 542 | 3245.649
> b01 | SHUFFLE | 600 | avg | 325677 | 5.199
> b01 | SHUFFLE | 3000 | avg | 52041 | 29.734
> b01 | SHUFFLE | 90000 | avg | 1217 | 1392.125
> b01 | SHUFFLE | 400000 | avg | 242 | 5772.859
> b01 | SHUFFLE | 1000000 | avg | 90 | 15483.65
> r30 | RANDOM | 600 | avg | 325677 | 4.307
> r30 | RANDOM | 3000 | avg | 52041 | 71.438
> r30 | RANDOM | 90000 | avg | 1217 | 3971.947
> r30 | RANDOM | 400000 | avg | 242 | 19924.32
> r30 | RANDOM | 1000000 | avg | 90 | 53671.9
> r30 | REPEATED | 600 | avg | 651354 | 1.36
> r30 | REPEATED | 3000 | avg | 104083 | 6.415
> r30 | REPEATED | 90000 | avg | 2435 | 578.708
> r30 | REPEATED | 400000 | avg | 484 | 2488.414
> r30 | REPEATED | 1000000 | avg | 180 | 6280.025
> r30 | SAWTOOTH | 600 | avg | 1954062 | 0.488
> r30 | SAWTOOTH | 3000 | avg | 312251 | 2.409
> r30 | SAWTOOTH | 90000 | avg | 7305 | 71.98
> r30 | SAWTOOTH | 400000 | avg | 1453 | 343.433
> r30 | SAWTOOTH | 1000000 | avg | 542 | 954.287
> r30 | STAGGER | 600 | avg | 1954062 | 1.064
> r30 | STAGGER | 3000 | avg | 312251 | 4.559
> r30 | STAGGER | 90000 | avg | 7305 | 135.383
> r30 | STAGGER | 400000 | avg | 1453 | 626.657
> r30 | STAGGER | 1000000 | avg | 542 | 1653.92
> r30 | SHUFFLE | 600 | avg | 325677 | 2.924
> r30 | SHUFFLE | 3000 | avg | 52041 | 18.819
> r30 | SHUFFLE | 90000 | avg | 1217 | 1019.036
> r30 | SHUFFLE | 400000 | avg | 242 | 4661.484
> r30 | SHUFFLE | 1000000 | avg | 90 | 11333.52
> r30_a | RANDOM | 600 | avg | 325677 | 4.024
> r30_a | RANDOM | 3000 | avg | 52041 | 72.86
> r30_a | ...

Hello Vamsi (@vamsi-parasa),

Could you please run the new benchmarking to finalize the best version?
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_r31_11.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_11a.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_12.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_12a.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java

Thank you,
Vladimir

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

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