On Sun, 22 Oct 2023 17:26:52 GMT, Laurent Bourgès <lbour...@openjdk.org> 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) Comparision of Stock JDK ( with AVX512sort) vs. Radix sort for All (https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_RadixForAll.java) <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 (us/op) | Builder | (size) | Stock JDK (+AVX512 sort) | Radix for All (+AVX512 sort) | Speedup -- | -- | -- | -- | -- | -- ArraysSort.Int.testSort | RANDOM | 800 | 3.345 | 2.329 | 1.436 ArraysSort.Int.testSort | RANDOM | 7000 | 31.617 | 29.886 | 1.058 ArraysSort.Int.testSort | RANDOM | 50000 | 304.558 | 258.662 | 1.177 ArraysSort.Int.testSort | RANDOM | 300000 | 2097.165 | 1626.93 | 1.289 ArraysSort.Int.testSort | RANDOM | 2000000 | 15357.603 | 11158.73 | 1.376 ArraysSort.Int.testSort | REPEATED | 800 | 0.921 | 0.997 | 0.924 ArraysSort.Int.testSort | REPEATED | 7000 | 3.386 | 4.434 | 0.764 ArraysSort.Int.testSort | REPEATED | 50000 | 22.774 | 22.85 | 0.997 ArraysSort.Int.testSort | REPEATED | 300000 | 161.34 | 172.827 | 0.934 ArraysSort.Int.testSort | REPEATED | 2000000 | 1138.572 | 994.153 | 1.145 ArraysSort.Int.testSort | STAGGER | 800 | 2.13 | 2.383 | 0.894 ArraysSort.Int.testSort | STAGGER | 7000 | 17.967 | 19.506 | 0.921 ArraysSort.Int.testSort | STAGGER | 50000 | 121.2 | 145.089 | 0.835 ArraysSort.Int.testSort | STAGGER | 300000 | 728.444 | 858.927 | 0.848 ArraysSort.Int.testSort | STAGGER | 2000000 | 4943.958 | 5976.788 | 0.827 ArraysSort.Int.testSort | SHUFFLE | 800 | 2.834 | 2.348 | 1.207 ArraysSort.Int.testSort | SHUFFLE | 7000 | 30.086 | 38.303 | 0.785 ArraysSort.Int.testSort | SHUFFLE | 50000 | 268.786 | 258.078 | 1.041 ArraysSort.Int.testSort | SHUFFLE | 300000 | 1996.706 | 2439.81 | 0.818 ArraysSort.Int.testSort | SHUFFLE | 2000000 | 14108.444 | 19083.22 | 0.739 ArraysSort.Int.testSortParallel | RANDOM | 800 | 3.318 | 8.074 | 0.41 ArraysSort.Int.testSortParallel | RANDOM | 7000 | 26.533 | 44.091 | 0.60 ArraysSort.Int.testSortParallel | RANDOM | 50000 | 213.697 | 173.553 | 1.23 ArraysSort.Int.testSortParallel | RANDOM | 300000 | 682.952 | 829.98 | 0.82 ArraysSort.Int.testSortParallel | RANDOM | 2000000 | 3872.564 | 5170.138 | 0.75 ArraysSort.Int.testSortParallel | REPEATED | 800 | 0.907 | 5.83 | 0.16 ArraysSort.Int.testSortParallel | REPEATED | 7000 | 7.308 | 22.218 | 0.33 ArraysSort.Int.testSortParallel | REPEATED | 50000 | 63.627 | 48.959 | 1.30 ArraysSort.Int.testSortParallel | REPEATED | 300000 | 190.258 | 191.384 | 0.99 ArraysSort.Int.testSortParallel | REPEATED | 2000000 | 1415.189 | 1258.653 | 1.12 ArraysSort.Int.testSortParallel | STAGGER | 800 | 2.127 | 5.819 | 0.37 ArraysSort.Int.testSortParallel | STAGGER | 7000 | 18.726 | 25.198 | 0.74 ArraysSort.Int.testSortParallel | STAGGER | 50000 | 70.084 | 71.956 | 0.97 ArraysSort.Int.testSortParallel | STAGGER | 300000 | 255.61 | 307.352 | 0.83 ArraysSort.Int.testSortParallel | STAGGER | 2000000 | 1591.563 | 1853.58 | 0.86 ArraysSort.Int.testSortParallel | SHUFFLE | 800 | 2.842 | 5.562 | 0.51 ArraysSort.Int.testSortParallel | SHUFFLE | 7000 | 24.412 | 33.364 | 0.73 ArraysSort.Int.testSortParallel | SHUFFLE | 50000 | 113.109 | 85.321 | 1.33 ArraysSort.Int.testSortParallel | SHUFFLE | 300000 | 359.728 | 397.225 | 0.91 ArraysSort.Int.testSortParallel | SHUFFLE | 2000000 | 2443.197 | 4177.416 | 0.58 </body> </html> ------------- PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1815392394