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

Fri Dec 8 23:11:20 UTC 2023

On Fri, 8 Dec 2023 20:08:22 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:

>> 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.te...
>
> 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

Sure Vladimir (@iaroslavski),

Will run the tests. 

Also, the baseline stock JDK has changed as a new PR which improves AVX512 sort by up to 35% has been integrated. The PR implements AVX2 sort (https://github.com/openjdk/jdk/pull/16534) but it also improves the performance of AVX512 sort.

Will use the new stock JDK for these measurements and provide the results by EOD Sunday (US pacific time).

Thanks,
Vamsi

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

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