Extend ArrayList fastpath to Collections.sort(List<T>, Comparator<T>).

My original reasons for not extending it were bogus. We can safely
cast Object[] to T[] in this case.

Also tidy up the benchmark by changing buildList(.. boolean isArrayList)
to buildList(.. Class<T extends List<Integer> list.

AFTER

SortWithComparator_arrayList, arrayListLength=4} 10881.97 ns; σ=64.97 ns @ 3 trials
SortWithComparator_arrayList, arrayListLength=16} 33235.73 ns; σ=127.45 ns @ 3 trials
SortWithComparator_arrayList, arrayListLength=64} 130317.52 ns; σ=135.31 ns @ 3 trials
SortWithComparator_arrayList, arrayListLength=256} 495200.19 ns; σ=1120.86 ns @ 3 trials
SortWithComparator_arrayList, arrayListLength=1024} 1990796.02 ns; σ=19151.58 ns @ 6 trials

BEFORE

SortWithComparator_arrayList, arrayListLength=4} 40030.32 ns; σ=509.60 ns @ 10 trials
SortWithComparator_arrayList, arrayListLength=16} 122122.08 ns; σ=182.58 ns @ 3 trials
SortWithComparator_arrayList, arrayListLength=64} 457833.87 ns; σ=1311.54 ns @ 3 trials
SortWithComparator_arrayList, arrayListLength=256} 1764647.22 ns; σ=35150.74 ns @ 10 trials
SortWithComparator_arrayList, arrayListLength=1024} 7127679.90 ns; σ=122546.75 ns @ 10 trials

bug: 18821961
Change-Id: I22a18d99598dfacbdc54cf75e38dbc32ab027754

1 files changed, 32 insertions, 7 deletions

diff --git a/benchmarks/src/benchmarks/regression/CollectionsBenchmark.java b/benchmarks/src/benchmarks/regression/CollectionsBenchmark.java
index 43d6d59..18b969a 100644
--- a/benchmarks/src/benchmarks/regression/CollectionsBenchmark.java
+++ b/benchmarks/src/benchmarks/regression/CollectionsBenchmark.java
@@ -20,6 +20,7 @@ import com.google.caliper.Param;
 import com.google.caliper.SimpleBenchmark;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
 import java.util.Random;
 import java.util.Vector;
@@ -28,25 +29,49 @@ public class CollectionsBenchmark extends SimpleBenchmark {
     @Param({"4", "16", "64", "256", "1024"})
     private int arrayListLength;
 
-    public void timeSort_arrayList(int nreps) {
-        List<Integer> input = buildList(arrayListLength, true /* use array list */);
+    public static Comparator<Integer> REVERSE = new Comparator<Integer>() {
+        @Override
+        public int compare(Integer lhs, Integer rhs) {
+            int lhsAsInt = lhs.intValue();
+            int rhsAsInt = rhs.intValue();
+            return rhsAsInt < lhsAsInt ? -1 : (lhsAsInt == rhsAsInt ? 0 : 1);
+        }
+    };
+
+
+    public void timeSort_arrayList(int nreps) throws Exception {
+        List<Integer> input = buildList(arrayListLength, ArrayList.class);
         for (int i = 0; i < nreps; ++i) {
             Collections.sort(input);
         }
     }
 
-    public void timeSort_vector(int nreps) {
-        List<Integer> input = buildList(arrayListLength, false /* use array list */);
+    public void timeSortWithComparator_arrayList(int nreps) throws Exception {
+        List<Integer> input = buildList(arrayListLength, ArrayList.class);
+        for (int i = 0; i < nreps; ++i) {
+            Collections.sort(input, REVERSE);
+        }
+    }
+
+    public void timeSort_vector(int nreps) throws Exception {
+        List<Integer> input = buildList(arrayListLength, Vector.class);
         for (int i = 0; i < nreps; ++i) {
             Collections.sort(input);
         }
     }
 
-    private static List<Integer> buildList(int arrayListLength, boolean useArrayList) {
+    public void timeSortWithComparator_vector(int nreps) throws Exception {
+        List<Integer> input = buildList(arrayListLength, Vector.class);
+        for (int i = 0; i < nreps; ++i) {
+            Collections.sort(input, REVERSE);
+        }
+    }
+
+    private static <T extends List<Integer>> List<Integer> buildList(
+            int arrayListLength, Class<T> listClass) throws Exception {
         Random random = new Random();
         random.setSeed(0);
-        List<Integer> list = useArrayList ? new ArrayList<Integer>(arrayListLength) :
-                new Vector<Integer>(arrayListLength);
+        List<Integer> list = listClass.newInstance();
         for (int i = 0; i < arrayListLength; ++i) {
             list.add(random.nextInt());
         }