On Wed, 30 Aug 2023 10:55:48 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: > > updated comments (v23.08) Hi team, @AlanBateman, @rose00, @mbreinhold There are a big efforts now to improve sorting with x86_64 AVX512 https://github.com/openjdk/jdk/pull/14227, no changes of Dual-Pivot Quicksort logic. But at the same time this PR offers algorithmic improvements, like optimized insertion sort, merging sort, better partitioning and Radix sort for fully random data. Radix sort has linear complexity instead of n*ln(n), much faster!. Also we handle properly situation if no enough memory for additional buffer, now we will face with OOM. Alan, you mentioned that DualPivotQuicksort will need detailed review. Can we go ahead and start reviewing? Laurent checked performance, JMH results look fine. I think it would be logical to integrate new DualPivotQuicksort first, and then apply AVX512 changes. ------------- PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1701162875
