[concurrency-interest] Scalability of ConcurrentHashMap#computeIfAbsent

Benoit Daloze eregontp at gmail.com
Thu Jul 6 13:09:29 EDT 2017


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/
>>>> concurrent/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/
>>>> concurrent/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/11d5b020/attachment.html>


More information about the Concurrency-interest mailing list