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

Srinivas Vamsi Parasa duke at openjdk.org
Sun Apr 21 04:40:49 UTC 2024 

On Tue, 9 Apr 2024 21:36:46 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:

>>> Hi Vamsi (@vamsi-parasa), few questions on your test environment:
>>> 
>>> * what are the hardware specs of your server ?
>>> * bare-metal or virtual ?
>>> * are other services or big processes running ?
>>> * os tuning ? CPU HT: off? Fixed CPU governor or frequency ?
>>> * isolation using taskset ?
>>> 
>>> Maybe C2 JIT (+ CDS archive) are given more performance on stock jdk sort than same code running outside jdk...
>>> 
>>> Thanks, Laurent
>> 
>> Hi Laurent,
>> 
>> The benchmarks are run on Intel TigerLake Core i7 machine. It's bare-metal without any virtualization. HT is ON and there is no other specific OS tuning or isolation using taskset.
>> 
>> Thanks,
>> Vamsi
>
> 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 | 180 | 8366.866
b01_mrg | STAGGER | 600 | avg | 1954062 | 0.73
b01_mrg | STAGGER | 3000 | avg | 312251 | 3.733
b01_mrg | STAGGER | 90000 | avg | 7305 | 114.35
b01_mrg | STAGGER | 400000 | avg | 1453 | 524.821
b01_mrg | STAGGER | 1000000 | avg | 542 | 1351.504
b01_mrg | SHUFFLE | 600 | avg | 325677 | 4.986
b01_mrg | SHUFFLE | 3000 | avg | 52041 | 28.456
b01_mrg | SHUFFLE | 90000 | avg | 1217 | 1291.609
b01_mrg | SHUFFLE | 400000 | avg | 242 | 5743.312
b01_mrg | SHUFFLE | 1000000 | avg | 90 | 15173.89
b01_piv | RANDOM | 600 | avg | 325677 | 6.108
b01_piv | RANDOM | 3000 | avg | 52041 | 77.286
b01_piv | RANDOM | 90000 | avg | 1217 | 4275.036
b01_piv | RANDOM | 400000 | avg | 242 | 21485.54
b01_piv | RANDOM | 1000000 | avg | 90 | 57532.96
b01_piv | REPEATED | 600 | avg | 651354 | 1.035
b01_piv | REPEATED | 3000 | avg | 104083 | 5.13
b01_piv | REPEATED | 90000 | avg | 2435 | 545.294
b01_piv | REPEATED | 400000 | avg | 484 | 2357.776
b01_piv | REPEATED | 1000000 | avg | 180 | 5897.241
b01_piv | STAGGER | 600 | avg | 1954062 | 0.98
b01_piv | STAGGER | 3000 | avg | 312251 | 4.924
b01_piv | STAGGER | 90000 | avg | 7305 | 132.861
b01_piv | STAGGER | 400000 | avg | 1453 | 590.477
b01_piv | STAGGER | 1000000 | avg | 542 | 1490.788
b01_piv | SHUFFLE | 600 | avg | 325677 | 4.647
b01_piv | SHUFFLE | 3000 | avg | 52041 | 28.797
b01_piv | SHUFFLE | 90000 | avg | 1217 | 1199.174
b01_piv | SHUFFLE | 400000 | avg | 242 | 5333.113
b01_piv | SHUFFLE | 1000000 | avg | 90 | 13569.69
b01_prt | RANDOM | 600 | avg | 325677 | 6.198
b01_prt | RANDOM | 3000 | avg | 52041 | 76.981
b01_prt | RANDOM | 90000 | avg | 1217 | 4084.038
b01_prt | RANDOM | 400000 | avg | 242 | 20829.11
b01_prt | RANDOM | 1000000 | avg | 90 | 54992.42
b01_prt | REPEATED | 600 | avg | 651354 | 1.695
b01_prt | REPEATED | 3000 | avg | 104083 | 10.026
b01_prt | REPEATED | 90000 | avg | 2435 | 713.94
b01_prt | REPEATED | 400000 | avg | 484 | 3046.4
b01_prt | REPEATED | 1000000 | avg | 180 | 8107.396
b01_prt | STAGGER | 600 | avg | 1954062 | 0.996
b01_prt | STAGGER | 3000 | avg | 312251 | 4.945
b01_prt | STAGGER | 90000 | avg | 7305 | 133.185
b01_prt | STAGGER | 400000 | avg | 1453 | 592.432
b01_prt | STAGGER | 1000000 | avg | 542 | 1491.101
b01_prt | SHUFFLE | 600 | avg | 325677 | 4.438
b01_prt | SHUFFLE | 3000 | avg | 52041 | 23.821
b01_prt | SHUFFLE | 90000 | avg | 1217 | 1172.62
b01_prt | SHUFFLE | 400000 | avg | 242 | 4874.561
b01_prt | SHUFFLE | 1000000 | avg | 90 | 12895.43
r29p | RANDOM | 600 | avg | 325677 | 4.352
r29p | RANDOM | 3000 | avg | 52041 | 65.579
r29p | RANDOM | 90000 | avg | 1217 | 3829.863
r29p | RANDOM | 400000 | avg | 242 | 19222.97
r29p | RANDOM | 1000000 | avg | 90 | 51848.6
r29p | REPEATED | 600 | avg | 651354 | 1.1
r29p | REPEATED | 3000 | avg | 104083 | 5.357
r29p | REPEATED | 90000 | avg | 2435 | 581.597
r29p | REPEATED | 400000 | avg | 484 | 2538.564
r29p | REPEATED | 1000000 | avg | 180 | 6406.969
r29p | STAGGER | 600 | avg | 1954062 | 0.486
r29p | STAGGER | 3000 | avg | 312251 | 2.396
r29p | STAGGER | 90000 | avg | 7305 | 71.766
r29p | STAGGER | 400000 | avg | 1453 | 341.391
r29p | STAGGER | 1000000 | avg | 542 | 948.696
r29p | SHUFFLE | 600 | avg | 325677 | 2.733
r29p | SHUFFLE | 3000 | avg | 52041 | 16.883
r29p | SHUFFLE | 90000 | avg | 1217 | 987.346
r29p | SHUFFLE | 400000 | avg | 242 | 4541.698
r29p | SHUFFLE | 1000000 | avg | 90 | 11179.08
r29p5 | RANDOM | 600 | avg | 325677 | 4.153
r29p5 | RANDOM | 3000 | avg | 52041 | 62.496
r29p5 | RANDOM | 90000 | avg | 1217 | 3833.639
r29p5 | RANDOM | 400000 | avg | 242 | 19222.55
r29p5 | RANDOM | 1000000 | avg | 90 | 51200.3
r29p5 | REPEATED | 600 | avg | 651354 | 1.044
r29p5 | REPEATED | 3000 | avg | 104083 | 4.994
r29p5 | REPEATED | 90000 | avg | 2435 | 583.856
r29p5 | REPEATED | 400000 | avg | 484 | 2482.716
r29p5 | REPEATED | 1000000 | avg | 180 | 6270.456
r29p5 | STAGGER | 600 | avg | 1954062 | 0.501
r29p5 | STAGGER | 3000 | avg | 312251 | 2.488
r29p5 | STAGGER | 90000 | avg | 7305 | 74.435
r29p5 | STAGGER | 400000 | avg | 1453 | 353.166
r29p5 | STAGGER | 1000000 | avg | 542 | 978.56
r29p5 | SHUFFLE | 600 | avg | 325677 | 3.006
r29p5 | SHUFFLE | 3000 | avg | 52041 | 18.062
r29p5 | SHUFFLE | 90000 | avg | 1217 | 1009.819
r29p5 | SHUFFLE | 400000 | avg | 242 | 4638.24
r29p5 | SHUFFLE | 1000000 | avg | 90 | 11350.48
p_b01 | RANDOM | 600 | avg | 325677 | 7.273
p_b01 | RANDOM | 3000 | avg | 52041 | 82.233
p_b01 | RANDOM | 90000 | avg | 1217 | 650.813
p_b01 | RANDOM | 400000 | avg | 242 | 2676.309
p_b01 | RANDOM | 1000000 | avg | 90 | 6862.199
p_b01 | REPEATED | 600 | avg | 651354 | 1.3
p_b01 | REPEATED | 3000 | avg | 104083 | 9.647
p_b01 | REPEATED | 90000 | avg | 2435 | 245.071
p_b01 | REPEATED | 400000 | avg | 484 | 972.151
p_b01 | REPEATED | 1000000 | avg | 180 | 2481.689
p_b01 | STAGGER | 600 | avg | 1954062 | 0.977
p_b01 | STAGGER | 3000 | avg | 312251 | 4.771
p_b01 | STAGGER | 90000 | avg | 7305 | 64.934
p_b01 | STAGGER | 400000 | avg | 1453 | 185.96
p_b01 | STAGGER | 1000000 | avg | 542 | 498.298
p_b01 | SHUFFLE | 600 | avg | 325677 | 5.131
p_b01 | SHUFFLE | 3000 | avg | 52041 | 29.535
p_b01 | SHUFFLE | 90000 | avg | 1217 | 271.691
p_b01 | SHUFFLE | 400000 | avg | 242 | 893.958
p_b01 | SHUFFLE | 1000000 | avg | 90 | 2016.456
p_b01_ins | RANDOM | 600 | avg | 325677 | 7.697
p_b01_ins | RANDOM | 3000 | avg | 52041 | 73.044
p_b01_ins | RANDOM | 90000 | avg | 1217 | 639.5
p_b01_ins | RANDOM | 400000 | avg | 242 | 2627.147
p_b01_ins | RANDOM | 1000000 | avg | 90 | 6965.733
p_b01_ins | REPEATED | 600 | avg | 651354 | 1.085
p_b01_ins | REPEATED | 3000 | avg | 104083 | 8.177
p_b01_ins | REPEATED | 90000 | avg | 2435 | 252.955
p_b01_ins | REPEATED | 400000 | avg | 484 | 1012.75
p_b01_ins | REPEATED | 1000000 | avg | 180 | 2448.868
p_b01_ins | STAGGER | 600 | avg | 1954062 | 1.132
p_b01_ins | STAGGER | 3000 | avg | 312251 | 5.343
p_b01_ins | STAGGER | 90000 | avg | 7305 | 65.105
p_b01_ins | STAGGER | 400000 | avg | 1453 | 192.285
p_b01_ins | STAGGER | 1000000 | avg | 542 | 506.095
p_b01_ins | SHUFFLE | 600 | avg | 325677 | 4.151
p_b01_ins | SHUFFLE | 3000 | avg | 52041 | 27.158
p_b01_ins | SHUFFLE | 90000 | avg | 1217 | 270.81
p_b01_ins | SHUFFLE | 400000 | avg | 242 | 867.613
p_b01_ins | SHUFFLE | 1000000 | avg | 90 | 1963.741
p_b01_mrg | RANDOM | 600 | avg | 325677 | 7.139
p_b01_mrg | RANDOM | 3000 | avg | 52041 | 73.579
p_b01_mrg | RANDOM | 90000 | avg | 1217 | 619.217
p_b01_mrg | RANDOM | 400000 | avg | 242 | 2542.126
p_b01_mrg | RANDOM | 1000000 | avg | 90 | 6573.197
p_b01_mrg | REPEATED | 600 | avg | 651354 | 1.18
p_b01_mrg | REPEATED | 3000 | avg | 104083 | 8.585
p_b01_mrg | REPEATED | 90000 | avg | 2435 | 304.565
p_b01_mrg | REPEATED | 400000 | avg | 484 | 993.142
p_b01_mrg | REPEATED | 1000000 | avg | 180 | 2440.591
p_b01_mrg | STAGGER | 600 | avg | 1954062 | 0.765
p_b01_mrg | STAGGER | 3000 | avg | 312251 | 3.779
p_b01_mrg | STAGGER | 90000 | avg | 7305 | 66.429
p_b01_mrg | STAGGER | 400000 | avg | 1453 | 207.316
p_b01_mrg | STAGGER | 1000000 | avg | 542 | 535.042
p_b01_mrg | SHUFFLE | 600 | avg | 325677 | 4.996
p_b01_mrg | SHUFFLE | 3000 | avg | 52041 | 28.052
p_b01_mrg | SHUFFLE | 90000 | avg | 1217 | 270.357
p_b01_mrg | SHUFFLE | 400000 | avg | 242 | 899.677
p_b01_mrg | SHUFFLE | 1000000 | avg | 90 | 2000.463
p_b01_piv | RANDOM | 600 | avg | 325677 | 6.991
p_b01_piv | RANDOM | 3000 | avg | 52041 | 76.157
p_b01_piv | RANDOM | 90000 | avg | 1217 | 56.604
p_b01_piv | RANDOM | 400000 | avg | 242 | 134.653
p_b01_piv | RANDOM | 1000000 | avg | 90 | 374.473
p_b01_piv | REPEATED | 600 | avg | 651354 | 1.009
p_b01_piv | REPEATED | 3000 | avg | 104083 | 4.718
p_b01_piv | REPEATED | 90000 | avg | 2435 | 56.453
p_b01_piv | REPEATED | 400000 | avg | 484 | 852.866
p_b01_piv | REPEATED | 1000000 | avg | 180 | 2183.644
p_b01_piv | STAGGER | 600 | avg | 1954062 | 0.97
p_b01_piv | STAGGER | 3000 | avg | 312251 | 4.791
p_b01_piv | STAGGER | 90000 | avg | 7305 | 66.761
p_b01_piv | STAGGER | 400000 | avg | 1453 | 191.334
p_b01_piv | STAGGER | 1000000 | avg | 542 | 516.535
p_b01_piv | SHUFFLE | 600 | avg | 325677 | 4.681
p_b01_piv | SHUFFLE | 3000 | avg | 52041 | 28.77
p_b01_piv | SHUFFLE | 90000 | avg | 1217 | 126.367
p_b01_piv | SHUFFLE | 400000 | avg | 242 | 288.9
p_b01_piv | SHUFFLE | 1000000 | avg | 90 | 972.511
p_b01_prt | RANDOM | 600 | avg | 325677 | 6.339
p_b01_prt | RANDOM | 3000 | avg | 52041 | 73.78
p_b01_prt | RANDOM | 90000 | avg | 1217 | 577.255
p_b01_prt | RANDOM | 400000 | avg | 242 | 2342.825
p_b01_prt | RANDOM | 1000000 | avg | 90 | 6087.572
p_b01_prt | REPEATED | 600 | avg | 651354 | 1.137
p_b01_prt | REPEATED | 3000 | avg | 104083 | 6.946
p_b01_prt | REPEATED | 90000 | avg | 2435 | 204.205
p_b01_prt | REPEATED | 400000 | avg | 484 | 995.421
p_b01_prt | REPEATED | 1000000 | avg | 180 | 2411.23
p_b01_prt | STAGGER | 600 | avg | 1954062 | 1.128
p_b01_prt | STAGGER | 3000 | avg | 312251 | 5.341
p_b01_prt | STAGGER | 90000 | avg | 7305 | 64.844
p_b01_prt | STAGGER | 400000 | avg | 1453 | 189.274
p_b01_prt | STAGGER | 1000000 | avg | 542 | 506.245
p_b01_prt | SHUFFLE | 600 | avg | 325677 | 4.393
p_b01_prt | SHUFFLE | 3000 | avg | 52041 | 25.166
p_b01_prt | SHUFFLE | 90000 | avg | 1217 | 235.482
p_b01_prt | SHUFFLE | 400000 | avg | 242 | 758.64
p_b01_prt | SHUFFLE | 1000000 | avg | 90 | 1710.273
p_r29p | RANDOM | 600 | avg | 325677 | 4.005
p_r29p | RANDOM | 3000 | avg | 52041 | 67.873
p_r29p | RANDOM | 90000 | avg | 1217 | 325.19
p_r29p | RANDOM | 400000 | avg | 242 | 1221.24
p_r29p | RANDOM | 1000000 | avg | 90 | 3047.764
p_r29p | REPEATED | 600 | avg | 651354 | 1.054
p_r29p | REPEATED | 3000 | avg | 104083 | 4.982
p_r29p | REPEATED | 90000 | avg | 2435 | 250.923
p_r29p | REPEATED | 400000 | avg | 484 | 1031.028
p_r29p | REPEATED | 1000000 | avg | 180 | 2516.481
p_r29p | STAGGER | 600 | avg | 1954062 | 0.496
p_r29p | STAGGER | 3000 | avg | 312251 | 2.476
p_r29p | STAGGER | 90000 | avg | 7305 | 54.193
p_r29p | STAGGER | 400000 | avg | 1453 | 207.309
p_r29p | STAGGER | 1000000 | avg | 542 | 486.682
p_r29p | SHUFFLE | 600 | avg | 325677 | 2.801
p_r29p | SHUFFLE | 3000 | avg | 52041 | 17.811
p_r29p | SHUFFLE | 90000 | avg | 1217 | 142.732
p_r29p | SHUFFLE | 400000 | avg | 242 | 750.188
p_r29p | SHUFFLE | 1000000 | avg | 90 | 1625.551
p_r29p5 | RANDOM | 600 | avg | 325677 | 4.447
p_r29p5 | RANDOM | 3000 | avg | 52041 | 62.797
p_r29p5 | RANDOM | 90000 | avg | 1217 | 326.74
p_r29p5 | RANDOM | 400000 | avg | 242 | 1212.317
p_r29p5 | RANDOM | 1000000 | avg | 90 | 2994.011
p_r29p5 | REPEATED | 600 | avg | 651354 | 1.132
p_r29p5 | REPEATED | 3000 | avg | 104083 | 5.474
p_r29p5 | REPEATED | 90000 | avg | 2435 | 244.921
p_r29p5 | REPEATED | 400000 | avg | 484 | 1056.798
p_r29p5 | REPEATED | 1000000 | avg | 180 | 2558.885
p_r29p5 | STAGGER | 600 | avg | 1954062 | 0.553
p_r29p5 | STAGGER | 3000 | avg | 312251 | 2.687
p_r29p5 | STAGGER | 90000 | avg | 7305 | 57.763
p_r29p5 | STAGGER | 400000 | avg | 1453 | 207.106
p_r29p5 | STAGGER | 1000000 | avg | 542 | 480.437
p_r29p5 | SHUFFLE | 600 | avg | 325677 | 3.018
p_r29p5 | SHUFFLE | 3000 | avg | 52041 | 18.435
p_r29p5 | SHUFFLE | 90000 | avg | 1217 | 144.3
p_r29p5 | SHUFFLE | 400000 | avg | 242 | 750.63
p_r29p5 | SHUFFLE | 1000000 | avg | 90 | 1638.547

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

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

More information about the core-libs-dev mailing list