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

Thu Jan 18 21:38:55 UTC 2024

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

Hello Vamsi (@vamsi-parasa),

Could you please run the benchmarking of new DQPS in your environment with AVX?

Take all classes below and put them in the package org.openjdk.bench.java.util.
ArraysSort class contains all tests for the new versions and ready to use.
(it will run all tests in one execution).

https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSort.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a15.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r20s.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r20p.java

Many thanks,
Vladimir

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

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