8154049: DualPivot sorting calculates incorrect runs for nearly sorted arrays
Reviewed-by: shade
--- a/jdk/src/java.base/share/classes/java/util/DualPivotQuicksort.java Mon May 16 01:05:57 2016 +0000
+++ b/jdk/src/java.base/share/classes/java/util/DualPivotQuicksort.java Mon May 16 07:01:26 2016 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2016, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -146,12 +146,26 @@
}
}
- // Check special cases
- // Implementation note: variable "right" is increased by 1.
- if (run[count] == right++) { // The last run contains one element
+ // These invariants should hold true:
+ // run[0] = 0
+ // run[<last>] = right + 1; (terminator)
+
+ if (count == 0) {
+ // A single equal run
+ return;
+ } else if (count == 1 && run[count] > right) {
+ // Either a single ascending or a transformed descending run.
+ // Always check that a final run is a proper terminator, otherwise
+ // we have an unterminated trailing run, to handle downstream.
+ return;
+ }
+ right++;
+ if (run[count] < right) {
+ // Corner case: the final run is not a terminator. This may happen
+ // if a final run is an equals run, or there is a single-element run
+ // at the end. Fix up by adding a proper terminator at the end.
+ // Note that we terminate with (right + 1), incremented earlier.
run[++count] = right;
- } else if (count <= 1) { // The array is already sorted
- return;
}
// Determine alternation base for merge
@@ -598,12 +612,26 @@
}
}
- // Check special cases
- // Implementation note: variable "right" is increased by 1.
- if (run[count] == right++) { // The last run contains one element
+ // These invariants should hold true:
+ // run[0] = 0
+ // run[<last>] = right + 1; (terminator)
+
+ if (count == 0) {
+ // A single equal run
+ return;
+ } else if (count == 1 && run[count] > right) {
+ // Either a single ascending or a transformed descending run.
+ // Always check that a final run is a proper terminator, otherwise
+ // we have an unterminated trailing run, to handle downstream.
+ return;
+ }
+ right++;
+ if (run[count] < right) {
+ // Corner case: the final run is not a terminator. This may happen
+ // if a final run is an equals run, or there is a single-element run
+ // at the end. Fix up by adding a proper terminator at the end.
+ // Note that we terminate with (right + 1), incremented earlier.
run[++count] = right;
- } else if (count <= 1) { // The array is already sorted
- return;
}
// Determine alternation base for merge
@@ -1086,12 +1114,26 @@
}
}
- // Check special cases
- // Implementation note: variable "right" is increased by 1.
- if (run[count] == right++) { // The last run contains one element
+ // These invariants should hold true:
+ // run[0] = 0
+ // run[<last>] = right + 1; (terminator)
+
+ if (count == 0) {
+ // A single equal run
+ return;
+ } else if (count == 1 && run[count] > right) {
+ // Either a single ascending or a transformed descending run.
+ // Always check that a final run is a proper terminator, otherwise
+ // we have an unterminated trailing run, to handle downstream.
+ return;
+ }
+ right++;
+ if (run[count] < right) {
+ // Corner case: the final run is not a terminator. This may happen
+ // if a final run is an equals run, or there is a single-element run
+ // at the end. Fix up by adding a proper terminator at the end.
+ // Note that we terminate with (right + 1), incremented earlier.
run[++count] = right;
- } else if (count <= 1) { // The array is already sorted
- return;
}
// Determine alternation base for merge
@@ -1574,12 +1616,26 @@
}
}
- // Check special cases
- // Implementation note: variable "right" is increased by 1.
- if (run[count] == right++) { // The last run contains one element
+ // These invariants should hold true:
+ // run[0] = 0
+ // run[<last>] = right + 1; (terminator)
+
+ if (count == 0) {
+ // A single equal run
+ return;
+ } else if (count == 1 && run[count] > right) {
+ // Either a single ascending or a transformed descending run.
+ // Always check that a final run is a proper terminator, otherwise
+ // we have an unterminated trailing run, to handle downstream.
+ return;
+ }
+ right++;
+ if (run[count] < right) {
+ // Corner case: the final run is not a terminator. This may happen
+ // if a final run is an equals run, or there is a single-element run
+ // at the end. Fix up by adding a proper terminator at the end.
+ // Note that we terminate with (right + 1), incremented earlier.
run[++count] = right;
- } else if (count <= 1) { // The array is already sorted
- return;
}
// Determine alternation base for merge
@@ -2158,12 +2214,26 @@
}
}
- // Check special cases
- // Implementation note: variable "right" is increased by 1.
- if (run[count] == right++) { // The last run contains one element
+ // These invariants should hold true:
+ // run[0] = 0
+ // run[<last>] = right + 1; (terminator)
+
+ if (count == 0) {
+ // A single equal run
+ return;
+ } else if (count == 1 && run[count] > right) {
+ // Either a single ascending or a transformed descending run.
+ // Always check that a final run is a proper terminator, otherwise
+ // we have an unterminated trailing run, to handle downstream.
+ return;
+ }
+ right++;
+ if (run[count] < right) {
+ // Corner case: the final run is not a terminator. This may happen
+ // if a final run is an equals run, or there is a single-element run
+ // at the end. Fix up by adding a proper terminator at the end.
+ // Note that we terminate with (right + 1), incremented earlier.
run[++count] = right;
- } else if (count <= 1) { // The array is already sorted
- return;
}
// Determine alternation base for merge
@@ -2701,12 +2771,26 @@
}
}
- // Check special cases
- // Implementation note: variable "right" is increased by 1.
- if (run[count] == right++) { // The last run contains one element
+ // These invariants should hold true:
+ // run[0] = 0
+ // run[<last>] = right + 1; (terminator)
+
+ if (count == 0) {
+ // A single equal run
+ return;
+ } else if (count == 1 && run[count] > right) {
+ // Either a single ascending or a transformed descending run.
+ // Always check that a final run is a proper terminator, otherwise
+ // we have an unterminated trailing run, to handle downstream.
+ return;
+ }
+ right++;
+ if (run[count] < right) {
+ // Corner case: the final run is not a terminator. This may happen
+ // if a final run is an equals run, or there is a single-element run
+ // at the end. Fix up by adding a proper terminator at the end.
+ // Note that we terminate with (right + 1), incremented earlier.
run[++count] = right;
- } else if (count <= 1) { // The array is already sorted
- return;
}
// Determine alternation base for merge
--- a/jdk/test/java/util/Arrays/SortingNearlySortedPrimitive.java Mon May 16 01:05:57 2016 +0000
+++ b/jdk/test/java/util/Arrays/SortingNearlySortedPrimitive.java Mon May 16 07:01:26 2016 +0200
@@ -1,6 +1,6 @@
/*
* Copyright 2015 Goldman Sachs.
- * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -23,6 +23,7 @@
*/
/*
* @test
+ * @bug 8154049
* @summary Tests the sorting of a large array of sorted primitive values,
* predominently for cases where the array is nearly sorted. This tests
* code that detects patterns in the array to determine if it is nearly
@@ -32,32 +33,117 @@
* @run testng SortingNearlySortedPrimitive
*/
-import org.testng.Assert;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
+import java.util.ArrayList;
import java.util.Arrays;
-import java.util.function.Supplier;
+import java.util.List;
+import java.util.StringJoiner;
+import java.util.function.IntFunction;
+import java.util.stream.IntStream;
+import java.util.stream.Stream;
public class SortingNearlySortedPrimitive {
- private static final int ARRAY_SIZE = 1_000_000;
+
+ static final int BASE = 3;
+ static final int WIDTH = 4;
+ // Should be > DualPivotQuicksort.QUICKSORT_THRESHOLD
+ static final int PAD = 300;
+
+ Stream<int[]> createCombinations() {
+ // Create all combinations for the BASE value and double the WIDTH
+ // elements
+ // This is create various combinations of ascending, descending and
+ // equal runs to exercise the nearly sorted code paths
+ return IntStream.range(0, (int) Math.pow(BASE, 2 * WIDTH)).
+ mapToObj(this::createArray);
+ }
- @DataProvider(name = "arrays")
- public Object[][] createData() {
- return new Object[][]{
- {"hiZeroLowTest", (Supplier<int[]>) this::hiZeroLowData},
- {"endLessThanTest", (Supplier<int[]>) this::endLessThanData},
- {"highFlatLowTest", (Supplier<int[]>) this::highFlatLowData},
- {"identicalTest", (Supplier<int[]>) this::identicalData},
- {"sortedReversedSortedTest", (Supplier<int[]>) this::sortedReversedSortedData},
- {"pairFlipTest", (Supplier<int[]>) this::pairFlipData},
- {"zeroHiTest", (Supplier<int[]>) this::zeroHiData},
- };
+ // Create an array which at either end is filled with -ve and +ve elements
+ // according to the base value and padded with zeros in between
+ int[] createArray(int v) {
+ int[] a = new int[WIDTH + PAD + WIDTH];
+
+ // Fill head of array
+ for (int j = 0; j < WIDTH; j++) {
+ a[j] = (v % BASE) - (BASE / 2);
+ v /= BASE;
+ }
+ // Fill tail of array
+ for (int j = 0; j < WIDTH; j++) {
+ a[WIDTH + PAD + j] = (v % BASE) - (BASE / 2);
+ v /= BASE;
+ }
+ return a;
}
- @Test(dataProvider = "arrays")
- public void runTests(String testName, Supplier<int[]> dataMethod) throws Exception {
- int[] intSourceArray = dataMethod.get();
+ @Test
+ public void testCombination() {
+ createCombinations().forEach(a -> {
+ try {
+ // Clone source array to ensure it is not modified
+ this.sortAndAssert(a.clone());
+ this.sortAndAssert(floatCopyFromInt(a));
+ this.sortAndAssert(doubleCopyFromInt(a));
+ this.sortAndAssert(longCopyFromInt(a));
+ this.sortAndAssert(shortCopyFromInt(a));
+ this.sortAndAssert(charCopyFromInt(a));
+ } catch (AssertionError sae) {
+ AssertionError ae = new AssertionError("Sort failed for " + arrayToString(a));
+ ae.addSuppressed(sae);
+ throw ae;
+ }
+ });
+ }
+
+ String arrayToString(int[] a) {
+ int[] l = Arrays.copyOfRange(a, 0, WIDTH + 2);
+ int[] r = Arrays.copyOfRange(a, a.length - (WIDTH + 2), a.length);
+ StringJoiner sj = new StringJoiner(",", "[", "]");
+ for (int i : l) {
+ sj.add(Integer.toString(i));
+ }
+ sj.add("...");
+ for (int i : r) {
+ sj.add(Integer.toString(i));
+ }
+ return sj.toString();
+ }
+
+
+ @DataProvider(name = "shapes")
+ public Object[][] createShapes() {
+ Stream<List<Object>> baseCases = Stream.of(
+ List.of("hiZeroLowTest", (IntFunction<int[]>) this::hiZeroLowData),
+ List.of("endLessThanTest", (IntFunction<int[]>) this::endLessThanData),
+ List.of("highFlatLowTest", (IntFunction<int[]>) this::highFlatLowData),
+ List.of("identicalTest", (IntFunction<int[]>) this::identicalData),
+ List.of("sortedReversedSortedTest", (IntFunction<int[]>) this::sortedReversedSortedData),
+ List.of("pairFlipTest", (IntFunction<int[]>) this::pairFlipData),
+ List.of("zeroHiTest", (IntFunction<int[]>) this::zeroHiData)
+ );
+
+ // Ensure the following inequality holds for certain sizes
+ // DualPivotQuicksort.QUICKSORT_THRESHOLD <= size - 1
+ // < DualPivotQuicksort.COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR
+ // This guarantees that code paths are taken for checking nearly sorted
+ // arrays for all primitive types
+ List<Integer> sizes = List.of(100, 1_000, 10_000, 1_000_000);
+ return baseCases.
+ flatMap(l -> sizes.stream().map(s -> append(l, s))).
+ toArray(Object[][]::new);
+ }
+
+ Object[] append(List<Object> l, Object value) {
+ List<Object> nl = new ArrayList<>(l);
+ nl.add(value);
+ return nl.toArray();
+ }
+
+ @Test(dataProvider = "shapes")
+ public void testShapes(String testName, IntFunction<int[]> dataMethod, int size) {
+ int[] intSourceArray = dataMethod.apply(size);
// Clone source array to ensure it is not modified
this.sortAndAssert(intSourceArray.clone());
@@ -110,73 +196,67 @@
private void sortAndAssert(int[] array) {
Arrays.sort(array);
- for (int i = 1; i < ARRAY_SIZE; i++) {
+ for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
throw new AssertionError("not sorted");
}
}
- Assert.assertEquals(ARRAY_SIZE, array.length);
}
private void sortAndAssert(char[] array) {
Arrays.sort(array);
- for (int i = 1; i < ARRAY_SIZE; i++) {
+ for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
throw new AssertionError("not sorted");
}
}
- Assert.assertEquals(ARRAY_SIZE, array.length);
}
private void sortAndAssert(short[] array) {
Arrays.sort(array);
- for (int i = 1; i < ARRAY_SIZE; i++) {
+ for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
throw new AssertionError("not sorted");
}
}
- Assert.assertEquals(ARRAY_SIZE, array.length);
}
private void sortAndAssert(double[] array) {
Arrays.sort(array);
- for (int i = 1; i < ARRAY_SIZE; i++) {
+ for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
throw new AssertionError("not sorted");
}
}
- Assert.assertEquals(ARRAY_SIZE, array.length);
}
private void sortAndAssert(float[] array) {
Arrays.sort(array);
- for (int i = 1; i < ARRAY_SIZE; i++) {
+ for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
throw new AssertionError("not sorted");
}
}
- Assert.assertEquals(ARRAY_SIZE, array.length);
}
private void sortAndAssert(long[] array) {
Arrays.sort(array);
- for (int i = 1; i < ARRAY_SIZE; i++) {
+ for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
throw new AssertionError("not sorted");
}
}
- Assert.assertEquals(ARRAY_SIZE, array.length);
}
- private int[] zeroHiData() {
- int[] array = new int[ARRAY_SIZE];
+ private int[] zeroHiData(int size) {
+ int[] array = new int[size];
- int threeQuarters = (int) (ARRAY_SIZE * 0.75);
+ int threeQuarters = (int) (size * 0.75);
for (int i = 0; i < threeQuarters; i++) {
array[i] = 0;
}
int k = 1;
- for (int i = threeQuarters; i < ARRAY_SIZE; i++) {
+ for (int i = threeQuarters; i < size; i++) {
array[i] = k;
k++;
}
@@ -184,10 +264,10 @@
return array;
}
- private int[] hiZeroLowData() {
- int[] array = new int[ARRAY_SIZE];
+ private int[] hiZeroLowData(int size) {
+ int[] array = new int[size];
- int oneThird = ARRAY_SIZE / 3;
+ int oneThird = size / 3;
for (int i = 0; i < oneThird; i++) {
array[i] = i;
}
@@ -195,16 +275,16 @@
for (int i = oneThird; i < twoThirds; i++) {
array[i] = 0;
}
- for (int i = twoThirds; i < ARRAY_SIZE; i++) {
+ for (int i = twoThirds; i < size; i++) {
array[i] = oneThird - i + twoThirds;
}
return array;
}
- private int[] highFlatLowData() {
- int[] array = new int[ARRAY_SIZE];
+ private int[] highFlatLowData(int size) {
+ int[] array = new int[size];
- int oneThird = ARRAY_SIZE / 3;
+ int oneThird = size / 3;
for (int i = 0; i < oneThird; i++) {
array[i] = i;
}
@@ -213,57 +293,57 @@
for (int i = oneThird; i < twoThirds; i++) {
array[i] = constant;
}
- for (int i = twoThirds; i < ARRAY_SIZE; i++) {
+ for (int i = twoThirds; i < size; i++) {
array[i] = constant - i + twoThirds;
}
return array;
}
- private int[] identicalData() {
- int[] array = new int[ARRAY_SIZE];
+ private int[] identicalData(int size) {
+ int[] array = new int[size];
int listNumber = 24;
- for (int i = 0; i < ARRAY_SIZE; i++) {
+ for (int i = 0; i < size; i++) {
array[i] = listNumber;
}
return array;
}
- private int[] endLessThanData() {
- int[] array = new int[ARRAY_SIZE];
+ private int[] endLessThanData(int size) {
+ int[] array = new int[size];
- for (int i = 0; i < ARRAY_SIZE - 1; i++) {
+ for (int i = 0; i < size - 1; i++) {
array[i] = 3;
}
- array[ARRAY_SIZE - 1] = 1;
+ array[size - 1] = 1;
return array;
}
- private int[] sortedReversedSortedData() {
- int[] array = new int[ARRAY_SIZE];
+ private int[] sortedReversedSortedData(int size) {
+ int[] array = new int[size];
- for (int i = 0; i < ARRAY_SIZE / 2; i++) {
+ for (int i = 0; i < size / 2; i++) {
array[i] = i;
}
int num = 0;
- for (int i = ARRAY_SIZE / 2; i < ARRAY_SIZE; i++) {
- array[i] = ARRAY_SIZE - num;
+ for (int i = size / 2; i < size; i++) {
+ array[i] = size - num;
num++;
}
return array;
}
- private int[] pairFlipData() {
- int[] array = new int[ARRAY_SIZE];
+ private int[] pairFlipData(int size) {
+ int[] array = new int[size];
- for (int i = 0; i < ARRAY_SIZE; i++) {
+ for (int i = 0; i < size; i++) {
array[i] = i;
}
- for (int i = 0; i < ARRAY_SIZE; i += 2) {
+ for (int i = 0; i < size; i += 2) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;