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 Parallel (https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_RadixForParallel.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 Parallel (+AVX512 sort) | Speedup -- | -- | -- | -- | -- | -- ArraysSort.Int.testSort | RANDOM | 800 | 3.345 | 2.377 | 1.41 ArraysSort.Int.testSort | RANDOM | 7000 | 31.617 | 28.326 | 1.12 ArraysSort.Int.testSort | RANDOM | 50000 | 304.558 | 280.234 | 1.09 ArraysSort.Int.testSort | RANDOM | 300000 | 2097.165 | 2036.771 | 1.03 ArraysSort.Int.testSort | RANDOM | 2000000 | 15357.603 | 15161.475 | 1.01 ArraysSort.Int.testSort | REPEATED | 800 | 0.921 | 0.999 | 0.92 ArraysSort.Int.testSort | REPEATED | 7000 | 3.386 | 3.913 | 0.87 ArraysSort.Int.testSort | REPEATED | 50000 | 22.774 | 22.676 | 1.00 ArraysSort.Int.testSort | REPEATED | 300000 | 161.34 | 172.978 | 0.93 ArraysSort.Int.testSort | REPEATED | 2000000 | 1138.572 | 997.713 | 1.14 ArraysSort.Int.testSort | STAGGER | 800 | 2.13 | 2.376 | 0.90 ArraysSort.Int.testSort | STAGGER | 7000 | 17.967 | 19.628 | 0.92 ArraysSort.Int.testSort | STAGGER | 50000 | 121.2 | 145.005 | 0.84 ArraysSort.Int.testSort | STAGGER | 300000 | 728.444 | 858.048 | 0.85 ArraysSort.Int.testSort | STAGGER | 2000000 | 4943.958 | 5981.555 | 0.83 ArraysSort.Int.testSort | SHUFFLE | 800 | 2.834 | 2.418 | 1.17 ArraysSort.Int.testSort | SHUFFLE | 7000 | 30.086 | 27.715 | 1.09 ArraysSort.Int.testSort | SHUFFLE | 50000 | 268.786 | 255.285 | 1.05 ArraysSort.Int.testSort | SHUFFLE | 300000 | 1996.706 | 1792.05 | 1.11 ArraysSort.Int.testSort | SHUFFLE | 2000000 | 14108.444 | 13587.261 | 1.04 ArraysSort.Int.testSortParallel | RANDOM | 800 | 3.318 | 8.131 | 0.41 ArraysSort.Int.testSortParallel | RANDOM | 7000 | 26.533 | 43.69 | 0.61 ArraysSort.Int.testSortParallel | RANDOM | 50000 | 213.697 | 200.058 | 1.07 ArraysSort.Int.testSortParallel | RANDOM | 300000 | 682.952 | 829.459 | 0.82 ArraysSort.Int.testSortParallel | RANDOM | 2000000 | 3872.564 | 5139.343 | 0.75 ArraysSort.Int.testSortParallel | REPEATED | 800 | 0.907 | 5.993 | 0.15 ArraysSort.Int.testSortParallel | REPEATED | 7000 | 7.308 | 22.028 | 0.33 ArraysSort.Int.testSortParallel | REPEATED | 50000 | 63.627 | 48.46 | 1.31 ArraysSort.Int.testSortParallel | REPEATED | 300000 | 190.258 | 185.385 | 1.03 ArraysSort.Int.testSortParallel | REPEATED | 2000000 | 1415.189 | 1255.589 | 1.13 ArraysSort.Int.testSortParallel | STAGGER | 800 | 2.127 | 5.325 | 0.40 ArraysSort.Int.testSortParallel | STAGGER | 7000 | 18.726 | 25.331 | 0.74 ArraysSort.Int.testSortParallel | STAGGER | 50000 | 70.084 | 72.09 | 0.97 ArraysSort.Int.testSortParallel | STAGGER | 300000 | 255.61 | 306.342 | 0.83 ArraysSort.Int.testSortParallel | STAGGER | 2000000 | 1591.563 | 1841.733 | 0.86 ArraysSort.Int.testSortParallel | SHUFFLE | 800 | 2.842 | 5.348 | 0.53 ArraysSort.Int.testSortParallel | SHUFFLE | 7000 | 24.412 | 31.345 | 0.78 ArraysSort.Int.testSortParallel | SHUFFLE | 50000 | 113.109 | 85.67 | 1.32 ArraysSort.Int.testSortParallel | SHUFFLE | 300000 | 359.728 | 397.965 | 0.90 ArraysSort.Int.testSortParallel | SHUFFLE | 2000000 | 2443.197 | 4140.38 | 0.59 </body> </html> ------------- PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1815389792
