[PATCH] Inefficient ArrayList.subList().toArray()

[Сергей Цыпанов]

Hi,

I've run into poor performance of toArray() method called on result of subList() taken from java.util.ArrayList.

Consider simple benchmark:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"})
public class SubListToArrayBenchmark {

    @Benchmark
    public Integer[] list_typeChecked(Data holder) {
        return holder.list.toArray(new Integer[0]);
    }

    @Benchmark
    public Integer[] subList_typeChecked(Data holder) {
        return holder.list.subList(0, holder.size).toArray(new Integer[0]);
    }

    @State(Scope.Thread)
    public static class Data {
        ArrayList<Integer> list;

        @Param({"0", "10", "100", "1000"})
        int size;

        @Setup
        public void setup() {
            list = IntStream
                    .range(0, size)
                    .boxed()
                    .collect(toCollection(ArrayList::new));
        }
    }
}


With Java 1.8.0_162 on my PC (Intel i5-4690 3,5 GHz) it yields these results:

Benchmark                    (size)  Mode  Cnt     Score     Error  Units
list_typeChecked                 0  avgt   50        4,630 ±    0,062  ns/op
list_typeChecked               10  avgt   50      16,629 ±    0,140  ns/op
list_typeChecked             100  avgt   50      79,783 ±    1,676  ns/op
list_typeChecked           1000  avgt   50    742,757 ±  10,357  ns/op

subList_typeChecked          0  avgt   50      11,833 ±    0,801  ns/op
subList_typeChecked        10  avgt   50      42,713 ±    0,590  ns/op
subList_typeChecked      100  avgt   50    197,336 ±    3,560  ns/op
subList_typeChecked    1000  avgt   50  1765,187 ±  19,729  ns/op

With Java 9 subList performs slightly better but still much worse than list.


Despite the fact that amount of data transfered from list to array is the same for both methods there's a huge difference in absolute values.

Instantiation of SubList costs in average only 9.591 ± 0.650  ns and is independent on the size of its source so it couldn't be root cause.

Here SubLists taken from ArrayList calls AbstractCollection.toArray() method while implementing RandomAccess and being array-based by its nature.
Array-based ArrayList provides efficient implementation of toArray(T[]) and we can apply the same approach for ArrayList.SubList.

Here's the patch for JDK 9:

--------------------------------------------------------------------------------------------------------------------------------------------------------

diff --git a/src/java.base/share/classes/java/util/ArrayList.java b/src/java.base/share/classes/java/util/ArrayList.java
--- a/src/java.base/share/classes/java/util/ArrayList.java
+++ b/src/java.base/share/classes/java/util/ArrayList.java
@@ -1363,6 +1363,20 @@
                 }
             };
         }
+
+        public Object[] toArray() {
+            return Arrays.copyOfRange(root.elementData, offset, size);
+        }
+
+        @SuppressWarnings("unchecked")
+        public <T> T[] toArray(T[] a) {
+            if (a.length < size)
+                return (T[]) Arrays.copyOfRange(root.elementData, offset, size, a.getClass());
+            System.arraycopy(root.elementData, offset, a, 0, size);
+            if (a.length > size)
+                a[size] = null;
+            return a;
+        }
     }
 
     /**

--------------------------------------------------------------------------------------------------------------------------------------------------------

Best regards,
Sergey Tsypanov