[concurrency-interest] RFR [8011215] optimization of CopyOnWriteArrayList.addIfAbsent()

[Doug Lea]

On 04/03/13 06:35, Doug Lea wrote:
> This was designed to perform best in the case of possibly contended
> updates when the element is absent, by avoiding retraversal, and
> thus minimizing lock hold times in the common case. (When not common,
> it can be guarded by a contains check.) However even in this case,
> it is possible that a retraversal via arraycopy could be faster
> because it can use optimized cheaper writes (fewer card marks).

Yes, by a little.
A simple but reliable performance test is now at
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/loops/COWALAddIfAbsentLoops.java?view=log

The simplest change allowing this (below) also appears to
be among the fastest. Running across various machines and
settings (GC, client/server), it seems to be between 5% and 15%
faster. This is a smaller difference than in Ivan's tests,
that didn't include lock and contention effects.

I committed jsr166 version. We'll need to sync this up with
with openjdk tl someday, but might as well wait until
other updates for Spliterators/streams are ready to integrate.

-Doug

*** CopyOnWriteArrayList.java.~1.100.~	Tue Mar 12 19:59:08 2013
--- CopyOnWriteArrayList.java	Fri Apr  5 08:03:29 2013
***************
*** 579,595 ****
           final ReentrantLock lock = this.lock;
           lock.lock();
           try {
-             // Copy while checking if already present.
-             // This wins in the most common case where it is not present
               Object[] elements = getArray();
               int len = elements.length;
-             Object[] newElements = new Object[len + 1];
               for (int i = 0; i < len; ++i) {
                   if (eq(e, elements[i]))
!                     return false; // exit, throwing away copy
!                 else
!                     newElements[i] = elements[i];
               }
               newElements[len] = e;
               setArray(newElements);
               return true;
--- 579,591 ----
           final ReentrantLock lock = this.lock;
           lock.lock();
           try {
               Object[] elements = getArray();
               int len = elements.length;
               for (int i = 0; i < len; ++i) {
                   if (eq(e, elements[i]))
!                     return false;
               }
+             Object[] newElements = Arrays.copyOf(elements, len + 1);
               newElements[len] = e;
               setArray(newElements);
               return true;