RFR 8154049: DualPivot sorting calculates incorrect runs for nearly sorted arrays

[Paul Sandoz]

Hi,

Please review:

  http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8154049-dual-pivot-sort-one-off-error/webrev/
  https://bugs.openjdk.java.net/browse/JDK-8154049


A bug was introduced with the fix for:

  https://bugs.openjdk.java.net/browse/JDK-8080945
  Improve the performance of primitive Arrays.sort for certain patterns of array elements

Certain patterns of nearly sorted data failed to sort, and surprisingly (and embarrassingly) this was not detected by existing sorting tests. It was detected by pack200 tests, but the intermittent nature of the failure at a distance meant it took a while to track this down.


If the number of elements to sort is > QUICKSORT_THRESHOLD (286), then a loop over the elements is performed to count equals, ascending and descending (transformed into ascending) runs. If the number of runs is < MAX_RUN_COUNT (67) then a merge sort of the runs is performed. When the loop finishes it is necessary to clean up some edge cases to report a final run.

Modifications for JDK-8080945 failed to take into account an additional case for reporting a final run (specifically a run of equals elements, in addition to the previous case of a single last element).

The fix is correctly report a final run in all cases. I tried to make the code more explicit. (It might be possible to clean up the code more, but i want to get a conservative fix in).

I have also modified the nearly sorted test case:

- all primitive types are correctly tested based on size thresholds, specifically short/char have a lower bound, COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR (3200) above which a counting sort is performed.

- added a combinatorial test, where 4 (base 3) digits, each taking values of -1, 0 or 1, bound at either side a sequence of zeros of sufficient length to ensure the array size is above the quick sort threshold. This should exercise all run counting code paths

In addition we have run the pack200 “test from hell” (thanks Kumar!) and this now passes without failure.

Paul.