[concurrency-interest] RFR [8011215] optimization of CopyOnWriteArrayList.addIfAbsent() (original) (raw)
Doug Lea dl at cs.oswego.edu
Fri Apr 5 12:27:40 UTC 2013
- Previous message: [concurrency-interest] RFR [8011215] optimization of CopyOnWriteArrayList.addIfAbsent()
- Next message: [concurrency-interest] RFR [8011215] optimization of CopyOnWriteArrayList.addIfAbsent()
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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;
- Previous message: [concurrency-interest] RFR [8011215] optimization of CopyOnWriteArrayList.addIfAbsent()
- Next message: [concurrency-interest] RFR [8011215] optimization of CopyOnWriteArrayList.addIfAbsent()
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]