[concurrency-interest] computeIfAbsent optimized for missing entries

Amir Hadadi amirhadadi at hotmail.com
Wed Feb 8 15:58:41 EST 2017


> Even if an element is apparently present, we need to guarantee
> that it is not in the process of being removed (while holding lock).


Let's assume computeIfAbsent is implemented by first checking if the key is present, returning the associated value if it is, and otherwise goes on to lock. So the mapping function is still performed under lock.

Let's say we have a CHM which initially maps a key K -> V.

Now thread T1 calls remove(K) concurrently with thread T2 calling computeIfAbsent(K, mappingFunction).

What sequence of events could T1, T2 or another thread T3 observe that is precluded by the existing implementation?

________________________________
From: Concurrency-interest <concurrency-interest-bounces at cs.oswego.edu> on behalf of Doug Lea <dl at cs.oswego.edu>
Sent: Wednesday, February 8, 2017 6:55:02 PM
To: concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] computeIfAbsent optimized for missing entries

On 02/08/2017 01:52 AM, Amir Hadadi wrote:
> I read the source code for ConcurrentHashMap's computeIfAbsent, and I
> noticed it enters a synchronized block whether or not the key is present.

computeIfAbsent must be more conservative than putIfAbsent because
we guarantee exclusion during the "compute" part.
Even if an element is apparently present, we need to guarantee
that it is not in the process of being removed (while holding lock).

There was a fair amount of pre-jdk8 discussion about whether to
guarantee locking/exclusion in CHM (it is not guaranteed for
ConcurrentMaps in general). The consensus was that it was
worth doing despite the extra overhead. Especially since it
is avoidable in cases where you know that a key will never be
removed once added, first calling get(), and then only
call computeIfAbsent if it returns null.


-Doug


_______________________________________________
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/20170208/0fb39860/attachment.html>


More information about the Concurrency-interest mailing list