RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
Srinivas Vamsi Parasa
duke at openjdk.org
Fri Jan 26 17:22:30 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),
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 REPEATED 90000 avgt 4 57.763 ± 1.955 us/op
ArraysSort.Int.jdk REPEATED 400000 avgt 4 182.238 ± 12.629 us/op
ArraysSort.Int.jdk REPEATED 3000000 avgt 4 1708.082 ± 159.046 us/op
ArraysSort.Int.jdk STAGGER 600 avgt 4 1.038 ± 0.062 us/op
ArraysSort.Int.jdk STAGGER 2000 avgt 4 3.434 ± 0.195 us/op
ArraysSort.Int.jdk STAGGER 90000 avgt 4 148.638 ± 2.531 us/op
ArraysSort.Int.jdk STAGGER 400000 avgt 4 663.076 ± 14.137 us/op
ArraysSort.Int.jdk STAGGER 3000000 avgt 4 5212.821 ± 142.427 us/op
ArraysSort.Int.jdk SHUFFLE 600 avgt 4 1.926 ± 0.116 us/op
ArraysSort.Int.jdk SHUFFLE 2000 avgt 4 6.858 ± 0.135 us/op
ArraysSort.Int.jdk SHUFFLE 90000 avgt 4 473.441 ± 21.678 us/op
ArraysSort.Int.jdk SHUFFLE 400000 avgt 4 2153.779 ± 71.683 us/op
ArraysSort.Int.jdk SHUFFLE 3000000 avgt 4 18180.141 ± 691.292 us/op
ArraysSort.Int.p_a15 RANDOM 600 avgt 4 7.102 ± 0.058 us/op
ArraysSort.Int.p_a15 RANDOM 2000 avgt 4 43.708 ± 1.933 us/op
ArraysSort.Int.p_a15 RANDOM 90000 avgt 4 743.725 ± 144.927 us/op
ArraysSort.Int.p_a15 RANDOM 400000 avgt 4 3099.628 ± 59.222 us/op
ArraysSort.Int.p_a15 RANDOM 3000000 avgt 4 25830.847 ± 1998.651 us/op
ArraysSort.Int.p_a15 REPEATED 600 avgt 4 1.042 ± 0.035 us/op
ArraysSort.Int.p_a15 REPEATED 2000 avgt 4 2.273 ± 0.117 us/op
ArraysSort.Int.p_a15 REPEATED 90000 avgt 4 204.887 ± 12.250 us/op
ArraysSort.Int.p_a15 REPEATED 400000 avgt 4 758.837 ± 37.845 us/op
ArraysSort.Int.p_a15 REPEATED 3000000 avgt 4 7635.330 ± 8220.782 us/op
ArraysSort.Int.p_a15 STAGGER 600 avgt 4 1.045 ± 0.046 us/op
ArraysSort.Int.p_a15 STAGGER 2000 avgt 4 3.410 ± 0.082 us/op
ArraysSort.Int.p_a15 STAGGER 90000 avgt 4 88.093 ± 7.805 us/op
ArraysSort.Int.p_a15 STAGGER 400000 avgt 4 218.848 ± 48.536 us/op
ArraysSort.Int.p_a15 STAGGER 3000000 avgt 4 2245.299 ± 77.811 us/op
ArraysSort.Int.p_a15 SHUFFLE 600 avgt 4 4.594 ± 0.165 us/op
ArraysSort.Int.p_a15 SHUFFLE 2000 avgt 4 17.759 ± 0.608 us/op
ArraysSort.Int.p_a15 SHUFFLE 90000 avgt 4 293.962 ± 49.226 us/op
ArraysSort.Int.p_a15 SHUFFLE 400000 avgt 4 1017.350 ± 181.660 us/op
ArraysSort.Int.p_a15 SHUFFLE 3000000 avgt 4 7419.434 ± 6051.411 us/op
ArraysSort.Int.p_jdk RANDOM 600 avgt 4 1.815 ± 0.628 us/op
ArraysSort.Int.p_jdk RANDOM 2000 avgt 4 6.923 ± 0.644 us/op
ArraysSort.Int.p_jdk RANDOM 90000 avgt 4 266.333 ± 39.212 us/op
ArraysSort.Int.p_jdk RANDOM 400000 avgt 4 835.310 ± 107.797 us/op
ArraysSort.Int.p_jdk RANDOM 3000000 avgt 4 6090.584 ± 3322.954 us/op
ArraysSort.Int.p_jdk REPEATED 600 avgt 4 0.486 ± 0.016 us/op
ArraysSort.Int.p_jdk REPEATED 2000 avgt 4 1.091 ± 0.181 us/op
ArraysSort.Int.p_jdk REPEATED 90000 avgt 4 104.197 ± 18.755 us/op
ArraysSort.Int.p_jdk REPEATED 400000 avgt 4 230.945 ± 45.924 us/op
ArraysSort.Int.p_jdk REPEATED 3000000 avgt 4 3781.371 ± 8241.887 us/op
ArraysSort.Int.p_jdk STAGGER 600 avgt 4 1.046 ± 0.045 us/op
ArraysSort.Int.p_jdk STAGGER 2000 avgt 4 3.405 ± 0.195 us/op
ArraysSort.Int.p_jdk STAGGER 90000 avgt 4 77.708 ± 9.312 us/op
ArraysSort.Int.p_jdk STAGGER 400000 avgt 4 215.360 ± 25.983 us/op
ArraysSort.Int.p_jdk STAGGER 3000000 avgt 4 2256.305 ± 103.960 us/op
ArraysSort.Int.p_jdk SHUFFLE 600 avgt 4 1.952 ± 0.106 us/op
ArraysSort.Int.p_jdk SHUFFLE 2000 avgt 4 6.962 ± 0.970 us/op
ArraysSort.Int.p_jdk SHUFFLE 90000 avgt 4 165.546 ± 31.007 us/op
ArraysSort.Int.p_jdk SHUFFLE 400000 avgt 4 434.846 ± 118.886 us/op
ArraysSort.Int.p_jdk SHUFFLE 3000000 avgt 4 4351.851 ± 2555.203 us/op
ArraysSort.Int.p_r20p RANDOM 600 avgt 4 4.315 ± 0.095 us/op
ArraysSort.Int.p_r20p RANDOM 2000 avgt 4 20.322 ± 1.816 us/op
ArraysSort.Int.p_r20p RANDOM 90000 avgt 4 409.892 ± 54.227 us/op
ArraysSort.Int.p_r20p RANDOM 400000 avgt 4 1322.129 ± 64.913 us/op
ArraysSort.Int.p_r20p RANDOM 3000000 avgt 4 9790.138 ± 1686.701 us/op
ArraysSort.Int.p_r20p REPEATED 600 avgt 4 1.033 ± 0.091 us/op
ArraysSort.Int.p_r20p REPEATED 2000 avgt 4 3.247 ± 0.488 us/op
ArraysSort.Int.p_r20p REPEATED 90000 avgt 4 184.565 ± 13.426 us/op
ArraysSort.Int.p_r20p REPEATED 400000 avgt 4 745.817 ± 75.773 us/op
ArraysSort.Int.p_r20p REPEATED 3000000 avgt 4 5881.615 ± 373.430 us/op
ArraysSort.Int.p_r20p STAGGER 600 avgt 4 0.807 ± 0.008 us/op
ArraysSort.Int.p_r20p STAGGER 2000 avgt 4 2.733 ± 0.085 us/op
ArraysSort.Int.p_r20p STAGGER 90000 avgt 4 73.869 ± 6.061 us/op
ArraysSort.Int.p_r20p STAGGER 400000 avgt 4 208.361 ± 28.714 us/op
ArraysSort.Int.p_r20p STAGGER 3000000 avgt 4 2122.314 ± 174.260 us/op
ArraysSort.Int.p_r20p SHUFFLE 600 avgt 4 3.386 ± 0.017 us/op
ArraysSort.Int.p_r20p SHUFFLE 2000 avgt 4 11.570 ± 0.225 us/op
ArraysSort.Int.p_r20p SHUFFLE 90000 avgt 4 146.273 ± 14.723 us/op
ArraysSort.Int.p_r20p SHUFFLE 400000 avgt 4 766.287 ± 48.840 us/op
ArraysSort.Int.p_r20p SHUFFLE 3000000 avgt 4 5917.997 ± 366.976 us/op
ArraysSort.Int.p_r20s RANDOM 600 avgt 4 4.334 ± 0.220 us/op
ArraysSort.Int.p_r20s RANDOM 2000 avgt 4 23.553 ± 13.608 us/op
ArraysSort.Int.p_r20s RANDOM 90000 avgt 4 818.752 ± 81.659 us/op
ArraysSort.Int.p_r20s RANDOM 400000 avgt 4 2817.805 ± 521.352 us/op
ArraysSort.Int.p_r20s RANDOM 3000000 avgt 4 21512.458 ± 2113.741 us/op
ArraysSort.Int.p_r20s REPEATED 600 avgt 4 1.048 ± 0.134 us/op
ArraysSort.Int.p_r20s REPEATED 2000 avgt 4 3.207 ± 0.324 us/op
ArraysSort.Int.p_r20s REPEATED 90000 avgt 4 183.860 ± 21.690 us/op
ArraysSort.Int.p_r20s REPEATED 400000 avgt 4 769.766 ± 53.749 us/op
ArraysSort.Int.p_r20s REPEATED 3000000 avgt 4 5883.943 ± 331.089 us/op
ArraysSort.Int.p_r20s STAGGER 600 avgt 4 0.796 ± 0.009 us/op
ArraysSort.Int.p_r20s STAGGER 2000 avgt 4 2.709 ± 0.096 us/op
ArraysSort.Int.p_r20s STAGGER 90000 avgt 4 74.508 ± 8.668 us/op
ArraysSort.Int.p_r20s STAGGER 400000 avgt 4 209.745 ± 22.114 us/op
ArraysSort.Int.p_r20s STAGGER 3000000 avgt 4 2129.720 ± 343.004 us/op
ArraysSort.Int.p_r20s SHUFFLE 600 avgt 4 3.394 ± 0.267 us/op
ArraysSort.Int.p_r20s SHUFFLE 2000 avgt 4 11.304 ± 0.890 us/op
ArraysSort.Int.p_r20s SHUFFLE 90000 avgt 4 277.046 ± 37.713 us/op
ArraysSort.Int.p_r20s SHUFFLE 400000 avgt 4 845.203 ± 113.387 us/op
ArraysSort.Int.p_r20s SHUFFLE 3000000 avgt 4 6028.514 ± 859.545 us/op
ArraysSort.Int.r20p RANDOM 600 avgt 4 4.343 ± 0.276 us/op
ArraysSort.Int.r20p RANDOM 2000 avgt 4 20.323 ± 2.063 us/op
ArraysSort.Int.r20p RANDOM 90000 avgt 4 4073.793 ± 69.464 us/op
ArraysSort.Int.r20p RANDOM 400000 avgt 4 19768.316 ± 499.096 us/op
ArraysSort.Int.r20p RANDOM 3000000 avgt 4 165296.770 ± 1527.047 us/op
ArraysSort.Int.r20p REPEATED 600 avgt 4 1.048 ± 0.157 us/op
ArraysSort.Int.r20p REPEATED 2000 avgt 4 3.212 ± 0.314 us/op
ArraysSort.Int.r20p REPEATED 90000 avgt 4 410.775 ± 12.550 us/op
ArraysSort.Int.r20p REPEATED 400000 avgt 4 1869.529 ± 21.372 us/op
ArraysSort.Int.r20p REPEATED 3000000 avgt 4 14302.261 ± 177.065 us/op
ArraysSort.Int.r20p STAGGER 600 avgt 4 0.808 ± 0.106 us/op
ArraysSort.Int.r20p STAGGER 2000 avgt 4 2.683 ± 0.106 us/op
ArraysSort.Int.r20p STAGGER 90000 avgt 4 121.519 ± 1.758 us/op
ArraysSort.Int.r20p STAGGER 400000 avgt 4 548.277 ± 20.543 us/op
ArraysSort.Int.r20p STAGGER 3000000 avgt 4 4496.204 ± 287.544 us/op
ArraysSort.Int.r20p SHUFFLE 600 avgt 4 3.383 ± 0.105 us/op
ArraysSort.Int.r20p SHUFFLE 2000 avgt 4 11.400 ± 1.032 us/op
ArraysSort.Int.r20p SHUFFLE 90000 avgt 4 1001.561 ± 59.738 us/op
ArraysSort.Int.r20p SHUFFLE 400000 avgt 4 4667.466 ± 179.177 us/op
ArraysSort.Int.r20p SHUFFLE 3000000 avgt 4 36284.178 ± 1077.830 us/op
ArraysSort.Int.r20s RANDOM 600 avgt 4 4.490 ± 0.093 us/op
ArraysSort.Int.r20s RANDOM 2000 avgt 4 21.156 ± 2.385 us/op
ArraysSort.Int.r20s RANDOM 90000 avgt 4 4103.675 ± 77.981 us/op
ArraysSort.Int.r20s RANDOM 400000 avgt 4 19946.442 ± 399.865 us/op
ArraysSort.Int.r20s RANDOM 3000000 avgt 4 164962.433 ± 2493.795 us/op
ArraysSort.Int.r20s REPEATED 600 avgt 4 1.056 ± 0.125 us/op
ArraysSort.Int.r20s REPEATED 2000 avgt 4 3.230 ± 0.490 us/op
ArraysSort.Int.r20s REPEATED 90000 avgt 4 412.847 ± 13.513 us/op
ArraysSort.Int.r20s REPEATED 400000 avgt 4 1870.414 ± 24.559 us/op
ArraysSort.Int.r20s REPEATED 3000000 avgt 4 14267.288 ± 136.736 us/op
ArraysSort.Int.r20s STAGGER 600 avgt 4 0.796 ± 0.025 us/op
ArraysSort.Int.r20s STAGGER 2000 avgt 4 2.747 ± 0.080 us/op
ArraysSort.Int.r20s STAGGER 90000 avgt 4 125.870 ± 6.901 us/op
ArraysSort.Int.r20s STAGGER 400000 avgt 4 535.893 ± 24.697 us/op
ArraysSort.Int.r20s STAGGER 3000000 avgt 4 4475.088 ± 105.652 us/op
ArraysSort.Int.r20s SHUFFLE 600 avgt 4 3.353 ± 0.205 us/op
ArraysSort.Int.r20s SHUFFLE 2000 avgt 4 11.682 ± 0.735 us/op
ArraysSort.Int.r20s SHUFFLE 90000 avgt 4 1001.254 ± 56.068 us/op
ArraysSort.Int.r20s SHUFFLE 400000 avgt 4 4702.312 ± 270.761 us/op
ArraysSort.Int.r20s SHUFFLE 3000000 avgt 4 35414.307 ± 169.534 us/op
-------------
PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1912409725
More information about the core-libs-dev
mailing list