Proposal: ArrayList constructor perforrmance improvement

[Steve Groeger]

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: groeges at 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