[concurrency-interest] Scalability of ConcurrentHashMap#computeIfAbsent

Viktor Klang viktor.klang at gmail.com
Thu Jul 6 11:30:47 EDT 2017


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" <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).


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.
>
>
>     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/149fec07/attachment.html>


More information about the Concurrency-interest mailing list