[concurrency-interest] ReadMostlyVector vs CopyOnWriteArrayList

Doug Lea dl at cs.oswego.edu
Wed Feb 13 08:22:42 EST 2013

On 02/13/13 07:27, Markus Krainz wrote:
> Hi,
> I have a question regarding ReadMostlyVector from the jsr166e package. I had a
> look at the sourcecode and it uses StampedLock, for which some impressive
> benchmarks results have been reported on this. For it's use cases it seems
> pretty similar to CopyOnWriteArrayList. There are some subtile differences from
> the API docs. The CopyOnWriteArrayList iterator does not reflecting changes,
> while the ReadMostlyVector will reflect them on a best effort basis (if
> snapshotIterator() is not used). CopyOnWriteArrayList's cow might have higher
> memory overhead. When should we use ReadMostlyVector in preference to
> CopyOnWriteArrayList?

These are good questions, that I'd been planning to post something
about when jdk8 j.u.c StampedLock becomes routinely compilable/usable
using early-access jdk8 and/or lambda builds. (It is possible to
do so now only if you are willing to create a custom build
from repositories.) In the mean time, the current jsr166e.StampedLock
does a reasonable emulation of j.u.c version for JDK7+ systems.
So now seems as good a time as ever:

The ReadMostlyVector class was initially conceived as one
application of SequenceLocks. We found though that without
some sort of readLock capability, these kinds of applications
didn't work out very well. Which led to the replacement of
SequenceLock with StampedLock, which looks to be a
good choice for a lock in a lot of contexts. The released
ReadMostlyVector class was minimally adjusted to use it.
But it should be further reworked here and there, and renamed
to ConcurrentlyReadableVector, to reflect its reliance
on combinations of optimistic and pessimistic read-write-style
locking. (In fact, I've done most of this so I that can
continue to use this class for internal testing
of StampedLock, but it remains uncommitted because there is not
yet a place to put it in our repositories that would correctly
reflect dependencies on as-yet-unavailable JDK builds).

OK, finally to the questions: ConcurrentlyReadableVector
should often be a better choice than any of Vector,
CopyOnWriteArrayList, or Collections.synchronizedList(...ArrayList..).
But is not strictly a replacement for any of them:

* Pure read-only operations it's a bit slower than CopyOnWriteArrayList.
Not by much though.

* It's main iterator is NOT a snapshot, and can throw
ConcurrentModificationExceptions unless a read-mode
lock is used surrounding traversal. But we don't want to hand out
that lock. ConcurrentlyReadableVector can support this in
jdk8 using:
   forEachReadLocked(Consumer<E> action);

* Most update operations will run faster than in any of the
other classes. Generally much faster and with less
space/GC overhead than CopyOnWriteArrayList. And faster
than the others unless one is used purely single-threadedly, in
which case it is likely that JVM biased or fast-path locking  used
inside Vector and synchronizedList will perform a bit better.

My only other hesitance about releasing ConcurrentlyReadableVector
is that it might give the false impression than sequential-list
classes are usually a good choice for heavily concurrent
applications. They really aren't. When possible, use
ConcurrentHashMaps and related scalable data structures.


More information about the Concurrency-interest mailing list