Сергей Цыпанов <sergei.tsypanov@yandex.ru> reports on core-libs-dev:

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;
+ }
     }

     /**