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) > Vamsi, Could you please run benchmarking with derived classes from jdk and my > version? > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a01.java > > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a02.java > > https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r01.java > II hope i allows us to detect the root of such behaviour. > > I see you used not the latest ArraysSort, I pointed to > https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSort.java > > It is not critical, but it will be better to be in the same environment, see > increased warmup, specified parameters for run and updated data sets > @WarmUp(iterations = 2, time = 3, timeUnit = TimeUnit.SECONDS) > @measurement(iterations = 4, time = 3, timeUnit = TimeUnit.SECONDS) > @fork(value=1, jvmArgsAppend={"-XX:CompileThreshold=1", > "-XX:-TieredCompilation"}) > Hello Vladimir (@iaroslavski), Please see the performance data below using the updated ArraysSort.java using the settings you suggested. Thank you for your understanding and patience! 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 (us/op) | Builder | (size) | Stock JDK (+ AVX512 sort) | DPQS_a01 (+ AVX512 sort) | Speedup -- | -- | -- | -- | -- | -- ArraysSort.Int.testSort | RANDOM | 600 | 2.256 | 2.069 | 1.09 ArraysSort.Int.testSort | RANDOM | 9000 | 41.457 | 42.359 | 0.98 ArraysSort.Int.testSort | RANDOM | 20000 | 98.448 | 99.709 | 0.99 ArraysSort.Int.testSort | RANDOM | 400000 | 2820.939 | 2867.054 | 0.98 ArraysSort.Int.testSort | RANDOM | 3000000 | 23426.411 | 23811.912 | 0.98 ArraysSort.Int.testSort | REPEATED | 600 | 1.032 | 1.309 | 0.79 ArraysSort.Int.testSort | REPEATED | 9000 | 5.114 | 5.026 | 1.02 ArraysSort.Int.testSort | REPEATED | 20000 | 10.3 | 12.02 | 0.86 ArraysSort.Int.testSort | REPEATED | 400000 | 210.742 | 234.39 | 0.90 ArraysSort.Int.testSort | REPEATED | 3000000 | 1948.589 | 1972.167 | 0.99 ArraysSort.Int.testSort | STAGGER | 600 | 2.125 | 2.077 | 1.02 ArraysSort.Int.testSort | STAGGER | 9000 | 29.86 | 28.353 | 1.05 ArraysSort.Int.testSort | STAGGER | 20000 | 67.096 | 80.237 | 0.84 ArraysSort.Int.testSort | STAGGER | 400000 | 1247.53 | 1241.979 | 1.00 ArraysSort.Int.testSort | STAGGER | 3000000 | 9435.404 | 9720.086 | 0.97 ArraysSort.Int.testSort | SHUFFLE | 600 | 2.701 | 2.653 | 1.02 ArraysSort.Int.testSort | SHUFFLE | 9000 | 38.976 | 40.214 | 0.97 ArraysSort.Int.testSort | SHUFFLE | 20000 | 96.399 | 94.587 | 1.02 ArraysSort.Int.testSort | SHUFFLE | 400000 | 2566.338 | 2571.189 | 1.00 ArraysSort.Int.testSort | SHUFFLE | 3000000 | 20835.935 | 21026.27 | 0.99 </body> </html> <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) | DPQS_a02 (+ AVX512 sort) | Speedup -- | -- | -- | -- | -- | -- ArraysSort.Int.testSort | RANDOM | 600 | 2.256 | 2.248 | 1.00 ArraysSort.Int.testSort | RANDOM | 9000 | 41.457 | 41.284 | 1.00 ArraysSort.Int.testSort | RANDOM | 20000 | 98.448 | 97.855 | 1.01 ArraysSort.Int.testSort | RANDOM | 400000 | 2820.939 | 2814.225 | 1.00 ArraysSort.Int.testSort | RANDOM | 3000000 | 23426.411 | 23227.972 | 1.01 ArraysSort.Int.testSort | REPEATED | 600 | 1.032 | 1.063 | 0.97 ArraysSort.Int.testSort | REPEATED | 9000 | 5.114 | 5.094 | 1.00 ArraysSort.Int.testSort | REPEATED | 20000 | 10.3 | 10.409 | 0.99 ArraysSort.Int.testSort | REPEATED | 400000 | 210.742 | 215.049 | 0.98 ArraysSort.Int.testSort | REPEATED | 3000000 | 1948.589 | 1921.44 | 1.01 ArraysSort.Int.testSort | STAGGER | 600 | 2.125 | 1.857 | 1.14 ArraysSort.Int.testSort | STAGGER | 9000 | 29.86 | 29.712 | 1.00 ArraysSort.Int.testSort | STAGGER | 20000 | 67.096 | 66.779 | 1.00 ArraysSort.Int.testSort | STAGGER | 400000 | 1247.53 | 1227.183 | 1.02 ArraysSort.Int.testSort | STAGGER | 3000000 | 9435.404 | 9457.907 | 1.00 ArraysSort.Int.testSort | SHUFFLE | 600 | 2.701 | 2.676 | 1.01 ArraysSort.Int.testSort | SHUFFLE | 9000 | 38.976 | 39.283 | 0.99 ArraysSort.Int.testSort | SHUFFLE | 20000 | 96.399 | 94.128 | 1.02 ArraysSort.Int.testSort | SHUFFLE | 400000 | 2566.338 | 2551.235 | 1.01 ArraysSort.Int.testSort | SHUFFLE | 3000000 | 20835.935 | 20628.565 | 1.01 </body> </html> <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) | DPQS_r01 (+ AVX512 sort) | Speedup -- | -- | -- | -- | -- | -- ArraysSort.Int.testSort | RANDOM | 600 | 2.256 | 1.713 | 1.32 ArraysSort.Int.testSort | RANDOM | 9000 | 41.457 | 38.316 | 1.08 ArraysSort.Int.testSort | RANDOM | 20000 | 98.448 | 86.376 | 1.14 ArraysSort.Int.testSort | RANDOM | 400000 | 2820.939 | 2792.333 | 1.01 ArraysSort.Int.testSort | RANDOM | 3000000 | 23426.411 | 23711.885 | 0.99 ArraysSort.Int.testSort | REPEATED | 600 | 1.032 | 0.859 | 1.20 ArraysSort.Int.testSort | REPEATED | 9000 | 5.114 | 5.014 | 1.02 ArraysSort.Int.testSort | REPEATED | 20000 | 10.3 | 9.532 | 1.08 ArraysSort.Int.testSort | REPEATED | 400000 | 210.742 | 235.281 | 0.90 ArraysSort.Int.testSort | REPEATED | 3000000 | 1948.589 | 1955.258 | 1.00 ArraysSort.Int.testSort | STAGGER | 600 | 2.125 | 2.157 | 0.99 ArraysSort.Int.testSort | STAGGER | 9000 | 29.86 | 29.931 | 1.00 ArraysSort.Int.testSort | STAGGER | 20000 | 67.096 | 66.543 | 1.01 ArraysSort.Int.testSort | STAGGER | 400000 | 1247.53 | 1224.999 | 1.02 ArraysSort.Int.testSort | STAGGER | 3000000 | 9435.404 | 9495.189 | 0.99 ArraysSort.Int.testSort | SHUFFLE | 600 | 2.701 | 1.64 | 1.65 ArraysSort.Int.testSort | SHUFFLE | 9000 | 38.976 | 34.201 | 1.14 ArraysSort.Int.testSort | SHUFFLE | 20000 | 96.399 | 79.616 | 1.21 ArraysSort.Int.testSort | SHUFFLE | 400000 | 2566.338 | 2436.271 | 1.05 ArraysSort.Int.testSort | SHUFFLE | 3000000 | 20835.935 | 20071.12 | 1.04 </body> </html> ------------- PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1828868104 PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1828869075 PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1828869933 PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1828870641
