Proposal: ArrayList constructor perforrmance improvement

[Martin Buchholz]

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
>
>