[concurrency-interest] ConcurrentHashMap computeIfAbsent

Doug Lea dl at cs.oswego.edu
Sun Dec 21 17:32:14 EST 2014

On 12/21/2014 02:33 PM, Peter Levart wrote:

> ... but measuring on my i7 Linux PC shows that holdsLock() amounts to an
> addition of 2/3 the overhead of non-contended locking.
> If we added an int field to Node class...

... then we'd probably do a lot more with it than this :-)

Among the requests/goals for jdk8 CHM was to reduce, not increase,
footprint compared to previous versions. Introducing space overhead
for the sake of small improvements in helping to diagnose uncommon
user errors is not a very defensible tradeoff.

But there may be some ways to more narrowly address the actual
user error scenarios; i.e., for m.computeIfAbsent(k1, f) where
function f calls m.computeIfAbsent(k2, ...),
across three cases: (1) k1 != k2 and they reside in different bins,
or (2) k1 != k2 but they reside in the same bin, or (3) k1 == k2.
(Further mixtures with computeIfPresent, compute, and/or merge
don't seem to change the basic problem.)

We should write off coping with deadlock and infinite recursion. But
we can still add some (cheap) integrity checks that can only be
violated in the remaining user-error scenarios. In particular
the one below, which will only trigger after-the-fact, but
still effective. I'll explore others too.

*** ConcurrentHashMap.java.~1.258.~	2014-12-20 11:16:27.835140276 -0500
--- ConcurrentHashMap.java	2014-12-21 17:23:43.233685637 -0500
*** 1633,1638 ****
--- 1633,1639 ----
                           } finally {
                               setTabAt(tab, i, node);
+                         if (r.next != null) throw new IllegalStateException();
                   if (binCount != 0)

More information about the Concurrency-interest mailing list