[concurrency-interest] ConcurrentHashMapV8

Doug Lea dl at cs.oswego.edu
Mon Aug 29 13:37:20 EDT 2011


Thanks for all the on- and off- list comments and suggestions!
I committed an update with various improvements.
Some follow-ups:

On 08/28/11 17:42, Joe Bowbeer wrote:
> Given the restrictions placed on computeIfAbsent's function (invoked
> atomically, short & simple, must not attempt to update any other mappings), I
> would like to see a more complete example.

Yes, the javadoc could use an example. Suggestions for a
tiny but informative one would be welcome.

On 08/28/11 17:00, Ben Manes wrote:
> If computation is being added, then bulk computation should be implemented as
> well. This is useful when a computation requires an I/O call, so a batch
> operation is an important optimization. The simplest approach is to insert
> placeholder nodes that are populated after the computation has completed.

Thanks, but the plain version of CHM doesn't itself deal with Futures (aka
placeholders). However, a cache version might do so, possibly based on
a CHM<K, Future<V>>.

> It wasn't obvious to me how recursive computations are handled for the same
> key and appears to livelock. This is an error condition that used to
> deadlocked MapMaker. I fixed this by failing fast if Thread.holdsLock() was
> true prior to waiting for the computation to finish.

I'm not sure I follow. If the user function in turn calls computeIfAbsent
for the same key, then it seems irreparably broken in the same sense as,
for example. a user's equals() function that attempts to invoke map.put.

>
> The exceptional computation case may be worth documenting. CHM only fails

It is -- an exception leaves mapping untouched. The more arbitrary decision
is what to do if the computation returns null. ComputeIfAbsent could be defined
to throw NullPointerException, but this is a fairly heavy response to the
case where it turns out that the key has no mapping, since a null return
provides the same information.

> the computing thread and allows the waiting threads to retry the
> computation. In other implementations the waiting threads rethrow the
> exception and don't recompute.

Yes; I think this is the difference between a plain CHM and one that
uses Futures as values.

>
> A recompute (a.k.a. refresh) method may also be useful, though can be
> adequately supplied by usages. This recomputes the value, but allows readers
>  to continue to use the stale value until it completes. This can be useful
> for cache invalidation where it is preferred vs. exposing the latency to the
> user (if naively done by removing first).
>

Thanks! Yes, this (i.e. compute(k, f) vs computeIfAbsent(k, f))
is easy to add, and provides a symmetical API to the two forms
of put, and has some uses, so I added it.

On 08/28/11 22:52, Dane Foster wrote:
> Have you had an opportunity to benchmark this against Cliff Click's
> concurrent hash map?
>

Yes. Results vary across different kinds of tests, depending on operation
mixes, key types, temporal locality of lookups, etc, so I can't
give a better answer than: each is sometimes faster (and
sometimes by a lot) than the other. But the previous scalability
limits due to use of Segments is now gone, so the performance differences
now mostly reflect other design tradeoffs.

-Doug






More information about the Concurrency-interest mailing list