Verify java.util.Arrays against OpenJDK 8u121-b13.

This change just clarifies some change markers.

The change from instanceof to getComponentType() in deepHashCode is
kept because it provides a measurable performance increase, see the
benchmarks in the comment for http://r.android.com/666141.

The change to return early from deepEquals when e2 == null is also
kept. Running the same benchmark with a change to include some null
elements gives the results shown below. That benchmark change is also
included here.

With the current code:

    Trial Report (1 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0001}}
      Results:
        runtime(ns): min=31367.26, 1st qu.=31367.26, median=31367.26, mean=31367.26, 3rd qu.=31367.26, max=31367.26
    Trial Report (2 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0004}}
      Results:
        runtime(ns): min=30724.31, 1st qu.=30724.31, median=30724.31, mean=30724.31, 3rd qu.=30724.31, max=30724.31
    Trial Report (3 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0016}}
      Results:
        runtime(ns): min=30966.47, 1st qu.=30966.47, median=30966.47, mean=30966.47, 3rd qu.=30966.47, max=30966.47
    Trial Report (4 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0256}}
      Results:
        runtime(ns): min=384872.18, 1st qu.=384872.18, median=384872.18, mean=384872.18, 3rd qu.=384872.18, max=384872.18
    Trial Report (5 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=2048}}
      Messages:
        INFO: This experiment does not require a microbenchmark. The granularity of the timer (1.243us) is less than 0.1% of the measured runtime. If all experiments for this benchmark have runtimes greater than 1.243ms, consider the macrobenchmark instrument.
      Results:
        runtime(ns): min=7466868.31, 1st qu.=7466868.31, median=7466868.31, mean=7466868.31, 3rd qu.=7466868.31, max=7466868.31
    Trial Report (6 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0001}}
      Results:
        runtime(ns): min=11564.19, 1st qu.=11564.19, median=11564.19, mean=11564.19, 3rd qu.=11564.19, max=11564.19
    Trial Report (7 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0004}}
      Results:
        runtime(ns): min=11996.46, 1st qu.=11996.46, median=11996.46, mean=11996.46, 3rd qu.=11996.46, max=11996.46
    Trial Report (8 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0016}}
      Results:
        runtime(ns): min=12501.23, 1st qu.=12501.23, median=12501.23, mean=12501.23, 3rd qu.=12501.23, max=12501.23
    Trial Report (9 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0256}}
      Results:
        runtime(ns): min=160199.22, 1st qu.=160199.22, median=160199.22, mean=160199.22, 3rd qu.=160199.22, max=160199.22
    Trial Report (10 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=2048}}
      Messages:
        INFO: This experiment does not require a microbenchmark. The granularity of the timer (1.243us) is less than 0.1% of the measured runtime. If all experiments for this benchmark have runtimes greater than 1.243ms, consider the macrobenchmark instrument.
      Results:
        runtime(ns): min=3677664.68, 1st qu.=3677664.68, median=3677664.68, mean=3677664.68, 3rd qu.=3677664.68, max=3677664.68

Without the e2 == null change:

    Trial Report (1 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0001}}
      Results:
        runtime(ns): min=29784.37, 1st qu.=29784.37, median=29784.37, mean=29784.37, 3rd qu.=29784.37, max=29784.37
    Trial Report (2 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0004}}
      Results:
        runtime(ns): min=29919.63, 1st qu.=29919.63, median=29919.63, mean=29919.63, 3rd qu.=29919.63, max=29919.63
    Trial Report (3 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0016}}
      Results:
        runtime(ns): min=30606.55, 1st qu.=30606.55, median=30606.55, mean=30606.55, 3rd qu.=30606.55, max=30606.55
    Trial Report (4 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=0256}}
      Results:
        runtime(ns): min=390343.22, 1st qu.=390343.22, median=390343.22, mean=390343.22, 3rd qu.=390343.22, max=390343.22
    Trial Report (5 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepEquals, vm=default, parameters={arrayLength=2048}}
      Messages:
        INFO: This experiment does not require a microbenchmark. The granularity of the timer (1.238us) is less than 0.1% of the measured runtime. If all experiments for this benchmark have runtimes greater than 1.238ms, consider the macrobenchmark instrument.
      Results:
        runtime(ns): min=7533281.31, 1st qu.=7533281.31, median=7533281.31, mean=7533281.31, 3rd qu.=7533281.31, max=7533281.31
    Trial Report (6 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0001}}
      Results:
        runtime(ns): min=12169.12, 1st qu.=12169.12, median=12169.12, mean=12169.12, 3rd qu.=12169.12, max=12169.12
    Trial Report (7 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0004}}
      Results:
        runtime(ns): min=12014.69, 1st qu.=12014.69, median=12014.69, mean=12014.69, 3rd qu.=12014.69, max=12014.69
    Trial Report (8 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0016}}
      Results:
        runtime(ns): min=13448.17, 1st qu.=13448.17, median=13448.17, mean=13448.17, 3rd qu.=13448.17, max=13448.17
    Trial Report (9 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=0256}}
      Results:
        runtime(ns): min=164844.00, 1st qu.=164844.00, median=164844.00, mean=164844.00, 3rd qu.=164844.00, max=164844.00
    Trial Report (10 of 10):
      Experiment {instrument=runtime, benchmarkMethod=deepHashCode, vm=default, parameters={arrayLength=2048}}
      Messages:
        INFO: This experiment does not require a microbenchmark. The granularity of the timer (1.238us) is less than 0.1% of the measured runtime. If all experiments for this benchmark have runtimes greater than 1.238ms, consider the macrobenchmark instrument.
      Results:
        runtime(ns): min=3866005.14, 1st qu.=3866005.14, median=3866005.14, mean=3866005.14, 3rd qu.=3866005.14, max=3866005.14

