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.tsypa...@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[] 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
>
