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

Tue Feb 27 20:56:59 UTC 2024

On Fri, 16 Feb 2024 23:43:15 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

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

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

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

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