changeset 37912:80b046f15b53

8154049: DualPivot sorting calculates incorrect runs for nearly sorted arrays Reviewed-by: shade
author psandoz
date Mon, 16 May 2016 07:01:26 +0200
parents 638fc62907ad
children 3cc95b690353
files jdk/src/java.base/share/classes/java/util/DualPivotQuicksort.java jdk/test/java/util/Arrays/SortingNearlySortedPrimitive.java
diffstat 2 files changed, 253 insertions(+), 89 deletions(-) [+]
line wrap: on
line diff
--- 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;
 
-    @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},
-        };
+    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);
     }
 
-    @Test(dataProvider = "arrays")
-    public void runTests(String testName, Supplier<int[]> dataMethod) throws Exception {
-        int[] intSourceArray = dataMethod.get();
+    // 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
+    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;