[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.
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
- 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.
- Some discipline is necessary to ensure that the array values are never
- All modification of the array field should happen through the updater
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
- 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
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).
Note - originally sent this from my personal account (thanks Thunderbird!)
so if it comes through twice, sorry... Moderator, feel free to kill the
More information about the Concurrency-interest