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
