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

[Martin Buchholz]

Thanks, Сергей
I filed a bug for you
https://bugs.openjdk.java.net/browse/JDK-8196207

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[] 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
>