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

[Martin Buchholz]

I'm still advocating an optimistic approach, that does not hold the lock
during the first traversal of the array snapshot.  This is much faster when
cache hits are the norm (or equals methods are expensive), which I would
hope would be the common case, and only slightly slower when all adds are
cache misses.

     public boolean addIfAbsent(E e) {
        Object[] snapshot = getArray();
        int len = snapshot.length;
        for (int i = 0; i < len; i++)
            if (eq(e, snapshot[i]))
                return false;
        return addIfAbsent(e, snapshot);
    }

    private boolean addIfAbsent(E e, Object[] snapshot) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] current = getArray();
            int len = current.length;
            if (snapshot != current) {
                // Optimize for contending with another addIfAbsent
                int common = Math.min(snapshot.length, len);
                for (int i = 0; i < common; i++)
                    if (current[i] != snapshot[i] && eq(e, current[i]))
                        return false;
                for (int i = common; i < len; i++)
                    if (eq(e, current[i]))
                        return false;
            }
            Object[] newElements = Arrays.copyOf(current, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }



On Fri, Apr 5, 2013 at 5:27 AM, Doug Lea <dl at cs.oswego.edu> wrote:

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