java ConcurrentHashMap computeIfAbsent

ConcurrentHashMap computeIfAbsent

提问by Vic

There is a new computeIfAbsent API introduced in Java 8. The javadocs for ConcurrentHashMap's impelementation of itstate:

Java 8 中引入了一个新的 computeIfAbsent API。ConcurrentHashMap 对其实现的javadocs状态：

If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. The entire method invocation is performed atomically, so the function is applied at most once per key. Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

如果指定的键尚未与值关联，则尝试使用给定的映射函数计算其值并将其输入此映射，除非为空。整个方法调用以原子方式执行，因此每个键最多应用一次该函数。其他线程在此映射上尝试的一些更新操作可能会在计算过程中被阻塞，因此计算应该简短且简单，并且不得尝试更新此映射的任何其他映射。

So, what does it say about locking of this implementation in case when the the key already exists and the computation is unneeded? Is the whole method computeIfAbsent synchronized as stated in docs even if no calculation is needed or just the mapping function call is syncronized to prevent calling the function twice?

那么，在密钥已经存在并且不需要计算的情况下，锁定这个实现是什么意思？即使不需要计算或者只是映射函数调用被同步以防止调用函数两次，整个方法computeIfAbsent是否如文档中所述同步？

采纳答案by Cristian Greco

The implementation of ConcurrentHashMapis quite complex, as it is specifically designed to allow concurrent readability while minimizing update contention. At a very high level of abstraction, it is organized as a bucketed hash table. All read operations do not require locking, and (quoting the javadoc) "there is not any support for locking the entire table in a way that prevents all access". To accomplish this, the internal design is highly sophisticated (but still elegant), with key-value mappings held in nodes which can be arranged in various ways (such as lists or balanced trees) in order to take advantage of fine grained locks. If you're interested in implementation details you can also have a look at the source code.

ConcurrentHashMap的实现非常复杂，因为它专门设计为允许并发可读性，同时最大限度地减少更新争用。在非常高的抽象层次上，它被组织为一个分桶哈希表。所有读取操作都不需要锁定，并且（引用 javadoc）“不支持以阻止所有访问的方式锁定整个表”。为了实现这一点，内部设计非常复杂（但仍然优雅），键值映射保存在节点中，可以以各种方式（例如列表或平衡树）排列，以利用细粒度锁。如果您对实现细节感兴趣，还可以查看源代码。

Trying to answer your questions:

尝试回答您的问题：

So, what does it say about locking of this implementation in case when the the key already exists and the computation is unneeded?

那么，在密钥已经存在并且不需要计算的情况下，锁定这个实现是什么意思？

It is reasonable to think that, as with any read operation, no locking is required to check if the key already exists and the mapping function does not need to be executed.

可以合理地认为，与任何读取操作一样，不需要锁定来检查密钥是否已经存在，也不需要执行映射函数。

Is the whole method computeIfAbsent synchronized as stated in docs even if no calculation is needed or just the mapping function call is synchronized to prevent calling the function twice?

即使不需要计算或者只是映射函数调用被同步以防止调用函数两次，整个方法computeIfAbsent是否如文档中所述同步？

No, the method is not synchronizedin terms of locking, but from the point of view of the caller it is executed atomically (i.e. the mapping function is applied at most once). If the key is not found, an update operation must be performed using the value computed by the mapping function and some kind of locking is involved while that function is invoked. It is reasonable to think that such locking is very fine-grained and only involves a very small portion of the table (well, the specific data structure where the key has to be stored) and this is why (quoting the javadoc, emphasis mine) "someattempted update operations by other threads maybe blocked while computation is in progress".

不，该方法在锁定方面不是同步的，但从调用者的角度来看，它是原子地执行的（即映射函数最多应用一次）。如果未找到键，则必须使用映射函数计算的值执行更新操作，并且在调用该函数时涉及某种锁定。可以合理地认为这种锁定是非常细粒度的，并且只涉及表的很小一部分（嗯，必须存储密钥的特定数据结构），这就是原因（引用 javadoc，强调我的）“当计算正在进行时，其他线程尝试的一些更新操作可能会被阻止”。

回答by purplie

You canget contention when the value already exists.

当值已经存在时，您可能会发生争用。

