I'm back to playing around with hash tables of various flavors,
including some variants of the ConcurrentReaderHashMap I mentioned
here many months ago. Here's quick recap of background: The main idea
is to use a bin+list structure where the linked lists in each bin have
immutable (i.e. final) next-pointers and contents. This ensures that
you can read a list even if another thread is about to add (via simple
prepending, keeping all existing nodes) or remove (by rebuilding part
of the list if necessary). So, all the reader thread needs to ensure
is that it accesses the current list -- a valid bin of a valid table
(the table arrays may change when resizing).
There are three ways I know to ensure that reader threads get a valid
list:
1. Get the ref to the table under a synch lock, that is also
(briefly) held by writer threads upon any update. (From the
table list, you can then get to the bin/list).
2. An optimistic version of (1): get the table ref without synch, but if
you don't find what you are looking for, get it again, under synch.
(I once posted a version of this to this list.)
3. Get the ref after a read barrier, implemented by reading a volatile
that writers have written to after each update.
(3) is only guaranteed to work under the proposed "strong" volatile
rules. It's an instance of "publish-subscribe" barrier usage.
It turns out to be possible to get a glimpse right now of how these
fare. Even though (3) is only a proposal, I think I managed to get its
basic effects in an implementation that writes to volatiles only when
a thread is about to release the writer-exclusion lock anyway; and
done in a way that is very unlikely to be reordered. On a sparc in
TSO, this should have the same effect (although there is no way to
check), since a lock release includes a barrier.
Here are results of a test using 1-4 threads on a shared a dictionary
of 50000 words (from a linux /usr/dict/words), where each thread did,
1 million times: search for random word in word list, if absent then
with .75 probability add it, else if present, with .05 probablity
remove it. While only a synthetic benchmark, it's similar enough to
some real usage patterns to take seriously.
They were run on 2 JVMs on a 4-CPU Entrprise 450. Times in
milliseconds. Also, for comparison, are results using regular
java.util.HashMap and java.util.Hashtable.
First, EVM (Solaris production release 1.2.2_05a). Recall that this VM
passes all of Bill's volatile compliance tests except the
read-after-write test. I don't think there are any cases in this code
where read-after-write failures would lead to problems.
Threads 1 2 3 4
volatile 1551 2000 2846 5368
optimistic 1633 2491 3942 7349
lock 1939 6484 24196 40171
HashMap 1660
Hashtable 1886 15828 26884 30078
Next, a recent hotspot build, that fails ALL of Bill's volatile tests,
but even this is unlikely to be a correctness problem due to
underlying sparc properties.
Threads 1 2 3 4
volatile 1498 2087 2365 3018
optimistic 1553 3057 3982 4811
lock 1740 8974 14993 20302
HashMap 1659
Hashtable 1861 10435 16431 22550
The main moral is that, at least on machines with strong orderings,
adopting strong-volatile allows construction of faster library code.
Also note the pathetic performance of the locking version. The
contention for the lock needed solely as a memory barrier causes
pile-ups that sometimes turn out to be even worse (with 4 CPUs anyway)
than fully synchronizing the methods (as is done in
java.util.Hashtable). This suggests that even on machines with weaker
orderings, inserting the required barriers for volatiles is likely to
be much preferable to using locks.
Also note that the fact that java.util.Hashtable is "thread-safe"
doesn't mean that you'd actually want to use it in multithreaded
programs with heavy contention.
-- Doug Lea, Computer Science Department, SUNY Oswego, Oswego, NY 13126 USA dl@cs.oswego.edu 315-341-2688 FAX:315-341-5424 http://gee.cs.oswego.edu/ ------------------------------- JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:28 EDT