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

Fri Feb 16 23:46:01 UTC 2024

On Thu, 8 Feb 2024 20:04:20 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:

>> Hi Vladimir (@iaroslavski),
>> 
>> The new ArraysSortNew.Java has compilation issues:
>> 
>> 
>> error: DualPivotQuicksort is not public in java.util; cannot be accessed from outside package
>>              java.util.DualPivotQuicksort.sort(b, PARALLELISM, 0, b.length);
>> 
>> Have you run into this issue? 
>> 
>> Thanks,
>> Vamsi
>
> Hi Vamsi (@vamsi-parasa),
> 
> My fault, there was an incorrect version of ArraysSortNew.java. Methods, of course, should be
> 
> @Benchmark
> public void sort() {
>     Arrays.sort(b);
> }
> 
> @Benchmark
> public void p_sort() {
>     Arrays.parallelSort(b);
> }
> 
> I uploaded correct version, see
> https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSortNew.java
> 
> I also comment that pom.xml contains additional options (I guess you have the same)
> <arg>--add-exports=java.base/jdk.internal.misc=ALL-UNNAMED</arg>
> <arg>--add-exports=java.base/jdk.internal.vm.annotation=ALL-UNNAMED</arg>
> full text is there https://github.com/iaroslavski/sorting/blob/master/radixsort/pom.xml
> 
> and command to run test is
> java --add-exports=java.base/jdk.internal.vm.annotation=ALL-UNNAMED --add-exports=java.base/jdk.internal.misc=ALL-UNNAMED -jar target/benchmarks.jar
> 
> I assume that each variant of DPQS (DualPivotQuicksort_jdk, DualPivotQuicksort_r20p, DualPivotQuicksort_r20s, DualPivotQuicksort_r25p, DualPivotQuicksort_r25s) is renamed to DualPivotQuicksort and put into
> package java.util. Then benchmarking for a given variant with patched JDK is executed.
> 
> Thank you,
> Vladimir

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.698 | 699.75 | 447.069
ArraysSort.Int.p_sort | SHUFFLE | 3000000 | 4326.88 | 7133.045 | 4205.47 | 7161.862 | 4337.321
ArraysSort.Int.sort | RANDOM | 600 | 1.671 | 2.707 | 2.741 | 2.698 | 2.779
ArraysSort.Int.sort | RANDOM | 2000 | 7.265 | 8.226 | 8.942 | 8.193 | 8.339
ArraysSort.Int.sort | RANDOM | 90000 | 529.054 | 559.499 | 554.29 | 566.009 | 559.131
ArraysSort.Int.sort | RANDOM | 400000 | 2448.226 | 2654.71 | 2622.964 | 2629.673 | 2619.051
ArraysSort.Int.sort | RANDOM | 3000000 | 21471.133 | 22670.45 | 22654.94 | 22811.7 | 22957.97
ArraysSort.Int.sort | REPEATED | 600 | 0.517 | 0.578 | 0.578 | 0.587 | 0.568
ArraysSort.Int.sort | REPEATED | 2000 | 1.136 | 1.228 | 1.215 | 1.377 | 1.222
ArraysSort.Int.sort | REPEATED | 90000 | 57.575 | 56.406 | 56.542 | 56.068 | 56.77
ArraysSort.Int.sort | REPEATED | 400000 | 178.874 | 173.883 | 176.098 | 171.975 | 172.067
ArraysSort.Int.sort | REPEATED | 3000000 | 1856.71 | 1588.104 | 1489.842 | 1480.34 | 1522.399
ArraysSort.Int.sort | STAGGER | 600 | 1.143 | 0.893 | 0.901 | 0.896 | 0.906
ArraysSort.Int.sort | STAGGER | 2000 | 3.726 | 3.062 | 3.18 | 3.061 | 3.169
ArraysSort.Int.sort | STAGGER | 90000 | 138.503 | 135.008 | 134.023 | 136.328 | 136.026
ArraysSort.Int.sort | STAGGER | 400000 | 615.732 | 608.269 | 609.348 | 606.986 | 603.287
ArraysSort.Int.sort | STAGGER | 3000000 | 4914.443 | 4578.733 | 4584.407 | 4591.832 | 4613.16
ArraysSort.Int.sort | SHUFFLE | 600 | 2.137 | 2.886 | 2.948 | 2.898 | 2.871
ArraysSort.Int.sort | SHUFFLE | 2000 | 7.029 | 7.697 | 8.133 | 7.666 | 8.122
ArraysSort.Int.sort | SHUFFLE | 90000 | 482.23 | 463.796 | 454.744 | 463.55 | 462.538
ArraysSort.Int.sort | SHUFFLE | 400000 | 2195.147 | 2276.979 | 2233.066 | 2234.718 | 2216.289
ArraysSort.Int.sort | SHUFFLE | 3000000 | 18654.727 | 19861.77 | 18980.49 | 19039.88 | 19081.4

</body>

</html>

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

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