Kind reminder about JDK-8193031

[Tagir Valeev]

Hello!

If ArrayList is the collection which could mostly benefit from this, why
not peel off this case and provide special path for ArrayList only?
E.g. like this:

--- src/java.base/share/classes/java/util/ArrayList.java (revision
55248:10a2778ecbbfb1a9fc33c8cfade7e2479617b096)
+++ src/java.base/share/classes/java/util/ArrayList.java (date
1559791684058)
@@ -665,7 +665,10 @@
      * @throws NullPointerException if the specified collection is null
      */
     public boolean addAll(Collection<? extends E> c) {
-        Object[] a = c.toArray();
+        return addArray(c.toArray());
+    }
+
+    final boolean addArray(Object[] a) {
         modCount++;
         int numNew = a.length;
         if (numNew == 0)
===================================================================
--- src/java.base/share/classes/java/util/Collections.java (revision
55248:10a2778ecbbfb1a9fc33c8cfade7e2479617b096)
+++ src/java.base/share/classes/java/util/Collections.java (date
1549176714305)
@@ -5494,6 +5494,9 @@
      */
     @SafeVarargs
     public static <T> boolean addAll(Collection<? super T> c, T...
elements) {
+        if (c.getClass() == ArrayList.class) {
+            return ((ArrayList<?>) c).addArray(elements);
+        }
         boolean result = false;
         for (T element : elements)
             result |= c.add(element);

This would eliminate extra array copying and should produce even less
overhead for ArrayList at the cost of adding an extra classword check for
other collections which looks acceptable to me. This also allows to
postpone the decision about exposing a method like addArray into the
Collection API. This may also add an implicit optimization in some real
world programs converting c.add callsite from polymorphic to bimorphic or
from bimorphic to monomorphic, though additional benchmarks are necessary
to prove this.

With best regards,
Tagir Valeev.



On Fri, Jun 14, 2019 at 8:34 AM Stuart Marks <stuart.marks at oracle.com>
wrote:

> Hi Sergey,
>
> There are some links to a few other discussion threads in the bug report
> [1].
> I've added a link to this one. :-)
>
> It's too late for JDK 13, which entered RDP1 today. However, the JDK 14
> source
> base is open, and we can proceed there.
>
> In one of the previous discussions, I had suggested an alternative which
> is to
> add a default method ("addEach") that adds to a collection all the
> elements of a
> given array. This was probably a distraction from that discussion, and it
> might
> have had the side effect of derailing that discussion. So, sorry about
> that.
>
> Let's focus on Martin's proposal. Basically this replaces the for-loop
> with code
> that wraps the array with Arrays.asList and then simply calls
> Collection.addAll.
> There is also some spec cleanup.
>
> Overall I think this is fine, but I did have a reservation. If we have
>
>      Collections.addAll(arraylist, array)
>
> this would end up calling
>
>      arraylist.addAll(Arrays.asList(array))
>
> The first thing ArrayList.addAll() does is
>
>      Object[] a = c.toArray();
>
> which makes a copy of the input array. Right away, this seems like a waste.
>
> On the other hand, I observed that doing two bulk array copies was
> actually
> faster than making one copy using a for-loop. I don't remember what sizes
> I
> checked. I'm a bit surprised, though, I would have thought that some sizes
> would
> be faster and some slower. Perhaps someone should do some more benchmarks.
> But
> that seems like an advantage of using addAll.
>
> One thing I didn't think of previously was that using a for-loop to add
> elements
> one-at-a-time might resize the destination ArrayList more than once,
> resulting
> in some redundant copying, whereas a bulk copy with addAll() will resize
> the
> destination at most once before doing the copy. That's another point in
> favor of
> using addAll().
>
> In summary, while this might seem like an obvious thing to do, it's not a
> no-brainer, and there are some subtle tradeoffs. We might end up doing
> this
> eventually, but it would be good to have a better handle on the tradeoffs
> and
> potential impact.
>
> Martin was working on this most recently. Martin, what do you think?
>
> s'marks
>
>
>
>
>
>
>
> On 6/13/19 4:39 AM, Сергей Цыпанов wrote:
> > Hello,
> >
> > the issue [1] was opened almost two years ago,
> > but even today Collections.addAll still looks like this:
> >
> > public static <T> boolean addAll(Collection<? super T> c, T... elements)
> {
> >      boolean result = false;
> >      for (T element : elements)
> >          result |= c.add(element);
> >      return result;
> > }
> >
> > The most wide-spread collections in Java-world is ArrayList for which
> Collections.addAll is likely to be slower then
> Collection.addAll(Arrays.asList).
> > The same is valid for ArrayDeque and especially for COWList. There's a
> webrev [2] for mentioned ticket. The whole story begins in [3].
> >
> > Could the change [2] be done for JDK 13?
> >
> > Regards,
> > Sergey Tsypanov
> >
> >
> > 1. https://bugs.openjdk.java.net/browse/JDK-8193031
> > 2. http://cr.openjdk.java.net/~martin/webrevs/jdk/Collections-addAll
> > 3.
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2017-December/050326.html
> >
>