If you look at the source code for computeIfAbsent(), it's pretty complex but you see that the check whether the value is already present is inside the synchronized block. Consider this alternate version (which doesn't operate atomically):

如果您查看computeIfAbsent() 的源代码，它非常复杂，但是您会看到检查值是否已经存在是在同步块内。考虑这个替代版本（它不以原子方式运行）：

/**
 * Alternate implementation that doesn't block when map already
 * contains the value
 */
public V computeIfAbsent2(K key, Function<? super K, ? extends V> mappingFunction) {
    V value = get(key);
    if (value == null) {
        value = mappingFunction.apply(key);
        put(key, value);
    }
    return value;
}

I ran a JMH test comparing this alternate implementation with the original. I ran 20 threads, and used a ConcurrentHashMap containing 20 values that already existed. Each thread would use all 20 values. The test exercised onlythe case that the value already exists. It ran on OS X. The result (after a 2-minute warmup) was

我运行了一个 JMH 测试，将这个替代实现与原始实现进行了比较。我运行了 20 个线程，并使用了一个包含 20 个已经存在的值的 ConcurrentHashMap 。每个线程将使用所有 20 个值。该测试仅在该值已存在的情况下进行。它在 OS X 上运行。结果（经过 2 分钟的预热）是

Benchmark                                     Mode  Cnt       Score   Error   Units
ComputIfAbsentTest.benchComputeAbsent        thrpt    2   77966.354          ops/ms
ComputIfAbsentTest.benchComputeAbsent2       thrpt    2  463096.033          ops/ms

I also tried running this with Flight Recording enabled, and the contention was clearly visible. Here's an example stack trace:

我还尝试在启用飞行记录的情况下运行它，并且争用清晰可见。这是一个示例堆栈跟踪：

"local.ComputIfAbsentTest.benchComputeAbsent-jmh-worker-11" #25 daemon prio=5 os_prio=31 tid=0x00007f89da10b000 nid=0x7203 waiting for monitor entry [0x00007000021f8000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674)
    - waiting to lock <0x0000000795f80540> (a java.util.concurrent.ConcurrentHashMap$Node)
    at local.ComputIfAbsentTest.benchComputeAbsent(ComputIfAbsentTest.java:87)
    at local.generated.ComputIfAbsentTest_benchComputeAbsent_jmhTest.benchComputeAbsent_thrpt_jmhStub(ComputIfAbsentTest_benchComputeAbsent_jmhTest.java:116)
    at local.generated.ComputIfAbsentTest_benchComputeAbsent_jmhTest.benchComputeAbsent_Throughput(ComputIfAbsentTest_benchComputeAbsent_jmhTest.java:76)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:483)
    at org.openjdk.jmh.runner.BenchmarkHandler$BenchmarkTask.call(BenchmarkHandler.java:430)
    at org.openjdk.jmh.runner.BenchmarkHandler$BenchmarkTask.call(BenchmarkHandler.java:412)
    at java.util.concurrent.FutureTask.run(FutureTask.java:266)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

回答by Amir Hadadi

The bugfix @RolandIllig mentioned states that contention can still occur if the key is not the first in the bin. I tested this using JMH with Java 10.

提到的错误修复 @RolandIllig 指出，如果密钥不是 bin 中的第一个，则仍可能发生争用。我使用 JMH 和 Java 10 对此进行了测试。

Throughput of luckyKey:

幸运密钥的吞吐量：

Result: 324172.798 ±(99.9%) 15244.448 ops/ms [Average]

Throughput of unluckyKey:

unluckyKey 的吞吐量：

Result: 15386.202 ±(99.9%) 526.877 ops/ms [Average]

Benchmark code

基准代码

@Threads(8)
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class ComputeIfAbsentBenchmark {

  @State(Scope.Benchmark)
  public static class MyState {
    private final Map<String, Integer> map = new ConcurrentHashMap<>();

    public MyState() {
      for (int i = 0; i < 100; i++)
        map.put(Integer.toString(i), i);
    }
  }

  @Benchmark
  public void luckyKey(final MyState state) {
    state.map.computeIfAbsent("1", key -> 100);
  }

  @Benchmark
  public void unluckyKey(final MyState state) {
    state.map.computeIfAbsent("98", key -> 100);
  }

}