[concurrency-interest] Atomic array field updater

David M. Lloyd david.lloyd at redhat.com
Thu Apr 23 19:03:19 EDT 2009


Unsatisfied with some of the limitations of CopyOnWriteArray* (and 
indirectly reminded by Sam Berlin), I thought I'd share a class that I 
wrote which I use to efficiently manage volatile array fields with 
immutable array values.

http://anonsvn.jboss.org/repos/jbossas/projects/jboss-threads/trunk/main/src/main/java/org/jboss/threads/AtomicArray.java

The precondition is that any array that you store in the field has to be 
immutable for most of these methods to work.  Basically it's an enhanced 
AtomicReferenceFieldUpdater that provides operations to atomically read and 
update array fields with copy-on-write semantics using basic add, remove, 
find, sort, and other operations.

It has a few advantages over CopyOnWriteArrayList/CopyOnWriteArraySet:

- Only one instance of AtomicArray per target class, rather than one per 
instance (similar to how AtomicReferenceFieldUpdater compares to 
AtomicReference).
- You can take a very efficient read-only snapshot of the value by simply 
copying the array reference.  (a snapshot with CopyOnWriteArray* involves 
calling clone(), which also clones the write lock which is not useful in 
most (?) snapshot situations)
- This class supports maintaining a sorted array with O(log N) lookup time 
using Arrays.binarySearch().  Thus it could be used to implement a 
copy-on-write sorted set.

Disadvantages:

- Some discipline is necessary to ensure that the array values are never 
mutated.
- All modification of the array field should happen through the updater 
instance.

Neither here nor there:

- There's a small optimization that avoids multiple copies of empty arrays 
from hanging around (it keeps one empty array instance for that array type).
- No locking is used on write.  If a write fails (cannot be completed 
atomically), it's retried.  In some situations this could cause excessive 
spinning, so the user would have to implement write locking on their own in 
this case.
- An AtomicReferenceFieldUpdater is used to update the field; its 
performance characteristics are not well understood (by me).  In any case, 
this class is best used in situations where the array is seldom modified 
(similar to COWA*) because every modification requires a whole copy of the 
original array.

Some other stuff could be added to this class as well.  What I've put in 
here is just stuff I've used and found to be useful.

Let me know what you guys think.  It's under LGPL but that is open to 
negotiation if it looks useful enough to actually include in the JDK/JSR166 
stuff in some form (though I doubt it because it's arguably redundant with 
respect to what's already in the JDK).

- DML

Note - originally sent this from my personal account (thanks Thunderbird!) 
so if it comes through twice, sorry...  Moderator, feel free to kill the 
original.


More information about the Concurrency-interest mailing list