RFR: 8333133: Simplify QuickSort::sort

[Kim Barrett]

On Wed, 29 May 2024 18:52:03 GMT, Kim Barrett <kbarrett 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

Thanks for the review.

> So .... IIUC

Not exactly.

> the only code that would be affected by this change would be code that
> passes true,

Correct.

> which could also have equivalent elements to sort,

Correct.

> and which requires the sort order to always be the same regardless of the
> order the elements are found.

It does not provide any such thing. All the flag does is prevent swapping of
equivalent elements, which doesn't give us any interesting additional ordering
property.

We can only detect the effect of the flag if there are elements that are
equivalent according to the sort function but are distinguishable by some
other means. Depending on what you mean, either

(1) All permutations of the sequence will sort to the same order.  This isn't
implementable.

(2) The sort doesn't change the relative order of equivalent elements, e.g.
the sort is stable.  Simple quicksort is not stable.  It's possible to make it
stable via O(N) extra memory, or (I've read) using a complex variant that is
significantly slower.  We're not doing either of those.

> I think only the archive related code cares about deterministic order, and
> package and module names should be unique, so this seems fine.

Correct.

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

PR Comment: https://git.openjdk.org/jdk/pull/19464#issuecomment-2169182340