[concurrency-interest] Scalability of ConcurrentHashMap#computeIfAbsent

Josh Humphries jhump at bluegosling.com
Thu Jul 6 11:38:04 EDT 2017


On Thu, Jul 6, 2017 at 11:11 AM, Jonas Konrad <me at yawk.at> wrote:

> I don't see how pessimistic locking is *required* for computeIfAbsent with
> a fast path for already-existing elements. It could basically do
> double-checked locking (and you can already to that manually, with the same
> guarantees as computeIfAbsent).


True enough. It is not required for the read case, when a value already
exists. In the latest JSR166 sources (targeted for JDK 9 I guess), if the
key is the first in the bin, it will be returned without locking. But if
querying the key encounters a hash collision (e.g. requires traversing a
list or tree in the bin), then a lock is acquired.


>
> On 2017-07-06 17:01, Josh Humphries wrote:
>
>> On Thu, Jul 6, 2017 at 10:47 AM, Doug Lea <dl at cs.oswego.edu
>> <mailto:dl at cs.oswego.edu>> wrote:
>>
>>     On 07/06/2017 10:14 AM, Benoit Daloze wrote:
>>
>>     > I have been chasing a scalability problem that only happens with
>> over 8
>>     > cores on my benchmark and it turns out
>>     > ConcurrentHashMap#computeIfAbsent when used as a cache with the
>> same key
>>     > does not scale.
>>
>>
>> This is necessary since the spec
>> <https://docs.oracle.com/javase/8/docs/api/java/util/concurr
>> ent/ConcurrentHashMap.html#computeIfAbsent-K-java.util.function.Function->
>> indicates
>> that the operation (including computation of the value) is atomic. To
>> make this atomic, it must use pessimistic locking, so it seems you are
>> observing lock contention. (Interestingly, this behavior contrasts with
>> the default implementation
>> <https://docs.oracle.com/javase/8/docs/api/java/util/concurr
>> ent/ConcurrentMap.html#computeIfAbsent-K-java.util.function.Function-> in
>> the ConcurrentMap interface, which uses optimistic concurrency and
>> retries and makes no promise of atomicity.) The scalability of the map
>> relies on many threads operating on different keys, not all operations
>> using the same key.
>>
>> Your work-around, to have every thread eagerly execute the function in
>> parallel and then "first one wins" to store the value in the map, looks
>> appropriate.
>>
>>
>>
>>     Please try this using JDK9, which locks only on (possible) hash
>>     collision. (See discussion in list archives.)
>>
>>
>> The original question indicates the operation not scaling is for the
>> same key, so I think it will encounter a hash collision and the same
>> scalability issue even with this patch.
>>
>
I misunderstood your comment, Doug. Looks like this would indeed help
reduce the likelihood of the scalability issue observed.
Sorry.


>
>>
>>     If we had known that JDK9 would face so much adoption delay,
>>     we might have tried to arrange backports of this and other minor
>>     improvements and fixes...
>>
>>     -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
>>     <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
>>
>> _______________________________________________
> 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/20170706/42ec8069/attachment.html>


More information about the Concurrency-interest mailing list