Proposal: ArrayList constructor perforrmance improvement
Martin Buchholz
martinrb at google.com
Tue Dec 18 17:23:38 UTC 2018
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 <GROEGES at 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: 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