RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v9]

[iaroslavski]

On Fri, 15 Sep 2023 20:17:17 GMT, Paul Sandoz <psandoz at 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