[concurrency-interest] Scalability of ConcurrentHashMap#computeIfAbsent

Benoit Daloze eregontp at gmail.com
Thu Jul 6 13:12:25 EDT 2017


(but arguably the increment does not scale so well either if frequently
done on the same LongAdder)

On Thu, Jul 6, 2017 at 7:09 PM, Benoit Daloze <eregontp at gmail.com> wrote:

> Indeed, this is the exact same issue, thank you for the link!
>
> The fix only fixes the case where this is the first node in the bin (no
> collision) though, as Josh mentioned.
>
> This is interestingly contradicting CHM's own JavaDoc:
>
>  * <p>A ConcurrentHashMap can be used as a scalable frequency map (a
>  * form of histogram or multiset) by using {@link
>  * java.util.concurrent.atomic.LongAdder} values and initializing via
>  * {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
>  * to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
>  * {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
>
> This will not scale if a key accessed frequently is not the first in its
> bin.
>
> -Benoit
>
> On Thu, Jul 6, 2017 at 6:20 PM, Testo Nakada <test1 at doramail.com> wrote:
>
>> Does this have something to do with this JDK issue
>> http://bugs.java.com/bugdatabase/view_bug.do?bug_id=8161372?
>>
>> *Sent:* Thursday, July 06, 2017 at 8:53 AM
>> *From:* "Benjamin Manes" <ben.manes at gmail.com>
>> *To:* "Josh Humphries" <jhump at bluegosling.com>
>> *Cc:* concurrency-interest <concurrency-interest at cs.oswego.edu>
>> *Subject:* Re: [concurrency-interest] Scalability of
>> ConcurrentHashMap#computeIfAbsent
>> 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.
>>>>> 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
>>>>
>>>
>>> _______________________________________________
>>> 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/5f7aa348/attachment-0001.html>


More information about the Concurrency-interest mailing list