[concurrency-interest] ConcurrentHashMap computeIfAbsent

Benjamin Manes ben.manes at gmail.com
Sun Dec 21 16:20:45 EST 2014


Thanks Peter,

I don't think compute() changes my suggestion. If the bucket count is
larger than one, then I was suggesting inserting a regular Node with a null
value that is updated when the mapping function completes successfully. The
node is scavenged when the computation fails, but since we know the
instance that extra scan should be cheap. By updating a regular node I had
hoped one could avoid garbage in the common case.

Experimenting to determine the feasibility of this type of change is too
invasive for me to feel comfortable trying given the interactions with all
the other map operations that I may not fully consider at the moment. Since
ReservationNode is a special type, it seems likely that there are scenarios
that I'm not considering.

On Sun, Dec 21, 2014 at 12:53 PM, Peter Levart <peter.levart at gmail.com>
wrote:

>  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>
> wrote:
>
>>
>>
>> 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
>>
>>
>
>
> _______________________________________________
> Concurrency-interest mailing listConcurrency-interest at cs.oswego.eduhttp://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141221/61ec0ea4/attachment.html>


More information about the Concurrency-interest mailing list