On Fri, 15 Sep 2023 20:17:17 GMT, Paul Sandoz <psan...@openjdk.org> wrote:
> > > Alan, you mentioned that DualPivotQuicksort will need detailed review. > > > Can we go ahead and start reviewing? Laurent checked performance, JMH > > > results look fine. > > > > As before, I think the main question with this change is whether adding > > radix sort to the mix is worth the complexity and additional code to > > maintain. Also as we discussed in the previous PR, the additional memory > > needed for the radix sort may have an effect on other things that are going > > on concurrently. I know it has been updated to handle OOME but I think > > potential reviewers would need to be comfortable with that part. > > I too share concerns about the potential increased use of memory for sorting > ints/longs/floats/doubles. With modern SIMD hardware and data parallel > techniques we can apply quicksort much more efficiently. I think it is > important to determine to what extent this reduces the need for radix sort. > To determine that we would need to carefully measure against the AVX-512 > implementation (with ongoing improvements) with appropriately initialized > data to sort, and further measure against an AVX2 version. Hi @PaulSandoz Paul, @AlanBateman Alan, I agree that additional memory must not change current behavior of the core. When parallel sort was introduced in JDK 8, parallel implementation with additional memory in merge sort went to the new method Arrays.parallelSort instead of Arrays.sort to be sure that existing applications will not broken. We take care of memory usages in sequential sorting, therefore I suggest the following variant: what if we introduce Radix sort for parallel sorting only? There are no memory changes in sequential sorting and in parallel sorting Radix sort will reuse buffer from parallel merge sort. It means there is no potential increased use of memory at all, no risk, we will keep current behavior. It is easy to adapt new implementation: one changed line for each type int/long/float/double. Paul, Alan, Do you agree with such idea? ------------- PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1722319763
