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

Krystal Mok rednaxelafx at gmail.com
Thu Jan 25 22:30:31 UTC 2018

Hi Sergey,

Not a Reviewer but I like this patch a lot. Thanks for contributing it to OpenJDK!

Best regards, Kris

On Thu, Jan 25, 2018 at 2:02 PM, Сергей Цыпанов <sergei.tsypanov at yandex.ru> wrote:

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[] listtypeChecked(Data holder) { return holder.list.toArray(new Integer[0]); } @Benchmark public Integer[] subListtypeChecked(Data holder) { return holder.list.subList(0, holder.size).toArray(new Integer[0]); } @State(Scope.Thread) public static class Data { ArrayList 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.0162 on my PC (Intel i5-4690 3,5 GHz) it yields these results: Benchmark (size) Mode Cnt Score Error Units listtypeChecked 0 avgt 50 4,630 ± 0,062 ns/op listtypeChecked 10 avgt 50 16,629 ± 0,140 ns/op listtypeChecked 100 avgt 50 79,783 ± 1,676 ns/op listtypeChecked 1000 avgt 50 742,757 ± 10,357 ns/op subListtypeChecked 0 avgt 50 11,833 ± 0,801 ns/op subListtypeChecked 10 avgt 50 42,713 ± 0,590 ns/op subListtypeChecked 100 avgt 50 197,336 ± 3,560 ns/op subListtypeChecked 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[] 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

More information about the core-libs-dev mailing list