[concurrency-interest] Scalability of ConcurrentHashMap#computeIfAbsent

Benjamin Manes ben.manes at gmail.com
Thu Jul 6 11:53:08 EDT 2017


An interesting insight Doug offered when this was first discussed is that
the performance profile differs at 32+ cores. I was surprised and able to
reproduce his results, though I still used the fast path in Caffeine for a
variety of reasons. If I recall correctly, a Zipf spread of keys was faster
with the pessimistic locking and a single key was much more comparable
(perhaps half the throughput). I would not have guess that interactions
with biased locking and safe points would have changed the profile that
much and depend on reaching a threshold core count. I still can't claim to
grok that.

On Thu, Jul 6, 2017 at 8:38 AM, Josh Humphries <jhump at bluegosling.com>
wrote:

>
> 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.funct
>>> ion.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
>>
>
>
> _______________________________________________
> 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/ba535eca/attachment-0001.html>


More information about the Concurrency-interest mailing list