[concurrency-interest] ConcurrentHashMap computeIfAbsent

Benjamin Manes ben.manes at gmail.com
Sun Dec 21 14:36:11 EST 2014

> This is worth considering, but it only detects one form of
> misbehavior when the bin doesn't hold any other nodes.
> Otherwise, the first node need not be a ReservationNode.

I'm not comfortable enough with the code to experiment, but reading it I
keep wondering if inserting a node prior to computation would provide
detection. The value would be null, to be filled in if the computation
succeeds. If a reentrant computation occurs then when the existing node is
found and we observe that the value is unset, then we have detected a cycle
since we already hold the necessary lock. This would require skipping those
nodes for methods that traverse the entire map, like iterators and size().

Internally, this would make computations feel more like the JCiP-style
future based approach Viktor mentioned and allow for supporting batch
computations. It has the nice property of not wasting more memory with
values wrapped in futures, unless an asynchronous cache was explicitly
requested. That can be built on-top of CHM, as was always possible, and an
API option that I plan on providing.

The remaining mysterious cases are nested computeIfAbsent
> calls for different keys that happen to hash to the same bin.
> These conceptually ought to deadlock. Instead they will
> sometimes happen to "work" but other times loop.

If changes like the above removed the live lock issue, then I'd be much
happier with a resulting deadlock remain unsolved. That's much easier for
developers to notice with jdk tooling when debugging server issues and
recognize the problem as their fault.

On Sun, Dec 21, 2014 at 10:07 AM, Viktor Klang <viktor.klang at gmail.com>

> On Sun, Dec 21, 2014 at 4:47 PM, Doug Lea <dl at cs.oswego.edu> wrote:
>> On 12/21/2014 09:59 AM, Viktor Klang wrote:
>>> For "computeIfAbsent"-style maps which are intended for multithreaded
>>> use, I
>>> tend to prefer to use ConcurrentMap[Key, CompletionStage[Value]],
>> Right. Prior to jdk8, we suggested variations of this and other
>> techniques that remain preferable in many cases. However, the
>> most common CHM user error was trying (but failing) to emulate
>> what is now supported as computeIfAbsent. This is an improvement,
>> but leads to new (much less common) kinds of potential errors.
>> We cannot automatically eliminate or trap all of them. It
>> might be possible to do more than we do now, either internally
>> (inside CHM) or, more likely, with improved developer tools.
> Absolutely, and the fact that there was only blocking Futures in the JDK
> at that time.
> Having "monadic" Futures like CompletableFuture means you can avoid
> blocking completely (assuming that the CHM impl is non-blocking). This is
> highly useful when using it as a cache, and especially if there's a very
> skewed read distribution, paired with a multitude of readers.
>> -Doug
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> --
> Cheers,
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141221/0b8f4f5c/attachment-0001.html>

More information about the Concurrency-interest mailing list