[concurrency-interest] ConcurrentHashMap computeIfAbsent

Peter Levart peter.levart at gmail.com
Sun Dec 21 15:53:11 EST 2014


Hi Benjamin,

Doug is certainly the one to give you the best explanation, but let me 
try...

On 12/21/2014 08:36 PM, Benjamin Manes wrote:
>
>     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().

...ReservationNode is such node. But is only inserted (with CAS) as 1st 
node of the bucket when the bucket is still empty. This is to provide 
the object to use as the lock when changing anything in the bucket. It 
is replaced with normal Node when the function's result is obtained. 
Logically it is skipped on look-ups and traversals. If a node is 
inserted into the bucket that already contains nodes, no ReservationNode 
is used.

And it's not only inserting (computeIfAbsent) that calls-back user code. 
See also compute() method. This method overwrites the old value with new 
value returned from function in existing node or even removes a Node 
from the bucket (if function returns null). How would you detect that 
such process is taking place when you re-enter?

I thought about it for some time, but didn't find any existing state 
combination that could be used for such checks. Perhaps a 
ReservationNode could be inserted just after 1st node in bucket 
temporarily just to mark the fact that we entered synchronization block 
and later remove it before exiting the block. This would most probably 
work, but would also mean that we produce one object of garbage for each 
such call. Maybe this is better than 4 bytes of state overhead for each 
node (see my experiment).

>
> 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.

Don't forget that CHM provides a lock-free lookup. We would not like to 
loose this feature. Lazy evaluation (or waiting on computation) can be 
added on top of CHM if one needs it.

Regards, Peter

>
>     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 
> <mailto:viktor.klang at gmail.com>> wrote:
>
>
>
>     On Sun, Dec 21, 2014 at 4:47 PM, Doug Lea <dl at cs.oswego.edu
>     <mailto: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
>         <mailto: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
>     <mailto:Concurrency-interest at cs.oswego.edu>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>
> _______________________________________________
> 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/0f32bb32/attachment.html>


More information about the Concurrency-interest mailing list