RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
Srinivas Vamsi Parasa
duke at openjdk.org
Fri Feb 2 20:13:05 UTC 2024
On Sun, 28 Jan 2024 22:23:38 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:
>> Hi Vladimir (@iaroslavski),
>>
>> Please see the JMH data below.
>>
>> Thanks,
>> Vamsi
>>
>> Benchmark (builder) (size) Mode Cnt Score Error Units
>> ArraysSort.Int.a15 RANDOM 600 avgt 4 7.096 ± 0.081 us/op
>> ArraysSort.Int.a15 RANDOM 2000 avgt 4 44.014 ± 1.717 us/op
>> ArraysSort.Int.a15 RANDOM 90000 avgt 4 4451.444 ± 71.168 us/op
>> ArraysSort.Int.a15 RANDOM 400000 avgt 4 22751.966 ± 683.597 us/op
>> ArraysSort.Int.a15 RANDOM 3000000 avgt 4 190326.306 ± 8008.512 us/op
>> ArraysSort.Int.a15 REPEATED 600 avgt 4 1.044 ± 0.016 us/op
>> ArraysSort.Int.a15 REPEATED 2000 avgt 4 2.272 ± 0.287 us/op
>> ArraysSort.Int.a15 REPEATED 90000 avgt 4 412.331 ± 11.656 us/op
>> ArraysSort.Int.a15 REPEATED 400000 avgt 4 1908.978 ± 30.241 us/op
>> ArraysSort.Int.a15 REPEATED 3000000 avgt 4 15163.443 ± 100.425 us/op
>> ArraysSort.Int.a15 STAGGER 600 avgt 4 1.055 ± 0.057 us/op
>> ArraysSort.Int.a15 STAGGER 2000 avgt 4 3.408 ± 0.096 us/op
>> ArraysSort.Int.a15 STAGGER 90000 avgt 4 149.220 ± 4.022 us/op
>> ArraysSort.Int.a15 STAGGER 400000 avgt 4 663.096 ± 30.252 us/op
>> ArraysSort.Int.a15 STAGGER 3000000 avgt 4 5206.890 ± 234.857 us/op
>> ArraysSort.Int.a15 SHUFFLE 600 avgt 4 4.611 ± 0.118 us/op
>> ArraysSort.Int.a15 SHUFFLE 2000 avgt 4 17.955 ± 0.356 us/op
>> ArraysSort.Int.a15 SHUFFLE 90000 avgt 4 1410.357 ± 41.128 us/op
>> ArraysSort.Int.a15 SHUFFLE 400000 avgt 4 5739.311 ± 128.270 us/op
>> ArraysSort.Int.a15 SHUFFLE 3000000 avgt 4 41501.980 ± 829.443 us/op
>> ArraysSort.Int.jdk RANDOM 600 avgt 4 1.612 ± 0.088 us/op
>> ArraysSort.Int.jdk RANDOM 2000 avgt 4 6.893 ± 0.375 us/op
>> ArraysSort.Int.jdk RANDOM 90000 avgt 4 522.749 ± 19.386 us/op
>> ArraysSort.Int.jdk RANDOM 400000 avgt 4 2424.204 ± 63.844 us/op
>> ArraysSort.Int.jdk RANDOM 3000000 avgt 4 21000.434 ± 801.315 us/op
>> ArraysSort.Int.jdk REPEATED 600 avgt 4 0.496 ± 0.030 us/op
>> ArraysSort.Int.jdk REPEATED 2000 avgt 4 1.037 ± 0.083 us/op
>> ArraysSort.Int.jdk REPE...
>
> Hi Vamsi (@vamsi-parasa), Laurent(@bourgesl),
>
> The latest benchmarking compares compares the following versions:
> jdk - direct call of Arrays.sort();
> a15 - the current source of DualPivotQuicksort from the latest build (except renaming)
> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java
> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a15.java
> r20s - new version without Radix sort
> r20p - new version with Radix sort in parallel case only
>
> It is expected that timing of jdk and a15 should be more or less the same, but please look at the results:
>
> Benchmark | Data Type | Array Size | Arrays.sort() from jdk | Current source (a15)
> -- | -- | -- | -- | --
> ArraysSort.Int.testSort | RANDOM | 600 | 1.612 | 7.096
> ArraysSort.Int.testSort | RANDOM | 2000 | 6.893 | 44.014
> ArraysSort.Int.testSort | RANDOM | 90000 | 522.749 | 4451.444
> ArraysSort.Int.testSort | RANDOM | 400000 | 2424.204 | 22751.966
> ArraysSort.Int.testSort | RANDOM | 3000000 | 21000.434 | 190326.306
> ArraysSort.Int.testSort | REPEATED | 600 | 0.496 | 1.044
> ArraysSort.Int.testSort | REPEATED | 2000 | 1.037 | 2.272
> ArraysSort.Int.testSort | REPEATED | 90000 | 57.763 | 412.331
> ArraysSort.Int.testSort | REPEATED | 400000 | 182.238 | 1908.978
> ArraysSort.Int.testSort | REPEATED | 3000000 | 1708.082 | 15163.443
> ArraysSort.Int.testSort | STAGGER | 600 | 1.038 | 1.055
> ArraysSort.Int.testSort | STAGGER | 2000 | 3.434 | 3.408
> ArraysSort.Int.testSort | STAGGER | 90000 | 148.638 | 149.220
> ArraysSort.Int.testSort | STAGGER | 400000 | 663.076 | 663.096
> ArraysSort.Int.testSort | STAGGER | 3000000 | 5212.821 | 5206.890
> ArraysSort.Int.testSort | SHUFFLE | 600 | 1.926 | 4.611
> ArraysSort.Int.testSort | SHUFFLE | 2000 | 6.858 | 17.955
> ArraysSort.Int.testSort | SHUFFLE | 90000 | 473.441 | 1410.357
> ArraysSort.Int.testSort | SHUFFLE | 400000 | 2153.779 | 5739.311
> ArraysSort.Int.testSort | SHUFFLE | 3000000 | 18180.141 | 41501.980
>
> You can see that a15 (current source) works extremly slower than Arrays.sort(), but the code is the same
> with minor differences: renaming and repackaging (I put the class to the test package org.openjdk.bench.java.util).
> How does other package org.openjdk.bench.java.util effect so much?
>
> I use this pom.xml file https://github.com/iaroslavski/sorting/blob/master/radixsort/pom.xml and run as following script:
>
> `mvn cl...
Hi Vladimir (@iaroslavski),
Please see the data below. All tests were run after putting the DPQS code in java.util package and recompiling the JDK for each case.
<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 | a15 | r20p | r20s
-- | -- | -- | -- | -- | -- | --
ArraysSort.Int.testParallelSort | RANDOM | 600 | 2.24 | 2.201 | 2.423 | 2.389
ArraysSort.Int.testParallelSort | RANDOM | 9000 | 35.318 | 35.961 | 79.028 | 83.774
ArraysSort.Int.testParallelSort | RANDOM | 20000 | 118.729 | 120.872 | 134.829 | 138.349
ArraysSort.Int.testParallelSort | RANDOM | 400000 | 822.676 | 822.44 | 1200.858 | 872.264
ArraysSort.Int.testParallelSort | RANDOM | 3000000 | 5864.514 | 5948.82 | 8800.391 | 6020.616
ArraysSort.Int.testParallelSort | REPEATED | 600 | 0.924 | 0.936 | 0.752 | 0.733
ArraysSort.Int.testParallelSort | REPEATED | 9000 | 9.896 | 9.317 | 31.409 | 24.896
ArraysSort.Int.testParallelSort | REPEATED | 20000 | 58.265 | 42.189 | 40.92 | 40.101
ArraysSort.Int.testParallelSort | REPEATED | 400000 | 256.952 | 253.217 | 236.568 | 239.163
ArraysSort.Int.testParallelSort | REPEATED | 3000000 | 2844.107 | 2851.088 | 2752.939 | 3040.423
ArraysSort.Int.testParallelSort | STAGGER | 600 | 2.245 | 2.296 | 2.15 | 2.219
ArraysSort.Int.testParallelSort | STAGGER | 9000 | 29.278 | 29.119 | 28.288 | 28.141
ArraysSort.Int.testParallelSort | STAGGER | 20000 | 50.129 | 50.442 | 49.746 | 49.686
ArraysSort.Int.testParallelSort | STAGGER | 400000 | 463.309 | 413.619 | 418.077 | 407.519
ArraysSort.Int.testParallelSort | STAGGER | 3000000 | 3687.198 | 4363.242 | 3732.777 | 3769.898
ArraysSort.Int.testParallelSort | SHUFFLE | 600 | 1.715 | 1.698 | 2.799 | 2.733
ArraysSort.Int.testParallelSort | SHUFFLE | 9000 | 27.69 | 27.183 | 32.883 | 32.373
ArraysSort.Int.testParallelSort | SHUFFLE | 20000 | 62.067 | 60.987 | 63.281 | 52.89
ArraysSort.Int.testParallelSort | SHUFFLE | 400000 | 467.213 | 495.14 | 650.173 | 476.403
ArraysSort.Int.testParallelSort | SHUFFLE | 3000000 | 4456.617 | 4318.491 | 7676.837 | 4259.434
ArraysSort.Int.testSort | RANDOM | 600 | 2.282 | 2.356 | 2.479 | 2.56
ArraysSort.Int.testSort | RANDOM | 9000 | 36.457 | 36.25 | 35.399 | 36.066
ArraysSort.Int.testSort | RANDOM | 20000 | 81.019 | 81.012 | 79.987 | 80.566
ArraysSort.Int.testSort | RANDOM | 400000 | 2523.781 | 2492.705 | 2713.143 | 2694.033
ArraysSort.Int.testSort | RANDOM | 3000000 | 21299.95 | 21436.19 | 23279.92 | 23557.36
ArraysSort.Int.testSort | REPEATED | 600 | 0.923 | 0.925 | 0.728 | 0.731
ArraysSort.Int.testSort | REPEATED | 9000 | 5.015 | 5.324 | 4.789 | 4.868
ArraysSort.Int.testSort | REPEATED | 20000 | 10.76 | 11.464 | 13.833 | 11.873
ArraysSort.Int.testSort | REPEATED | 400000 | 236.532 | 213.273 | 247.777 | 231.067
ArraysSort.Int.testSort | REPEATED | 3000000 | 2050.757 | 2059.629 | 2113.255 | 2122.659
ArraysSort.Int.testSort | STAGGER | 600 | 2.236 | 2.192 | 2.116 | 2.21
ArraysSort.Int.testSort | STAGGER | 9000 | 28.12 | 27.949 | 30.822 | 29.807
ArraysSort.Int.testSort | STAGGER | 20000 | 66.48 | 67.361 | 63.297 | 62.592
ArraysSort.Int.testSort | STAGGER | 400000 | 1422.026 | 1410.685 | 1268.24 | 1312.031
ArraysSort.Int.testSort | STAGGER | 3000000 | 10938.67 | 10913.78 | 34406.74 | 10467.03
ArraysSort.Int.testSort | SHUFFLE | 600 | 1.712 | 1.67 | 2.803 | 2.809
ArraysSort.Int.testSort | SHUFFLE | 9000 | 32.927 | 32.824 | 34.267 | 35.117
ArraysSort.Int.testSort | SHUFFLE | 20000 | 85.591 | 85.656 | 77.072 | 77.365
ArraysSort.Int.testSort | SHUFFLE | 400000 | 2273.753 | 2274.048 | 2343.126 | 2307.69
ArraysSort.Int.testSort | SHUFFLE | 3000000 | 18675.12 | 18575.08 | 19684.59 | 19613.74
</body>
</html>
-------------
PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1924613668
More information about the core-libs-dev
mailing list