Proposal: ArrayList constructor perforrmance improvement
Steve Groeger
GROEGES at uk.ibm.com
Tue Dec 18 16:44:15 UTC 2018
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
More information about the core-libs-dev
mailing list