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

[iaroslavski]

On Wed, 20 Sep 2023 16:33:56 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 Paul (@PaulSandoz), Alan (@AlanBateman), Any update? Do you agree with Radix sort in parallel case only?
> 
> I think its definitely a better fit, but another aspect of my previous comment was wondering if we need a radix sort if the vectorized quicksort implementation is fast enough. IMO we need to compare performance results with the vectorized quick sort, and be aware of future enhancements to that.

Hi Paul (@PaulSandoz), Alan (@AlanBateman),
Any update? What do you think?

-------------

PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1777492279