RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
Srinivas Vamsi Parasa
duke at openjdk.org
Mon Mar 11 19:34:22 UTC 2024
On Tue, 27 Feb 2024 20:54:03 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:
>> Hello Vladimir (@iaroslavski),
>>
>> Please see the data below. Each DPQS class was copied to java.util and the JDK was recompiled.
>>
>> Thanks,
>> Vamsi
>>
>> <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 | (builder) | (size) | Stock JDK | r20p | r20s | r25p | r25s
>> -- | -- | -- | -- | -- | -- | -- | --
>> ArraysSort.Int.p_sort | RANDOM | 600 | 1.618 | 2.601 | 2.966 | 2.898 | 3.269
>> ArraysSort.Int.p_sort | RANDOM | 2000 | 7.433 | 8.438 | 8.463 | 8.414 | 8.65
>> ArraysSort.Int.p_sort | RANDOM | 90000 | 258.853 | 355.261 | 326.378 | 347.65 | 321.894
>> ArraysSort.Int.p_sort | RANDOM | 400000 | 842.085 | 1225.929 | 899.852 | 1278.681 | 932.627
>> ArraysSort.Int.p_sort | RANDOM | 3000000 | 5723.659 | 8711.108 | 6086.974 | 8948.101 | 6122.612
>> ArraysSort.Int.p_sort | REPEATED | 600 | 0.52 | 0.585 | 0.629 | 0.586 | 0.579
>> ArraysSort.Int.p_sort | REPEATED | 2000 | 1.18 | 1.225 | 1.21 | 1.225 | 1.238
>> ArraysSort.Int.p_sort | REPEATED | 90000 | 102.142 | 85.79 | 86.131 | 87.954 | 86.036
>> ArraysSort.Int.p_sort | REPEATED | 400000 | 244.508 | 229.142 | 227.613 | 228.608 | 228.367
>> ArraysSort.Int.p_sort | REPEATED | 3000000 | 2752.745 | 2584.103 | 2544.192 | 2576.803 | 2609.833
>> ArraysSort.Int.p_sort | STAGGER | 600 | 1.146 | 0.894 | 0.898 | 0.904 | 0.912
>> ArraysSort.Int.p_sort | STAGGER | 2000 | 3.712 | 3.096 | 3.121 | 3.03 | 3.049
>> ArraysSort.Int.p_sort | STAGGER | 90000 | 72.763 | 77.575 | 78.366 | 79.158 | 77.199
>> ArraysSort.Int.p_sort | STAGGER | 400000 | 212.455 | 228.331 | 225.888 | 224.686 | 225.728
>> ArraysSort.Int.p_sort | STAGGER | 3000000 | 2290.327 | 2216.741 | 2196.138 | 2236.658 | 2262.472
>> ArraysSort.Int.p_sort | SHUFFLE | 600 | 2.01 | 2.92 | 2.907 | 2.91 | 2.926
>> ArraysSort.Int.p_sort | SHUFFLE | 2000 | 7.06 | 7.759 | 7.776 | 7.688 | 8.062
>> ArraysSort.Int.p_sort | SHUFFLE | 90000 | 157.728 | 151.871 | 151.101 | 154.03 | 151.2
>> ArraysSort.Int.p_sort | SHUFFLE | 400000 | 441.166 | 715.243 | 449...
>
> Hello Vamsi (@vamsi-parasa),
>
> Could you please run benchmarking of 4 cases with **updated** test class **ArraysSortNew2**?
> https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSortNew2.java
>
> Put each DPQS class in java.util package and recompiling the JDK for each case as you
> did before, and run new class **ArraysSortNew2**.
>
> Find the sources there:
>
> https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSortNew2.java
> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01.java
> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r27b.java
> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r27p.java
> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r27s.java
>
> Thank you,
> Vladimir
Hi Vladimir (@iaroslavski),
Please see the data below.
Thanks,
Vamsi
<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">
Builder | Size | Stock JDK | b01 | r27b | r27p | r27s
-- | -- | -- | -- | -- | -- | --
RANDOM | 600 | 1.615 | 1.59 | 2.316 | 1.805 | 1.77
RANDOM | 2000 | 6.794 | 6.638 | 8.443 | 6.354 | 6.295
RANDOM | 90000 | 296.877 | 304.15 | 337.625 | 341.999 | 307.099
RANDOM | 400000 | 838.061 | 801.108 | 1136.688 | 1161.181 | 781.487
RANDOM | 3000000 | 5468.214 | 5452.125 | 8522.698 | 8476.445 | 5368.777
PERIOD | 600 | 0.877 | 0.875 | 0.663 | 0.663 | 0.685
PERIOD | 2000 | 1.57 | 1.548 | 1.458 | 1.451 | 1.487
PERIOD | 90000 | 97.208 | 97.677 | 106.01 | 106.516 | 106.629
PERIOD | 400000 | 237.4 | 264.103 | 235.466 | 231.349 | 231.235
PERIOD | 3000000 | 2604.56 | 2829.935 | 4867.668 | 4872.361 | 4888.391
STAGGER | 600 | 1.052 | 1.064 | 0.774 | 0.78 | 0.791
STAGGER | 2000 | 3.449 | 3.443 | 2.604 | 2.627 | 2.597
STAGGER | 90000 | 102.331 | 103.464 | 73.582 | 73.532 | 75.85
STAGGER | 400000 | 210.829 | 229.37 | 207.356 | 208.565 | 205.141
STAGGER | 3000000 | 2205.565 | 2174.588 | 2086.885 | 2070.132 | 2373.443
SHUFFLE | 600 | 1.885 | 1.892 | 1.934 | 1.36 | 1.386
SHUFFLE | 2000 | 6.787 | 6.724 | 7.338 | 4.994 | 4.96
SHUFFLE | 90000 | 158.065 | 154.48 | 152.874 | 148.337 | 140.703
SHUFFLE | 400000 | 415.089 | 424.777 | 676.272 | 676.89 | 410.717
SHUFFLE | 3000000 | 3999.006 | 4017.496 | 6861.872 | 6894.785 | 3880.883
RANDOM | 600 | 1.614 | 1.588 | 2.329 | 1.789 | 1.847
RANDOM | 2000 | 6.756 | 6.634 | 7.757 | 6.224 | 6.23
RANDOM | 90000 | 516.671 | 512.52 | 623.995 | 488.492 | 482.646
RANDOM | 400000 | 2400.818 | 2399.264 | 2903.654 | 2356.675 | 2358.409
RANDOM | 3000000 | 20933.23 | 20822.49 | 24428.27 | 20847.57 | 20868.68
PERIOD | 600 | 0.864 | 0.871 | 0.681 | 0.665 | 0.664
PERIOD | 2000 | 1.583 | 1.547 | 1.451 | 1.46 | 1.483
PERIOD | 90000 | 63.436 | 63.148 | 63.617 | 64.391 | 65.865
PERIOD | 400000 | 209.807 | 209.234 | 228.7 | 232.854 | 235.667
PERIOD | 3000000 | 1930.74 | 1943.51 | 1969.285 | 1991.225 | 1976.821
STAGGER | 600 | 1.07 | 1.068 | 0.772 | 0.78 | 0.77
STAGGER | 2000 | 3.455 | 3.451 | 2.582 | 2.579 | 2.566
STAGGER | 90000 | 148.7 | 390.833 | 123.443 | 123.166 | 123.64
STAGGER | 400000 | 661.018 | 662.037 | 568.606 | 584.962 | 594.313
STAGGER | 3000000 | 5170.135 | 5476.926 | 4431.776 | 4495.846 | 4538.187
SHUFFLE | 600 | 1.901 | 1.853 | 1.845 | 1.371 | 1.398
SHUFFLE | 2000 | 6.671 | 6.659 | 7.207 | 4.985 | 5.093
SHUFFLE | 90000 | 467.201 | 465.951 | 558.455 | 416.208 | 415.508
SHUFFLE | 400000 | 2168.29 | 2148.741 | 2633.919 | 2038.333 | 2026.282
SHUFFLE | 3000000 | 17994.7 | 17944.2 | 21180.53 | 17126.11 | 17082.88
</body>
</html>
-------------
PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1989270043
More information about the core-libs-dev
mailing list