RFR: 8333133: Simplify QuickSort::sort

[Kim Barrett]

On Thu, 30 May 2024 11:41:31 GMT, Aleksey Shipilev <shade at openjdk.org> wrote:

>> The "idempotent" argument is removed from that function, with associated
>> simplifications to the implementation. Callers are updated to remove that
>> argument. Callers that were providing a false value are unaffected in their
>> behavior.  The 3 callers that were providing a true value to request the
>> associated feature are also unaffected (other than by being made faster),
>> because the arrays involved don't contain any equivalent pairs.
>> 
>> There are also some miscellaneous cleanups, including using the swap utility
>> and fixing some comments.
>> 
>> Testing: mach5 tier1-3
>
> src/hotspot/share/utilities/quickSort.hpp line 75:
> 
>> 73:     for ( ; true; ++left_index, --right_index) {
>> 74:       for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {
>> 75:         assert(left_index < (length - 1), "reached end of partition");
> 
> Let me see if I understand this change. It makes assert stronger: we do not accept `left_index == length - 1` anymore. I guess that would mean the pivot is at the last element? Which makes the partition is empty, which cannot happen?

The reason I looked at the assert carefully in the first place was that `left_index < length` could
pass and yet we could still do `array[length]`, which could be UB.  So the tightened condition must
be correct, else we have a bug.  Proving we don't have a bug is a little bit harder.

We know that the last element in the sequence can't be less than the pivot,
because of the way find_pivot works.  It arranges for the first, middle, and
last values in the sequence to be ordered A[0] <= A[pivot] <= A[length-1].

The tricky case is the sequence [Vi..., P, P], where P is the pivot and all
Vi < P. The from-left scan proceeds until it reaches the left occurrence of P.
The from-right scan immediately stops on the right occurrence of P. The two
P's are swapped. left_index is incremented and right_index is decremented.
The from-left scan is restarted with left_index == length - 1, stops
immediately because P < P is false, and does not execute the assert. Similarly,
the from-right scan is restarted with right_index == length - 2, and also stops
because P > P is false.  And now the outer loop terminates.

A similar argument applies for the from-right scan, where we already assert
right_index > 0.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19464#discussion_r1621217067