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

Tue Apr 9 21:39:08 UTC 2024

On Mon, 11 Mar 2024 19:31:45 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> 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.4...
>
>> Hi Vamsi (@vamsi-parasa), few questions on your test environment:
>> 
>> * what are the hardware specs of your server ?
>> * bare-metal or virtual ?
>> * are other services or big processes running ?
>> * os tuning ? CPU HT: off? Fixed CPU governor or frequency ?
>> * isolation using taskset ?
>> 
>> Maybe C2 JIT (+ CDS archive) are given more performance on stock jdk sort than same code running outside jdk...
>> 
>> Thanks, Laurent
> 
> Hi Laurent,
> 
> The benchmarks are run on Intel TigerLake Core i7 machine. It's bare-metal without any virtualization. HT is ON and there is no other specific OS tuning or isolation using taskset.
> 
> Thanks,
> Vamsi

Hello Vamsi (@vamsi-parasa),

Could you please run the new benchmarking?
To save time and don't patch JDK several times, I've created JavaBenchmarkHarness
class which is under package java.util and compares several versions of DPQS.
Also I prepared several versions of current sorting source from JDK to detect what is going wrong.

What you need is to compile and run JavaBenchmarkHarness once:

javac --patch-module java.base=. -d classes *.java
java -XX:CompileThreshold=1 -XX:-TieredCompilation --patch-module java.base=classes -cp classes java.util.JavaBenchmarkHarness

Find the sources there:

https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java  
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_ins.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_mrg.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_piv.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_b01_prt.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r29p.java
https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r29p5.java

Thank you,
Vladimir

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

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