RFR: 8193031: Collections.addAll is likely to perform worse than Collection.addAll
https://bugs.openjdk.java.net/browse/JDK-8193031 http://cr.openjdk.java.net/~martin/webrevs/jdk/Collections-addAll/
On 12/4/17 7:50 PM, Martin Buchholz wrote:
https://bugs.openjdk.java.net/browse/JDK-8193031 http://cr.openjdk.java.net/~martin/webrevs/jdk/Collections-addAll/
* Adds all of the specified elements to the specified collection. * Elements to be added may be specified individually or as an array. * The behavior of this convenience method is identical to that of - * {@code c.addAll(Arrays.asList(elements))}, but this method is likely - * to run significantly faster under most implementations. + * {@code c.addAll(Arrays.asList(elements))}. * * <p>When elements are specified individually, this method provides a * convenient way to add a few elements to an existing collection: I agree with the removal of "significantly faster." In some real cases, it's definitely not! Usually the behavior wording isn't "is identical to". I'd prefer something like "the behavior is as if...." public static <T> boolean addAll(Collection<? super T> c, T... elements) { - boolean result = false; - for (T element : elements) - result |= c.add(element); - return result; + return c.addAll(Arrays.asList(elements)); } So, this seems sensible, but the tradeoffs aren't obvious. If the destination is an ArrayList, the first thing that addAll() does is call toArray() on the argument. And Arrays$ArrayList.toArray() makes a copy, as required by spec. So this redundantly copies every element, compared to the for-loop. But I did some quick benchmarks and I found that bulk copies are so fast that even doing two of them is quite a bit faster than a single copy in a for-loop, ranging from 4x-6x faster over a variety of sizes. This also requires temp space the size of the input array. This gives me (and the garbage collector) a bit of a pause. Turning to other collections, the AbstractCollection.addAll() implementation runs essentially the same loop as here, except that it runs it over its Collection argument instead of an array. Thus it uses an Iterator to loop instead of indexing over an array. Here, converting to a list has a slight performance disadvantage, around 10-15% (for HashSet, which uses AbstractCollection.addAll). You point out in the bug report that the implementation of Collections.addAll() misses out on optimizations that implementations can provide for bulk updates. This is true, but my feeling is that loses something by converting the array into a Collection before calling the virtual addAll(Collection) method. How about this alternative: do the same thing we did with sort(). Add a new default method Collection.addEach(T...) whose default implementation is either the original implementation of Collections.addAll() or your proposed modification. (We should use a name other than addAll, since overloading with a varargs method is a bad idea.) Add overrides for key implementations like ArrayList. Then, have Collections.addAll(c, T... elements) delegate to c.addEach(elements). For ArrayList, at least, this would avoid the redundant copy and temporary allocation, which seems nice. s'marks
+1 being also able to write, List<String> l = ... l.addEach("foo", "bar", "baz"); is a nice addition. Rémi ----- Mail original -----
De: "Stuart Marks" <stuart.marks@oracle.com> À: "Martin Buchholz" <martinrb@google.com> Cc: "core-libs-dev" <core-libs-dev@openjdk.java.net> Envoyé: Mardi 5 Décembre 2017 08:27:41 Objet: Re: RFR: 8193031: Collections.addAll is likely to perform worse than Collection.addAll
On 12/4/17 7:50 PM, Martin Buchholz wrote:
https://bugs.openjdk.java.net/browse/JDK-8193031 http://cr.openjdk.java.net/~martin/webrevs/jdk/Collections-addAll/
* Adds all of the specified elements to the specified collection. * Elements to be added may be specified individually or as an array. * The behavior of this convenience method is identical to that of - * {@code c.addAll(Arrays.asList(elements))}, but this method is likely - * to run significantly faster under most implementations. + * {@code c.addAll(Arrays.asList(elements))}. * * <p>When elements are specified individually, this method provides a * convenient way to add a few elements to an existing collection:
I agree with the removal of "significantly faster." In some real cases, it's definitely not! Usually the behavior wording isn't "is identical to". I'd prefer something like "the behavior is as if...."
public static <T> boolean addAll(Collection<? super T> c, T... elements) { - boolean result = false; - for (T element : elements) - result |= c.add(element); - return result; + return c.addAll(Arrays.asList(elements)); }
So, this seems sensible, but the tradeoffs aren't obvious.
If the destination is an ArrayList, the first thing that addAll() does is call toArray() on the argument. And Arrays$ArrayList.toArray() makes a copy, as required by spec. So this redundantly copies every element, compared to the for-loop.
But I did some quick benchmarks and I found that bulk copies are so fast that even doing two of them is quite a bit faster than a single copy in a for-loop, ranging from 4x-6x faster over a variety of sizes.
This also requires temp space the size of the input array. This gives me (and the garbage collector) a bit of a pause.
Turning to other collections, the AbstractCollection.addAll() implementation runs essentially the same loop as here, except that it runs it over its Collection argument instead of an array. Thus it uses an Iterator to loop instead of indexing over an array. Here, converting to a list has a slight performance disadvantage, around 10-15% (for HashSet, which uses AbstractCollection.addAll).
You point out in the bug report that the implementation of Collections.addAll() misses out on optimizations that implementations can provide for bulk updates. This is true, but my feeling is that loses something by converting the array into a Collection before calling the virtual addAll(Collection) method.
How about this alternative: do the same thing we did with sort().
Add a new default method Collection.addEach(T...) whose default implementation is either the original implementation of Collections.addAll() or your proposed modification. (We should use a name other than addAll, since overloading with a varargs method is a bad idea.) Add overrides for key implementations like ArrayList. Then, have Collections.addAll(c, T... elements) delegate to c.addEach(elements).
For ArrayList, at least, this would avoid the redundant copy and temporary allocation, which seems nice.
s'marks
participants (3)
-
Martin Buchholz
-
Remi Forax
-
Stuart Marks