This is no question that we can optimize the case of ArrayList -> ArrayList, but what about all the other Collection implementations? ArrayDeque and CopyOnWriteArrayList come to mind. ArrayList is a popular class to use for making copies of Collections. Where do you stop?
A pathological subclass of ArrayList could decide to not store elements in the backing array, with ensuing breakage. The blessed solution to the list copy problem is probably List.copyOf https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/List.html#copyOf(java.util.Collection) which might do the optimization you're hoping for. On Tue, Dec 18, 2018 at 8:47 AM Steve Groeger <groe...@uk.ibm.com> wrote: > Hi all, > > I am proposing an enhancement to ArrayList.java to improve its > performance. > > ArrayList has a constructor which takes an arbitrary Collection as a > parameter. This constructor will create an iterator over the collection > and it will add each entry returned to the ArrayList. > > We have found that quite a lot of the time the object passed as a > parameter is in fact an instance of ArrayList. > In the case of an ArrayList it is possible to significantly increase the > performance of the method since there is no need for an iterator - the > backing array can be directly copied. > > I would like to propose the following change: > > webrev: > http://cr.openjdk.java.net/~sgroeger/perf/arraylist/webrev.00/ > > hg diff: > > diff -r 086dfcfc3731 src/java.base/share/classes/java/util/ArrayList.java > --- a/src/java.base/share/classes/java/util/ArrayList.java Thu Dec 13 > 08:36:10 2018 +0100 > +++ b/src/java.base/share/classes/java/util/ArrayList.java Tue Dec 18 > 11:35:22 2018 +0000 > @@ -176,15 +176,21 @@ > * @throws NullPointerException if the specified collection is null > */ > public ArrayList(Collection<? extends E> c) { > - elementData = c.toArray(); > - if ((size = elementData.length) != 0) { > - // defend against c.toArray (incorrectly) not returning > Object[] > - // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652 > ) > - if (elementData.getClass() != Object[].class) > - elementData = Arrays.copyOf(elementData, size, > Object[].class); > + if (c instanceof ArrayList) { > + elementData = new Object[((ArrayList)c).elementData.length]; > + System.arraycopy(((ArrayList)c).elementData, 0, elementData, > 0, ((ArrayList)c).elementData.length); > + size = ((ArrayList)c).size; > } else { > - // replace with empty array. > - this.elementData = EMPTY_ELEMENTDATA; > + elementData = c.toArray(); > + if ((size = elementData.length) != 0) { > + // defend against c.toArray (incorrectly) not returning > Object[] > + // (see e.g. > https://bugs.openjdk.java.net/browse/JDK-6260652) > + if (elementData.getClass() != Object[].class) > + elementData = Arrays.copyOf(elementData, size, > Object[].class); > + } else { > + // replace with empty array. > + this.elementData = EMPTY_ELEMENTDATA; > + } > } > } > > due to the re-indentation the diff looks more complicated that it actually > is, the the change just adds this: > > + if (c instanceof ArrayList) { > + elementData = new Object[((ArrayList)c).elementData.length]; > + System.arraycopy(((ArrayList)c).elementData, 0, elementData, > 0, ((ArrayList)c).elementData.length); > + size = ((ArrayList)c).size; > > I have a JMH test that tests the creation of a new ArrayList, using a > separate ArrayList of different sizes then adds an items to the new > ArrayList. > http://cr.openjdk.java.net/~sgroeger/perf/arraylist/ArrayListBenchmark.java > > Test results from running the above JMH test are: > With Oracle OpenJDK12 > > Without performance change > Benchmark (size) Mode Cnt Score > Error Units > ArrayListBenchmark.construct_new_array_list 10 thrpt 25 388.212 ± > 23.110 ops/s > ArrayListBenchmark.construct_new_array_list 100 thrpt 25 90.208 ± > 7.995 ops/s > ArrayListBenchmark.construct_new_array_list 1000 thrpt 25 23.289 ± > 1.687 ops/s > ArrayListBenchmark.construct_new_array_list 10000 thrpt 25 7.659 ± > 0.560 ops/s > > With performance change > Benchmark (size) Mode Cnt Score > Error Units > ArrayListBenchmark.construct_new_array_list 10 thrpt 25 562.678 ± > 37.370 ops/s > ArrayListBenchmark.construct_new_array_list 100 thrpt 25 119.791 ± > 13.232 ops/s > ArrayListBenchmark.construct_new_array_list 1000 thrpt 25 33.811 ± > 3.812 ops/s > ArrayListBenchmark.construct_new_array_list 10000 thrpt 25 10.889 ± > 0.564 ops/s > > Results of the JTReg test for jdk/java/util/ArayList are the same with > and without the performance change. > > Any comments would be gratefully received. > > Thanks > Steve Groeger > IBM Runtime Technologies > Hursley, Winchester > Tel: (44) 1962 816911 Mobex: 279990 Mobile: 07718 517 129 > Fax (44) 1962 816800 > Lotus Notes: Steve Groeger/UK/IBM > Internet: groe...@uk.ibm.com > > Unless stated otherwise above: > IBM United Kingdom Limited - Registered in England and Wales with number > 741598. > Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU > Unless stated otherwise above: > IBM United Kingdom Limited - Registered in England and Wales with number > 741598. > Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU > >
