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

Fri Jan 26 09:33:45 UTC 2024

On Thu, 18 Jan 2024 21:36:22 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:

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

Hi Vladimir (@iaroslavski),

I was able to figure out the issue and started the benchmarking JMH run. It's night time here, will provide the data Friday morning (US PST)

Thanks,
Vamsi

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

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