Bug: 35910877
Test: Treehugger
Change-Id: Ic611ce1982073113786e840dd6d80c79a48c384f

2 files changed, 24 insertions, 10 deletions

diff --git a/benchmarks/src/benchmarks/DeepArrayOpsBenchmark.java b/benchmarks/src/benchmarks/DeepArrayOpsBenchmark.java
index 624d8234bd..c671da6f41 100644
--- a/benchmarks/src/benchmarks/DeepArrayOpsBenchmark.java
+++ b/benchmarks/src/benchmarks/DeepArrayOpsBenchmark.java
@@ -30,9 +30,9 @@ public class DeepArrayOpsBenchmark {
     private Object[] array2;
 
     @BeforeExperiment public void setUp() throws Exception {
-        array = new Object[arrayLength * 13];
-        array2 = new Object[arrayLength * 13];
-        for (int i = 0; i < arrayLength; i += 13) {
+        array = new Object[arrayLength * 14];
+        array2 = new Object[arrayLength * 14];
+        for (int i = 0; i < arrayLength; i += 14) {
             array[i] = new IntWrapper(i);
             array2[i] = new IntWrapper(i);
 
@@ -73,6 +73,9 @@ public class DeepArrayOpsBenchmark {
             // Subarray types is an interface.
             array[i + 12] = new16ElementArray(CharSequence.class, String.class);
             array2[i + 12] = new16ElementArray(CharSequence.class, String.class);
+
+            array[i + 13] = null;
+            array2[i + 13] = null;
         }
     }
 
@@ -142,4 +145,3 @@ public class DeepArrayOpsBenchmark {
         }
     }
 }
-
diff --git a/ojluni/src/main/java/java/util/Arrays.java b/ojluni/src/main/java/java/util/Arrays.java
index b9072da352..258ca152bc 100644
--- a/ojluni/src/main/java/java/util/Arrays.java
+++ b/ojluni/src/main/java/java/util/Arrays.java
@@ -78,7 +78,7 @@ public class Arrays {
      * tasks that makes parallel speedups unlikely.
      * @hide
      */
-    // Android-changed: make public (used by harmony ArraysTest)
+    // Android-changed: Make MIN_ARRAY_SORT_GRAN public and @hide (used by harmony ArraysTest)
     public static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
 
     // Suppresses default constructor, ensuring non-instantiability.
@@ -1201,6 +1201,8 @@ public class Arrays {
      * Sorting of complex type arrays.
      */
 
+    // Android-removed: LegacyMergeSort class (unused on Android).
+
     /**
      * Sorts the specified array of objects into ascending order, according
      * to the {@linkplain Comparable natural ordering} of its elements.
@@ -1244,13 +1246,15 @@ public class Arrays {
      *         {@link Comparable} contract
      */
     public static void sort(Object[] a) {
-        // Android-changed: LegacyMergeSort is no longer supported
+        // Android-removed: LegacyMergeSort support
         // if (LegacyMergeSort.userRequested)
         //     legacyMergeSort(a);
         // else
             ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
     }
 
+    // Android-removed: legacyMergeSort() (unused on Android)
+
     /**
      * Sorts the specified range of the specified array of objects into
      * ascending order, according to the
@@ -1305,13 +1309,15 @@ public class Arrays {
      */
     public static void sort(Object[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        // Android-changed: LegacyMergeSort is no longer supported
+        // Android-removed: LegacyMergeSort support
         // if (LegacyMergeSort.userRequested)
         //     legacyMergeSort(a, fromIndex, toIndex);
         // else
             ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
     }
 
+    // Android-removed: legacyMergeSort() (unused on Android)
+
     /**
      * Tuning parameter: list size at or below which insertion sort will be
      * used in preference to mergesort.
@@ -1425,7 +1431,7 @@ public class Arrays {
         if (c == null) {
             sort(a);
         } else {
-            // Android-changed: LegacyMergeSort is no longer supported
+        // Android-removed: LegacyMergeSort support
             // if (LegacyMergeSort.userRequested)
             //     legacyMergeSort(a, c);
             // else
@@ -1433,6 +1439,8 @@ public class Arrays {
         }
     }
 
+    // Android-removed: legacyMergeSort() (unused on Android)
+
     /**
      * Sorts the specified range of the specified array of objects according
      * to the order induced by the specified comparator.  The range to be
@@ -1491,7 +1499,7 @@ public class Arrays {
             sort(a, fromIndex, toIndex);
         } else {
             rangeCheck(a.length, fromIndex, toIndex);
-            // Android-changed: LegacyMergeSort is no longer supported
+            // Android-removed: LegacyMergeSort support
             // if (LegacyMergeSort.userRequested)
             //     legacyMergeSort(a, fromIndex, toIndex, c);
             // else
@@ -1499,6 +1507,9 @@ public class Arrays {
         }
     }
 
+    // Android-removed: legacyMergeSort() (unused on Android)
+    // Android-removed: mergeSort() (unused on Android)
+
     // Parallel prefix
 
     /**
@@ -4113,7 +4124,7 @@ public class Arrays {
 
         for (Object element : a) {
             int elementHash = 0;
-            // BEGIN Android-changed: getComponentType() is faster than instanceof()
+            // BEGIN Android-changed: getComponentType() is faster than instanceof
             if (element != null) {
                 Class<?> cl = element.getClass().getComponentType();
                 if (cl == null)
@@ -4197,6 +4208,7 @@ public class Arrays {
             if (e1 == e2)
                 continue;
             // Android-changed: Return early if e2 == null
+            // if (e1 == null)
             if (e1 == null || e2 == null)
                 return false;