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

[Vladimir Yaroslavskiy]

On Fri, 10 May 2024 22:08:47 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> 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
>
> Hi Vladimir (@iaroslavski),
> 
> Please see the data below.
> 
> Thanks,
> Vamsi
> 
> 
> name | builder | size | mode | count | score
> -- | -- | -- | -- | -- | --
> b01 | RANDOM | 600 | avg | 325677 | 6.861
> b01 | RANDOM | 3000 | avg | 52041 | 77.313
> b01 | RANDOM | 90000 | avg | 1217 | 4315.41
> b01 | RANDOM | 400000 | avg | 242 | 22110.95
> b01 | RANDOM | 1000000 | avg | 90 | 58613.45
> b01 | REPEATED | 600 | avg | 651354 | 1.993
> b01 | REPEATED | 3000 | avg | 104083 | 13.026
> b01 | REPEATED | 90000 | avg | 2435 | 741.97
> b01 | REPEATED | 400000 | avg | 484 | 3161.073
> b01 | REPEATED | 1000000 | avg | 180 | 8363.671
> b01 | STAGGER | 600 | avg | 1954062 | 9.124
> b01 | STAGGER | 3000 | avg | 312251 | 10.026
> b01 | STAGGER | 90000 | avg | 7305 | 286.313
> b01 | STAGGER | 400000 | avg | 1453 | 1278.758
> b01 | STAGGER | 1000000 | avg | 542 | 3242.849
> b01 | SHUFFLE | 600 | avg | 325677 | 5.113
> b01 | SHUFFLE | 3000 | avg | 52041 | 28.85
> b01 | SHUFFLE | 90000 | avg | 1217 | 1368.91
> b01 | SHUFFLE | 400000 | avg | 242 | 5718.052
> b01 | SHUFFLE | 1000000 | avg | 90 | 15376.1
> r31_11 | RANDOM | 600 | avg | 325677 | 4.305
> r31_11 | RANDOM | 3000 | avg | 52041 | 73.399
> r31_11 | RANDOM | 90000 | avg | 1217 | 3963.515
> r31_11 | RANDOM | 400000 | avg | 242 | 19841.07
> r31_11 | RANDOM | 1000000 | avg | 90 | 53372.63
> r31_11 | REPEATED | 600 | avg | 651354 | 1.208
> r31_11 | REPEATED | 3000 | avg | 104083 | 6.206
> r31_11 | REPEATED | 90000 | avg | 2435 | 614.159
> r31_11 | REPEATED | 400000 | avg | 484 | 2615.923
> r31_11 | REPEATED | 1000000 | avg | 180 | 6553.801
> r31_11 | STAGGER | 600 | avg | 1954062 | 1.023
> r31_11 | STAGGER | 3000 | avg | 312251 | 4.406
> r31_11 | STAGGER | 90000 | avg | 7305 | 129.76
> r31_11 | STAGGER | 400000 | avg | 1453 | 600.581
> r31_11 | STAGGER | 1000000 | avg | 542 | 1588.827
> r31_11 | SHUFFLE | 600 | avg | 325677 | 2.887
> r31_11 | SHUFFLE | 3000 | avg | 52041 | 17.901
> r31_11 | SHUFFLE | 90000 | avg | 1217 | 1033.808
> r31_11 | SHUFFLE | 400000 | avg | 242 | 4686.188
> r31_11 | SHUFFLE | 1000000 | avg | 90 | 11589.67
> r31_11a | RANDOM | 600 | avg | 325677 | 4.277
> r31_11a | RANDOM | 3000 | avg | 52041 | 70.578
> r31_11a | RANDOM | 90000 | avg | 1217 | 3963.836
> r31_11a | RANDOM | 400000 | avg | 242 | 19771.67
> r31_11a | RANDOM | 1000000 | avg | 90 | 53417.95
> r31_11a | REPEATED | 600 | avg | 651354 | 1.112
> r31_11a | REPEATED | 3000 | avg | 104083 | 5.662
> r31_11a | REPEATED | 90000 | avg | 2435 | 596.963
> r31_11a | REPEATED | 400000 | avg | 484 | 2618.076
> r31_11a | REPEATED | 1000000 | avg | 180 | 6597.833
> r31_1...

Hello Vamsi (@vamsi-parasa),

Could you please run the new benchmarking to check sorting of all data types?
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_r32.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java

Thank you,
Vladimir

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

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