Scalability of ConcurrentHashMap#computeIfAbsent

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Scalability of ConcurrentHashMap#computeIfAbsent

Benoit Daloze
Hello all,

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.

Specifically, at least in Oracle JDK 8, #computeIfAbsent on the same key synchronizes every time (on the same object) to return the existing mapping value.
On the contrary, ConcurrentHashMap#get() does not synchronize and scales well.

I thought computeIfAbsent() is a nice method to cache things in a CHM, but obviously that's a very large drawback.

Original code not scaling:

Charset charset = encodingToCharsetMap.computeIfAbsent(encoding, EncodingManager::charsetForEncoding);

New code, scaling:

Charset charset = encodingToCharsetMap.get(encoding);
if (charset == null) {
    charset = EncodingManager.charsetForEncoding(encoding);
    encodingToCharsetMap.putIfAbsent(encoding, charset);
    // More complex if charsetForEncoding is not idempotent
}

It seems in general the implementation of computeIfAbsent() in JDK 8
is optimizing for the absent case, which makes little sense when the map is used as a cache.

Does using a ConcurrentHashMap as a cache with computeIfAbsent() make sense?
Do you think this worth a bug report?

-Benoit

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Doug Lea
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.

Please try this using JDK9, which locks only on (possible) hash
collision. (See discussion in list archives.)
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
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Josh Humphries-2
On Thu, Jul 6, 2017 at 10:47 AM, Doug Lea <[hidden email]> 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 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 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.
 
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
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Jonas Konrad
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).

On 2017-07-06 17:01, Josh Humphries wrote:

> On Thu, Jul 6, 2017 at 10:47 AM, Doug Lea <[hidden email]
> <mailto:[hidden email]>> 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.
>
>
>     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
>     [hidden email]
>     <mailto:[hidden email]>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>     <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Benoit Daloze
In reply to this post by Josh Humphries-2
Thank you for your answers, I'll give it a shot on JDK9.

As Jonas points out, I want to optimize for the key-is-present case.
I believe checking eagerly if the key is in the map does not affect semantics, but it might affect the performance of the absent case a tiny bit.

Another workaround which would work just as well here:

Charset charset = encodingToCharsetMap.get(encoding);
if (charset == null) {
    charset = encodingToCharsetMap.computeIfAbsent(encoding, EncodingManager::charsetForEncoding);
}

So essentially just adding a fast-path, because #computeIfAbsent does not scale on the same key when the key is already in the map.

-Benoit

On Thu, Jul 6, 2017 at 5:01 PM, Josh Humphries <[hidden email]> wrote:
On Thu, Jul 6, 2017 at 10:47 AM, Doug Lea <[hidden email]> 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 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 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.
 
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
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Viktor Klang
In reply to this post by Doug Lea
You could do a read, if absent you store a CompletableFuture with putIfAbsent, and if you win you complete it with the result of the computation, readers and losers of the putIfAbsent will get the CF and block until it is available...

--
Cheers,

On Jul 6, 2017 5:11 PM, "Jonas Konrad" <[hidden email]> 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).


On 2017-07-06 17:01, Josh Humphries wrote:
On Thu, Jul 6, 2017 at 10:47 AM, Doug Lea <[hidden email]
<mailto:[hidden email]>> 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.


    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
    [hidden email]
    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>





_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Josh Humphries-2
In reply to this post by Jonas Konrad

On Thu, Jul 6, 2017 at 11:11 AM, Jonas Konrad <[hidden email]> 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 <[hidden email]
<mailto:[hidden email]>> 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
    [hidden email]
    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Benjamin Manes
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 <[hidden email]> wrote:

On Thu, Jul 6, 2017 at 11:11 AM, Jonas Konrad <[hidden email]> 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 <[hidden email]
<mailto:[hidden email]>> 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
    [hidden email]
    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

testn
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" <[hidden email]>
To: "Josh Humphries" <[hidden email]>
Cc: concurrency-interest <[hidden email]>
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 <[hidden email]> wrote:
 
On Thu, Jul 6, 2017 at 11:11 AM, Jonas Konrad <[hidden email]> 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 <[hidden email]
<mailto:[hidden email]>> 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
    [hidden email]

    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
 
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Benoit Daloze
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 <[hidden email]> 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" <[hidden email]>
To: "Josh Humphries" <[hidden email]>
Cc: concurrency-interest <[hidden email]>
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 <[hidden email]> wrote:
 
On Thu, Jul 6, 2017 at 11:11 AM, Jonas Konrad <[hidden email]> 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 <[hidden email]
<mailto:[hidden email]>> 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
    [hidden email]

    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
 
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Benoit Daloze
(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 <[hidden email]> 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 <[hidden email]> 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" <[hidden email]>
To: "Josh Humphries" <[hidden email]>
Cc: concurrency-interest <[hidden email]>
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 <[hidden email]> wrote:
 
On Thu, Jul 6, 2017 at 11:11 AM, Jonas Konrad <[hidden email]> 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 <[hidden email]
<mailto:[hidden email]>> 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
    [hidden email]

    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
 
_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scalability of ConcurrentHashMap#computeIfAbsent

Alex Otenko
In reply to this post by Viktor Klang
Readers shouldn’t block.

Losers need a mechanism to contend again, if CF fails.


Alex


On 6 Jul 2017, at 16:30, Viktor Klang <[hidden email]> wrote:

You could do a read, if absent you store a CompletableFuture with putIfAbsent, and if you win you complete it with the result of the computation, readers and losers of the putIfAbsent will get the CF and block until it is available...

--
Cheers,

On Jul 6, 2017 5:11 PM, "Jonas Konrad" <[hidden email]> 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).


On 2017-07-06 17:01, Josh Humphries wrote:
On Thu, Jul 6, 2017 at 10:47 AM, Doug Lea <[hidden email]
<mailto:[hidden email]>> 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.


    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
    [hidden email]
    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>





_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Loading...