Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Fri, 10 May 2024 22:08:47 GMT, Srinivas Vamsi Parasa wrote: >> Hello Vamsi (@vamsi-parasa), >> >> Could you please run the new benchmarking to finalize the best version? >> What you need is to compile and run JavaBenchmarkHarness: >> >> 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/DualPivotQuicksort_b01.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_11.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_11a.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_12.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_12a.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java >> >> Thank you, >> Vladimir > > Hi Vladimir (@iaroslavski), > > Please see the data below. > > Thanks, > Vamsi > > > name | builder | size | mode | count | score > -- | -- | -- | -- | -- | -- > b01 | RANDOM | 600 | avg | 325677 | 6.861 > b01 | RANDOM | 3000 | avg | 52041 | 77.313 > b01 | RANDOM | 9 | avg | 1217 | 4315.41 > b01 | RANDOM | 40 | avg | 242 | 22110.95 > b01 | RANDOM | 100 | avg | 90 | 58613.45 > b01 | REPEATED | 600 | avg | 651354 | 1.993 > b01 | REPEATED | 3000 | avg | 104083 | 13.026 > b01 | REPEATED | 9 | avg | 2435 | 741.97 > b01 | REPEATED | 40 | avg | 484 | 3161.073 > b01 | REPEATED | 100 | avg | 180 | 8363.671 > b01 | STAGGER | 600 | avg | 1954062 | 9.124 > b01 | STAGGER | 3000 | avg | 312251 | 10.026 > b01 | STAGGER | 9 | avg | 7305 | 286.313 > b01 | STAGGER | 40 | avg | 1453 | 1278.758 > b01 | STAGGER | 100 | avg | 542 | 3242.849 > b01 | SHUFFLE | 600 | avg | 325677 | 5.113 > b01 | SHUFFLE | 3000 | avg | 52041 | 28.85 > b01 | SHUFFLE | 9 | avg | 1217 | 1368.91 > b01 | SHUFFLE | 40 | avg | 242 | 5718.052 > b01 | SHUFFLE | 100 | avg | 90 | 15376.1 > r31_11 | RANDOM | 600 | avg | 325677 | 4.305 > r31_11 | RANDOM | 3000 | avg | 52041 | 73.399 > r31_11 | RANDOM | 9 | avg | 1217 | 3963.515 > r31_11 | RANDOM | 40 | avg | 242 | 19841.07 > r31_11 | RANDOM | 100 | avg | 90 | 53372.63 > r31_11 | REPEATED | 600 | avg | 651354 | 1.208 > r31_11 | REPEATED | 3000 | avg | 104083 | 6.206 > r31_11 | REPEATED | 9 | avg | 2435 | 614.159 > r31_11 | REPEATED | 40 | avg | 484 | 2615.923 > r31_11 | REPEATED | 100 | avg | 180 | 6553.801 > r31_11 | STAGGER | 600 | avg | 1954062 | 1.023 > r31_11 | STAGGER | 3000 | avg | 312251 | 4.406 > r31_11 | STAGGER | 9 | avg | 7305 | 129.76 > r31_11 | STAGGER | 40 | avg | 1453 | 600.581 > r31_11 | STAGGER | 100 | avg | 542 | 1588.827 > r31_11 | SHUFFLE | 600 | avg | 325677 | 2.887 > r31_11 | SHUFFLE | 3000 | avg | 52041 | 17.901 > r31_11 | SHUFFLE | 9 | avg | 1217 | 1033.808 > r31_11 | SHUFFLE | 40 | avg | 242 | 4686.188 > r31_11 | SHUFFLE | 100 | avg | 90 | 11589.67 > r31_11a | RANDOM | 600 | avg | 325677 | 4.277 > r31_11a | RANDOM | 3000 | avg | 52041 | 70.578 > r31_11a | RANDOM | 9 | avg | 1217 | 3963.836 > r31_11a | RANDOM | 40 | avg | 242 | 19771.67 > r31_11a | RANDOM | 100 | avg | 90 | 53417.95 > r31_11a | REPEATED | 600 | avg | 651354 | 1.112 > r31_11a | REPEATED | 3000 | avg | 104083 | 5.662 > r31_11a | REPEATED | 9 | avg | 2435 | 596.963 > r31_11a | REPEATED | 40 | avg | 484 | 2618.076 > r31_11a | REPEATED | 100 | avg | 180 | 6597.833 > r31_1... Hello Vamsi (@vamsi-parasa), Could you please run the new benchmarking to check sorting of all data types? What you need is to compile and run JavaBenchmarkHarness: 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/DualPivotQuicksort_b01.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r32.java https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java Thank you, Vladimir - PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-2179307223
Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Sun, 22 Oct 2023 17:26:52 GMT, Laurent Bourgès wrote: >> * improved mixed insertion sort (makes whole sorting faster) >> * introduced Radix which sort shows several times boost of performance and >> has linear complexity instead of n*ln(n) >> * improved merging sort for almost sorted data >> * optimized parallel sorting >> * improved step for pivot candidates and pivot partitioning >> * extended existing tests >> * added benchmarking JMH tests >> * suggested better buffer allocation: if no memory, it is switched to >> in-place sorting with no OutOfMemoryError, threshold is 1/16th heap >> >> I am going on previous PR by Vladimir Yaroslavskyi: >> https://github.com/openjdk/jdk/pull/3938 > > Laurent Bourgès has updated the pull request incrementally with one > additional commit since the last revision: > > add @SuppressWarnings (serial) Version for other data types is being prepared - PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-2156111460
Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Wed, 8 May 2024 20:37:28 GMT, Vladimir Yaroslavskiy wrote: >> Hi Vladimir (@iaroslavski), >> >> Please see the data below. >> >> Thanks, >> Vamsi >> >> name | builder | size | mode | count | score >> -- | -- | -- | -- | -- | -- >> b01 | RANDOM | 600 | avg | 325677 | 6.764 >> b01 | RANDOM | 3000 | avg | 52041 | 77.742 >> b01 | RANDOM | 9 | avg | 1217 | 4449.668 >> b01 | RANDOM | 40 | avg | 242 | 22764.05 >> b01 | RANDOM | 100 | avg | 90 | 60737.71 >> b01 | REPEATED | 600 | avg | 651354 | 1.723 >> b01 | REPEATED | 3000 | avg | 104083 | 12.383 >> b01 | REPEATED | 9 | avg | 2435 | 714.451 >> b01 | REPEATED | 40 | avg | 484 | 3039.447 >> b01 | REPEATED | 100 | avg | 180 | 8114.503 >> b01 | SAWTOOTH | 600 | avg | 1954062 | 1.009 >> b01 | SAWTOOTH | 3000 | avg | 312251 | 4.94 >> b01 | SAWTOOTH | 9 | avg | 7305 | 133.192 >> b01 | SAWTOOTH | 40 | avg | 1453 | 591.854 >> b01 | SAWTOOTH | 100 | avg | 542 | 1494.252 >> b01 | STAGGER | 600 | avg | 1954062 | 8.252 >> b01 | STAGGER | 3000 | avg | 312251 | 10.449 >> b01 | STAGGER | 9 | avg | 7305 | 287.811 >> b01 | STAGGER | 40 | avg | 1453 | 1288.92 >> b01 | STAGGER | 100 | avg | 542 | 3245.649 >> b01 | SHUFFLE | 600 | avg | 325677 | 5.199 >> b01 | SHUFFLE | 3000 | avg | 52041 | 29.734 >> b01 | SHUFFLE | 9 | avg | 1217 | 1392.125 >> b01 | SHUFFLE | 40 | avg | 242 | 5772.859 >> b01 | SHUFFLE | 100 | avg | 90 | 15483.65 >> r30 | RANDOM | 600 | avg | 325677 | 4.307 >> r30 | RANDOM | 3000 | avg | 52041 | 71.438 >> r30 | RANDOM | 9 | avg | 1217 | 3971.947 >> r30 | RANDOM | 40 | avg | 242 | 19924.32 >> r30 | RANDOM | 100 | avg | 90 | 53671.9 >> r30 | REPEATED | 600 | avg | 651354 | 1.36 >> r30 | REPEATED | 3000 | avg | 104083 | 6.415 >> r30 | REPEATED | 9 | avg | 2435 | 578.708 >> r30 | REPEATED | 40 | avg | 484 | 2488.414 >> r30 | REPEATED | 100 | avg | 180 | 6280.025 >> r30 | SAWTOOTH | 600 | avg | 1954062 | 0.488 >> r30 | SAWTOOTH | 3000 | avg | 312251 | 2.409 >> r30 | SAWTOOTH | 9 | avg | 7305 | 71.98 >> r30 | SAWTOOTH | 40 | avg | 1453 | 343.433 >> r30 | SAWTOOTH | 100 | avg | 542 | 954.287 >> r30 | STAGGER | 600 | avg | 1954062 | 1.064 >> r30 | STAGGER | 3000 | avg | 312251 | 4.559 >> r30 | STAGGER | 9 | avg | 7305 | 135.383 >> r30 | STAGGER | 40 | avg | 1453 | 626.657 >> r30 | STAGGER | 100 | avg | 542 | 1653.92 >> r30 | SHUFFLE | 600 | avg | 325677 | 2.924 >> r30 | SHUFFLE | 3000 | avg | 52041 | 18.819 >> r30 | SHUFFLE | 9 | avg | 1217 | 1019.036 >> r30 | SHUFFLE | 40 | avg | 242 | 4661.484 >> r30 | SHUFFLE | 100 ... > > Hello Vamsi (@vamsi-parasa), > > Could you please run the new benchmarking to finalize the best version? > What you need is to compile and run JavaBenchmarkHarness: > > 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/DualPivotQuicksort_b01.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_11.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_11a.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_12.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_12a.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java > > Thank you, > Vladimir Hi Vladimir (@iaroslavski), Please see the data below. Thanks, Vamsi name | builder | size | mode | count | score -- | -- | -- | -- | -- | -- b01 | RANDOM | 600 | avg | 325677 | 6.861 b01 | RANDOM | 3000 | avg | 52041 | 77.313 b01 | RANDOM | 9 | avg | 1217 | 4315.41 b01 | RANDOM | 40 | avg | 242 | 22110.95 b01 | RANDOM | 100 | avg | 90 | 58613.45 b01 | REPEATED | 600 | avg | 651354 | 1.993 b01 | REPEATED | 3000 | avg | 104083 | 13.026 b01 | REPEATED | 9 | avg | 2435 | 741.97 b01 | REPEATED | 40 | avg | 484 | 3161.073 b01 | REPEATED | 100 | avg | 180 | 8363.671 b01 | STAGGER | 600 | avg | 1954062 | 9.124 b01 | STAGGER | 3000 | avg | 312251 | 10.026 b01 | STAGGER | 9 | avg | 7305 | 286.313 b01 | STAGGER | 40 | avg | 1453 | 1278.758 b01 | STAGGER | 100 | avg | 542 | 3242.849 b01 | SHUFFLE | 600 | avg | 325677 | 5.113 b01 | SHUFFLE | 3000 | avg | 52041 | 28.85 b01 | SHUFFLE | 9 | avg | 1217 | 1368.91 b01 | SHUFFLE | 40 | avg | 242 | 5718.052 b01 | SHUFFLE | 100 | avg | 90 | 15376.1 r31_11 | RANDOM | 600 | avg | 325677 | 4.305 r31_11 | RANDOM | 3000 | avg | 52041 | 73.399 r31_11 | RANDOM | 9 | avg | 1217 | 3963.515 r31_11 | RANDOM | 40 | avg | 242 | 19841.07 r31_11 | RANDOM | 100 | avg | 90 | 53372.63 r31_11 | REPEATED | 600 | avg | 651354 | 1.208 r31_11 | REPEATED | 3000 | avg | 104083 | 6.206 r31_11 | REPEATED |
Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Mon, 6 May 2024 23:26:49 GMT, Srinivas Vamsi Parasa wrote: >> Hello Vamsi (@vamsi-parasa), >> >> Could you please run the new benchmarking to detect the best case >> for Radix sort and parallel sorting? >> >> What you need is to compile and run JavaBenchmarkHarness: >> >> 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/DualPivotQuicksort_b01.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_a.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_5.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_11.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_12.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_13.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_14.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_21.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_23.java >> https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java >> >> Thank you, >> Vladimir > > Hi Vladimir (@iaroslavski), > > Please see the data below. > > Thanks, > Vamsi > > name | builder | size | mode | count | score > -- | -- | -- | -- | -- | -- > b01 | RANDOM | 600 | avg | 325677 | 6.764 > b01 | RANDOM | 3000 | avg | 52041 | 77.742 > b01 | RANDOM | 9 | avg | 1217 | 4449.668 > b01 | RANDOM | 40 | avg | 242 | 22764.05 > b01 | RANDOM | 100 | avg | 90 | 60737.71 > b01 | REPEATED | 600 | avg | 651354 | 1.723 > b01 | REPEATED | 3000 | avg | 104083 | 12.383 > b01 | REPEATED | 9 | avg | 2435 | 714.451 > b01 | REPEATED | 40 | avg | 484 | 3039.447 > b01 | REPEATED | 100 | avg | 180 | 8114.503 > b01 | SAWTOOTH | 600 | avg | 1954062 | 1.009 > b01 | SAWTOOTH | 3000 | avg | 312251 | 4.94 > b01 | SAWTOOTH | 9 | avg | 7305 | 133.192 > b01 | SAWTOOTH | 40 | avg | 1453 | 591.854 > b01 | SAWTOOTH | 100 | avg | 542 | 1494.252 > b01 | STAGGER | 600 | avg | 1954062 | 8.252 > b01 | STAGGER | 3000 | avg | 312251 | 10.449 > b01 | STAGGER | 9 | avg | 7305 | 287.811 > b01 | STAGGER | 40 | avg | 1453 | 1288.92 > b01 | STAGGER | 100 | avg | 542 | 3245.649 > b01 | SHUFFLE | 600 | avg | 325677 | 5.199 > b01 | SHUFFLE | 3000 | avg | 52041 | 29.734 > b01 | SHUFFLE | 9 | avg | 1217 | 1392.125 > b01 | SHUFFLE | 40 | avg | 242 | 5772.859 > b01 | SHUFFLE | 100 | avg | 90 | 15483.65 > r30 | RANDOM | 600 | avg | 325677 | 4.307 > r30 | RANDOM | 3000 | avg | 52041 | 71.438 > r30 | RANDOM | 9 | avg | 1217 | 3971.947 > r30 | RANDOM | 40 | avg | 242 | 19924.32 > r30 | RANDOM | 100 | avg | 90 | 53671.9 > r30 | REPEATED | 600 | avg | 651354 | 1.36 > r30 | REPEATED | 3000 | avg | 104083 | 6.415 > r30 | REPEATED | 9 | avg | 2435 | 578.708 > r30 | REPEATED | 40 | avg | 484 | 2488.414 > r30 | REPEATED | 100 | avg | 180 | 6280.025 > r30 | SAWTOOTH | 600 | avg | 1954062 | 0.488 > r30 | SAWTOOTH | 3000 | avg | 312251 | 2.409 > r30 | SAWTOOTH | 9 | avg | 7305 | 71.98 > r30 | SAWTOOTH | 40 | avg | 1453 | 343.433 > r30 | SAWTOOTH | 100 | avg | 542 | 954.287 > r30 | STAGGER | 600 | avg | 1954062 | 1.064 > r30 | STAGGER | 3000 | avg | 312251 | 4.559 > r30 | STAGGER | 9 | avg | 7305 | 135.383 > r30 | STAGGER | 40 | avg | 1453 | 626.657 > r30 | STAGGER | 100 | avg | 542 | 1653.92 > r30 | SHUFFLE | 600 | avg | 325677 | 2.924 > r30 | SHUFFLE | 3000 | avg | 52041 | 18.819 > r30 | SHUFFLE | 9 | avg | 1217 | 1019.036 > r30 | SHUFFLE | 40 | avg | 242 | 4661.484 > r30 | SHUFFLE | 100 | avg | 90 | 11333.52 > r30_a | RANDOM | 600 | avg | 325677 | 4.024 > r30_a | RANDOM | 3000 | avg | 52041 | 72.86 > r30_a | ... Hello Vamsi (@vamsi-parasa), Could you please run the new benchmarking to finalize the best version? What you need is to compile and run JavaBenchmarkHarness: 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/DualPivotQuicksort_b01.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_11.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_11a.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r31_12.java
Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Tue, 30 Apr 2024 22:01:30 GMT, Vladimir Yaroslavskiy wrote: >> Hi Vladimir (@iaroslavski), >> >> Please see the data below: >> >> Thanks, >> Vamsi >> >> >> >> name | builder | size | mode | count | score >> -- | -- | -- | -- | -- | -- >> b01 | RANDOM | 600 | avg | 325677 | 6.862 >> b01 | RANDOM | 3000 | avg | 52041 | 82.233 >> b01 | RANDOM | 9 | avg | 1217 | 4456.51 >> b01 | RANDOM | 40 | avg | 242 | 22923.28 >> b01 | RANDOM | 100 | avg | 90 | 60598.84 >> b01 | REPEATED | 600 | avg | 651354 | 1.933 >> b01 | REPEATED | 3000 | avg | 104083 | 13.753 >> b01 | REPEATED | 9 | avg | 2435 | 723.039 >> b01 | REPEATED | 40 | avg | 484 | 3084.416 >> b01 | REPEATED | 100 | avg | 180 | 8234.428 >> b01 | STAGGER | 600 | avg | 1954062 | 1.005 >> b01 | STAGGER | 3000 | avg | 312251 | 4.945 >> b01 | STAGGER | 9 | avg | 7305 | 133.126 >> b01 | STAGGER | 40 | avg | 1453 | 592.144 >> b01 | STAGGER | 100 | avg | 542 | 1493.876 >> b01 | SHUFFLE | 600 | avg | 325677 | 5.12 >> b01 | SHUFFLE | 3000 | avg | 52041 | 29.252 >> b01 | SHUFFLE | 9 | avg | 1217 | 1396.664 >> b01 | SHUFFLE | 40 | avg | 242 | 5743.489 >> b01 | SHUFFLE | 100 | avg | 90 | 15490.81 >> b01_ins | RANDOM | 600 | avg | 325677 | 7.594 >> b01_ins | RANDOM | 3000 | avg | 52041 | 78.631 >> b01_ins | RANDOM | 9 | avg | 1217 | 4312.511 >> b01_ins | RANDOM | 40 | avg | 242 | 22108.18 >> b01_ins | RANDOM | 100 | avg | 90 | 58467.16 >> b01_ins | REPEATED | 600 | avg | 651354 | 1.569 >> b01_ins | REPEATED | 3000 | avg | 104083 | 11.313 >> b01_ins | REPEATED | 9 | avg | 2435 | 720.838 >> b01_ins | REPEATED | 40 | avg | 484 | 3003.673 >> b01_ins | REPEATED | 100 | avg | 180 | 8144.944 >> b01_ins | STAGGER | 600 | avg | 1954062 | 0.98 >> b01_ins | STAGGER | 3000 | avg | 312251 | 4.948 >> b01_ins | STAGGER | 9 | avg | 7305 | 132.909 >> b01_ins | STAGGER | 40 | avg | 1453 | 592.572 >> b01_ins | STAGGER | 100 | avg | 542 | 1492.627 >> b01_ins | SHUFFLE | 600 | avg | 325677 | 4.092 >> b01_ins | SHUFFLE | 3000 | avg | 52041 | 27.138 >> b01_ins | SHUFFLE | 9 | avg | 1217 | 1304.326 >> b01_ins | SHUFFLE | 40 | avg | 242 | 5465.745 >> b01_ins | SHUFFLE | 100 | avg | 90 | 14585.08 >> b01_mrg | RANDOM | 600 | avg | 325677 | 7.139 >> b01_mrg | RANDOM | 3000 | avg | 52041 | 81.01 >> b01_mrg | RANDOM | 9 | avg | 1217 | 4266.084 >> b01_mrg | RANDOM | 40 | avg | 242 | 21937.77 >> b01_mrg | RANDOM | 100 | avg | 90 | 58177.72 >> b01_mrg | REPEATED | 600 | avg | 651354 | 1.36 >> b01_mrg | REPEATED | 3000 | avg | 104083 | 9.013 >> b01_mrg | REPEATED ... > > Hello Vamsi (@vamsi-parasa), > > Could you please run the new benchmarking to detect the best case > for Radix sort and parallel sorting? > > What you need is to compile and run JavaBenchmarkHarness: > > 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/DualPivotQuicksort_b01.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_a.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_5.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_11.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_12.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_13.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_14.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_21.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_23.java > https://github.com/iaroslavski/sorting/blob/master/radixsort/JavaBenchmarkHarness.java > > Thank you, > Vladimir Hi Vladimir (@iaroslavski), Please see the data below. Thanks, Vamsi name | builder | size | mode | count | score -- | -- | -- | -- | -- | -- b01 | RANDOM | 600 | avg | 325677 | 6.764 b01 | RANDOM | 3000 | avg | 52041 | 77.742 b01 | RANDOM | 9 | avg | 1217 | 4449.668 b01 | RANDOM | 40 | avg | 242 | 22764.05 b01 | RANDOM | 100 | avg | 90 | 60737.71 b01 | REPEATED | 600 | avg | 651354 | 1.723 b01 | REPEATED | 3000 | avg | 104083 | 12.383 b01 | REPEATED | 9 | avg | 2435 | 714.451 b01 | REPEATED | 40 | avg | 484 | 3039.447 b01 | REPEATED | 100 | avg | 180 | 8114.503 b01 | SAWTOOTH | 600 | avg | 1954062 | 1.009 b01 | SAWTOOTH | 3000 | avg | 312251 | 4.94 b01 | SAWTOOTH | 9 | avg | 7305 | 133.192 b01 | SAWTOOTH | 40 | avg | 1453 | 591.854 b01 | SAWTOOTH | 100 | avg | 542 | 1494.252 b01 | STAGGER | 600 | avg | 1954062 | 8.252 b01 | STAGGER | 3000 |
Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Sun, 21 Apr 2024 04:37:45 GMT, Srinivas Vamsi Parasa wrote: >> 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 > > Hi Vladimir (@iaroslavski), > > Please see the data below: > > Thanks, > Vamsi > > > > name | builder | size | mode | count | score > -- | -- | -- | -- | -- | -- > b01 | RANDOM | 600 | avg | 325677 | 6.862 > b01 | RANDOM | 3000 | avg | 52041 | 82.233 > b01 | RANDOM | 9 | avg | 1217 | 4456.51 > b01 | RANDOM | 40 | avg | 242 | 22923.28 > b01 | RANDOM | 100 | avg | 90 | 60598.84 > b01 | REPEATED | 600 | avg | 651354 | 1.933 > b01 | REPEATED | 3000 | avg | 104083 | 13.753 > b01 | REPEATED | 9 | avg | 2435 | 723.039 > b01 | REPEATED | 40 | avg | 484 | 3084.416 > b01 | REPEATED | 100 | avg | 180 | 8234.428 > b01 | STAGGER | 600 | avg | 1954062 | 1.005 > b01 | STAGGER | 3000 | avg | 312251 | 4.945 > b01 | STAGGER | 9 | avg | 7305 | 133.126 > b01 | STAGGER | 40 | avg | 1453 | 592.144 > b01 | STAGGER | 100 | avg | 542 | 1493.876 > b01 | SHUFFLE | 600 | avg | 325677 | 5.12 > b01 | SHUFFLE | 3000 | avg | 52041 | 29.252 > b01 | SHUFFLE | 9 | avg | 1217 | 1396.664 > b01 | SHUFFLE | 40 | avg | 242 | 5743.489 > b01 | SHUFFLE | 100 | avg | 90 | 15490.81 > b01_ins | RANDOM | 600 | avg | 325677 | 7.594 > b01_ins | RANDOM | 3000 | avg | 52041 | 78.631 > b01_ins | RANDOM | 9 | avg | 1217 | 4312.511 > b01_ins | RANDOM | 40 | avg | 242 | 22108.18 > b01_ins | RANDOM | 100 | avg | 90 | 58467.16 > b01_ins | REPEATED | 600 | avg | 651354 | 1.569 > b01_ins | REPEATED | 3000 | avg | 104083 | 11.313 > b01_ins | REPEATED | 9 | avg | 2435 | 720.838 > b01_ins | REPEATED | 40 | avg | 484 | 3003.673 > b01_ins | REPEATED | 100 | avg | 180 | 8144.944 > b01_ins | STAGGER | 600 | avg | 1954062 | 0.98 > b01_ins | STAGGER | 3000 | avg | 312251 | 4.948 > b01_ins | STAGGER | 9 | avg | 7305 | 132.909 > b01_ins | STAGGER | 40 | avg | 1453 | 592.572 > b01_ins | STAGGER | 100 | avg | 542 | 1492.627 > b01_ins | SHUFFLE | 600 | avg | 325677 | 4.092 > b01_ins | SHUFFLE | 3000 | avg | 52041 | 27.138 > b01_ins | SHUFFLE | 9 | avg | 1217 | 1304.326 > b01_ins | SHUFFLE | 40 | avg | 242 | 5465.745 > b01_ins | SHUFFLE | 100 | avg | 90 | 14585.08 > b01_mrg | RANDOM | 600 | avg | 325677 | 7.139 > b01_mrg | RANDOM | 3000 | avg | 52041 | 81.01 > b01_mrg | RANDOM | 9 | avg | 1217 | 4266.084 > b01_mrg | RANDOM | 40 | avg | 242 | 21937.77 > b01_mrg | RANDOM | 100 | avg | 90 | 58177.72 > b01_mrg | REPEATED | 600 | avg | 651354 | 1.36 > b01_mrg | REPEATED | 3000 | avg | 104083 | 9.013 > b01_mrg | REPEATED | 9 | avg | 2435 | 737.684 > b01_mrg | REPEATED | 40 | avg | 484 | 3152.447 > b01_mrg | REPEATED | 100 | avg |... Hello Vamsi (@vamsi-parasa), Could you please run the new benchmarking to detect the best case for Radix sort and parallel sorting? What you need is to compile and run JavaBenchmarkHarness: 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/DualPivotQuicksort_b01.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_a.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_11.java https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r30_12.java
Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Sun, 21 Apr 2024 04:37:45 GMT, Srinivas Vamsi Parasa wrote: >> 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 > > Hi Vladimir (@iaroslavski), > > Please see the data below: > > Thanks, > Vamsi > > > > name | builder | size | mode | count | score > -- | -- | -- | -- | -- | -- > b01 | RANDOM | 600 | avg | 325677 | 6.862 > b01 | RANDOM | 3000 | avg | 52041 | 82.233 > b01 | RANDOM | 9 | avg | 1217 | 4456.51 > b01 | RANDOM | 40 | avg | 242 | 22923.28 > b01 | RANDOM | 100 | avg | 90 | 60598.84 > b01 | REPEATED | 600 | avg | 651354 | 1.933 > b01 | REPEATED | 3000 | avg | 104083 | 13.753 > b01 | REPEATED | 9 | avg | 2435 | 723.039 > b01 | REPEATED | 40 | avg | 484 | 3084.416 > b01 | REPEATED | 100 | avg | 180 | 8234.428 > b01 | STAGGER | 600 | avg | 1954062 | 1.005 > b01 | STAGGER | 3000 | avg | 312251 | 4.945 > b01 | STAGGER | 9 | avg | 7305 | 133.126 > b01 | STAGGER | 40 | avg | 1453 | 592.144 > b01 | STAGGER | 100 | avg | 542 | 1493.876 > b01 | SHUFFLE | 600 | avg | 325677 | 5.12 > b01 | SHUFFLE | 3000 | avg | 52041 | 29.252 > b01 | SHUFFLE | 9 | avg | 1217 | 1396.664 > b01 | SHUFFLE | 40 | avg | 242 | 5743.489 > b01 | SHUFFLE | 100 | avg | 90 | 15490.81 > b01_ins | RANDOM | 600 | avg | 325677 | 7.594 > b01_ins | RANDOM | 3000 | avg | 52041 | 78.631 > b01_ins | RANDOM | 9 | avg | 1217 | 4312.511 > b01_ins | RANDOM | 40 | avg | 242 | 22108.18 > b01_ins | RANDOM | 100 | avg | 90 | 58467.16 > b01_ins | REPEATED | 600 | avg | 651354 | 1.569 > b01_ins | REPEATED | 3000 | avg | 104083 | 11.313 > b01_ins | REPEATED | 9 | avg | 2435 | 720.838 > b01_ins | REPEATED | 40 | avg | 484 | 3003.673 > b01_ins | REPEATED | 100 | avg | 180 | 8144.944 > b01_ins | STAGGER | 600 | avg | 1954062 | 0.98 > b01_ins | STAGGER | 3000 | avg | 312251 | 4.948 > b01_ins | STAGGER | 9 | avg | 7305 | 132.909 > b01_ins | STAGGER | 40 | avg | 1453 | 592.572 > b01_ins | STAGGER | 100 | avg | 542 | 1492.627 > b01_ins | SHUFFLE | 600 | avg | 325677 | 4.092 > b01_ins | SHUFFLE | 3000 | avg | 52041 | 27.138 > b01_ins | SHUFFLE | 9 | avg | 1217 | 1304.326 > b01_ins | SHUFFLE | 40 | avg | 242 | 5465.745 > b01_ins | SHUFFLE | 100 | avg | 90 | 14585.08 > b01_mrg | RANDOM | 600 | avg | 325677 | 7.139 > b01_mrg | RANDOM | 3000 | avg | 52041 | 81.01 > b01_mrg | RANDOM | 9 | avg | 1217 | 4266.084 > b01_mrg | RANDOM | 40 | avg | 242 | 21937.77 > b01_mrg | RANDOM | 100 | avg | 90 | 58177.72 > b01_mrg | REPEATED | 600 | avg | 651354 | 1.36 > b01_mrg | REPEATED | 3000 | avg | 104083 | 9.013 > b01_mrg | REPEATED | 9 | avg | 2435 | 737.684 > b01_mrg | REPEATED | 40 | avg | 484 | 3152.447 > b01_mrg | REPEATED | 100 | avg |... Thank you, @vamsi-parasa ! I will investigate the result - PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-2068075025
Re: RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Tue, 9 Apr 2024 21:36:46 GMT, Vladimir Yaroslavskiy wrote: >>> 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 Hi Vladimir (@iaroslavski), Please see the data below: Thanks, Vamsi name | builder | size | mode | count | score -- | -- | -- | -- | -- | -- b01 | RANDOM | 600 | avg | 325677 | 6.862 b01 | RANDOM | 3000 | avg | 52041 | 82.233 b01 | RANDOM | 9 | avg | 1217 | 4456.51 b01 | RANDOM | 40 | avg | 242 | 22923.28 b01 | RANDOM | 100 | avg | 90 | 60598.84 b01 | REPEATED | 600 | avg | 651354 | 1.933 b01 | REPEATED | 3000 | avg | 104083 | 13.753 b01 | REPEATED | 9 | avg | 2435 | 723.039 b01 | REPEATED | 40 | avg | 484 | 3084.416 b01 | REPEATED | 100 | avg | 180 | 8234.428 b01 | STAGGER | 600 | avg | 1954062 | 1.005 b01 | STAGGER | 3000 | avg | 312251 | 4.945 b01 | STAGGER | 9 | avg | 7305 | 133.126 b01 | STAGGER | 40 | avg | 1453 | 592.144 b01 | STAGGER | 100 | avg | 542 | 1493.876 b01 | SHUFFLE | 600 | avg | 325677 | 5.12 b01 | SHUFFLE | 3000 | avg | 52041 | 29.252 b01 | SHUFFLE | 9 | avg | 1217 | 1396.664 b01 | SHUFFLE | 40 | avg | 242 | 5743.489 b01 | SHUFFLE | 100 | avg | 90 | 15490.81 b01_ins | RANDOM | 600 | avg | 325677 | 7.594 b01_ins | RANDOM | 3000 | avg | 52041 | 78.631 b01_ins | RANDOM | 9 | avg | 1217 | 4312.511 b01_ins | RANDOM | 40 | avg | 242 | 22108.18 b01_ins | RANDOM | 100 | avg | 90 | 58467.16 b01_ins | REPEATED | 600 | avg | 651354 | 1.569 b01_ins | REPEATED | 3000 | avg | 104083 | 11.313 b01_ins | REPEATED | 9 | avg | 2435 | 720.838 b01_ins | REPEATED | 40 | avg | 484 | 3003.673 b01_ins | REPEATED | 100 | avg | 180 | 8144.944 b01_ins | STAGGER | 600 | avg | 1954062 | 0.98 b01_ins | STAGGER | 3000 | avg | 312251 | 4.948 b01_ins | STAGGER | 9 | avg | 7305 | 132.909 b01_ins | STAGGER | 40 | avg | 1453 | 592.572 b01_ins | STAGGER | 100 | avg | 542 | 1492.627 b01_ins | SHUFFLE | 600 | avg | 325677 | 4.092 b01_ins | SHUFFLE | 3000 | avg | 52041 | 27.138 b01_ins | SHUFFLE | 9 | avg | 1217 | 1304.326 b01_ins | SHUFFLE | 40 | avg | 242 | 5465.745 b01_ins | SHUFFLE | 100 | avg | 90 | 14585.08 b01_mrg | RANDOM | 600 | avg | 325677 | 7.139 b01_mrg | RANDOM | 3000 | avg | 52041 | 81.01 b01_mrg | RANDOM | 9 | avg | 1217 | 4266.084 b01_mrg | RANDOM | 40 | avg | 242 | 21937.77 b01_mrg | RANDOM | 100 | avg | 90 | 58177.72 b01_mrg | REPEATED | 600 | avg | 651354 | 1.36 b01_mrg | REPEATED | 3000 | avg | 104083 | 9.013 b01_mrg | REPEATED | 9 | avg | 2435 | 737.684 b01_mrg | REPEATED | 40 | avg | 484 | 3152.447 b01_mrg | REPEATED | 100 | avg | 180 | 8366.866 b01_mrg | STAGGER | 600 | avg | 1954062 | 0.73 b01_mrg | STAGGER | 3000 | avg | 312251 | 3.733 b01_mrg | STAGGER | 9 | avg | 7305 | 114.35 b01_mrg | STAGGER | 40 | avg | 1453 | 524.821 b01_mrg | STAGGER | 100 | avg | 542 | 1351.504 b01_mrg | SHUFFLE | 600 | avg | 325677 | 4.986 b01_mrg |
