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

Fri Dec 8 20:11:21 UTC 2023

On Fri, 8 Dec 2023 01:27:35 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> Hello Vamsi (@vamsi-parasa),
>> 
>> Did you have a chance to run benchmarking?
>
> Hi Vladimir (@iaroslavski),
> 
> Please see the data below.
> 
> Thanks,
> Vamsi
> 
> <html xmlns:v="urn:schemas-microsoft-com:vml"
> xmlns:o="urn:schemas-microsoft-com:office:office"
> xmlns:x="urn:schemas-microsoft-com:office:excel"
> xmlns="http://www.w3.org/TR/REC-html40">
> 
> <head>
> 
> <meta name=ProgId content=Excel.Sheet>
> <meta name=Generator content="Microsoft Excel 15">
> <link id=Main-File rel=Main-File
> href="file:///C:/Users/sparasa/AppData/Local/Temp/msohtmlclip1/01/clip.htm">
> <link rel=File-List
> href="file:///C:/Users/sparasa/AppData/Local/Temp/msohtmlclip1/01/clip_filelist.xml">
> 
> 
> 
> </head>
> 
> <body link="#0563C1" vlink="#954F72">
> 
> 
> Benchmark (us/op) | (builder) | (size) | Stock JDK | r_02 | r_03 | r_04 | r_05 | r_06 | r_07 | r_08 | r_98 | r_99
> -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | --
> ArraysSort.Int.testSort | RANDOM | 600 | 2.256 | 1.634 | 1.651 | 1.659 | 1.671 | 1.646 | 1.611 | 1.661 | 1.642 | 1.671
> ArraysSort.Int.testSort | RANDOM | 9000 | 41.457 | 37.697 | 38.075 | 37.927 | 39.693 | 38.989 | 37.86 | 38.163 | 39.222 | 38.835
> ArraysSort.Int.testSort | RANDOM | 20000 | 98.448 | 91.494 | 89.683 | 87.971 | 90.231 | 90.141 | 90.515 | 90.415 | 89.571 | 90.308
> ArraysSort.Int.testSort | RANDOM | 400000 | 2820.939 | 2816.5 | 2811.334 | 2833.15 | 2802.958 | 2813.012 | 2815.24 | 2825.526 | 2801.497 | 2816.25
> ArraysSort.Int.testSort | RANDOM | 3000000 | 23426.411 | 23661.09 | 23778.15 | 23748.91 | 23802.62 | 23746.3 | 23778.16 | 23631.1 | 23651.78 | 23859.91
> ArraysSort.Int.testSort | REPEATED | 600 | 1.032 | 0.929 | 0.955 | 0.944 | 0.927 | 0.928 | 0.953 | 0.918 | 0.934 | 0.93
> ArraysSort.Int.testSort | REPEATED | 9000 | 5.114 | 5.059 | 4.832 | 5.162 | 4.965 | 4.973 | 5.518 | 5.003 | 5.435 | 4.971
> ArraysSort.Int.testSort | REPEATED | 20000 | 10.3 | 12.238 | 12.474 | 12.482 | 12.351 | 12.338 | 12.372 | 12.394 | 12.688 | 13.477
> ArraysSort.Int.testSort | REPEATED | 400000 | 210.742 | 261.709 | 264.572 | 263.203 | 260.822 | 260.475 | 262.03 | 260.356 | 265.976 | 264.273
> ArraysSort.Int.testSort | REPEATED | 3000000 | 1948.589 | 2062.235 | 2079.128 | 2065.445 | 2053.24 | 2076.278 | 2049.799 | 2059.1 | 2073.191 | 2075.65
> ArraysSort.Int.testSort | STAGGER | 600 | 2.125 | 2.001 | 2.023 | 2.021 | 2.001 | 2.018 | 2.011 | 2.017 | 2.005 | 2.011
> ArraysSort.Int.testSort | STAGGER | 9000 | 29.86 | 26.169 | 26.093 | 25.562 | 26.385 | 26.109 | 26.485 | 26.375 | 26.412 | 25.712
> ArraysSort.Int.testSort | STAGGER | 20000 | 67.096 | 77.157 | 63.636 | 64.479 | 58.697 | 59.728 | 58.91...

Hello Vamsi (@vamsi-parasa),

I made the process simpler: added all variants to be compared into ArraysSort class
(set the same package org.openjdk.bench.java.util). It will run all sorts incl. sort from jdk
in the same environment. It should provide more accurate results, otherwise we see some anomalies.

Could you please find time to run the benchmarking?
Take all classes below and put them in the package org.openjdk.bench.java.util.
https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSort.java

https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a10.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r14.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r17.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r18.java

Many thanks,
Vladimir

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

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