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

Mon Dec 11 21:19:41 UTC 2023

On Mon, 11 Dec 2023 03:42:51 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> 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
>
> Hi Vladimir (@iaroslavski)
> 
> Please see the data below using the latest version of AVX512 sort that got integrated into OpenJDK.
> 
> <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) | Stock JDK | a10 | r14 | r17 | r18
> -- | -- | -- | -- | -- | -- | --
> ArraysSort.Int.testSort | RANDOM | 2.202 | 2.226 | 1.535 | 1.556 | 1.546
> ArraysSort.Int.testSort | RANDOM | 35.128 | 34.804 | 30.808 | 30.914 | 31.284
> ArraysSort.Int.testSort | RANDOM | 78.571 | 77.224 | 72.567 | 73.098 | 73.337
> ArraysSort.Int.testSort | RANDOM | 2466.487 | 2470.66 | 2504.654 | 2494.051 | 2499.746
> ArraysSort.Int.testSort | RANDOM | 20704.14 | 20668.19 | 21377.73 | 21362.63 | 21278.94
> ArraysSort.Int.testSort | REPEATED | 0.877 | 0.892 | 0.74 | 0.724 | 0.718
> ArraysSort.Int.testSort | REPEATED | 4.789 | 4.788 | 4.92 | 4.721 | 4.891
> ArraysSort.Int.testSort | REPEATED | 11.172 | 11.778 | 11.53 | 11.467 | 11.406
> ArraysSort.Int.testSort | REPEATED | 207.212 | 207.292 | 255.46 | 258.832 | 254.44
> ArraysSort.Int.testSort | REPEATED | 1862.544 | 1876.759 | 1952.646 | 1957.978 | 1981.906
> ArraysSort.Int.testSort | STAGGER | 2.092 | 2.137 | 1.999 | 2.031 | 2.015
> ArraysSort.Int.testSort | STAGGER | 29.891 | 30.321 | 25.626 | 26.318 | 26.396
> ArraysSort.Int.testSort | STAGGER | 60.979 | 83.439 | 57.864 | 57.213 | 79.762
> ArraysSort.Int.testSort | STAGGER | 1227.933 | 1224.495 | 1236.133 | 1229.773 | 1228.877
> ArraysSort.Int.testSort | STAGGER | 9514.873 | 9565.599 | 9491.509 | 9481.147 | 9481.905
> ArraysSort.Int.testSort | SHUFFLE | 1.608 | 1.595 | 1.419 | 1.442 | 1.491
> ArraysSort.Int.testSort | SHUFFLE | 31.566 | 32.789 | 28.718 | 28.768 | 28.671
> ArraysSort.Int.testSort | SHUFFLE | 82.157 | 83.741 | 70.889 | 69.951 | 71.196
> ArraysSort.Int.testSort | SHUFFLE | 2251.219 | 2248.496 | 2184.459 | 2163.969 | 2156.239
> ArraysSort.Int.testSort | SHUFFLE | 18211.05 | 18223.24 | 17987.4 | 18114.26 | 17994.98
> 
> 
> 
> </body>
> 
> </html>
> 
> Thanks,
> Vamsi

Many thanks, Vamsi (@vamsi-parasa)
I will analyze this result.

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

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