ConcurrentHashMap computeIfAbsent再帰呼び出しはNG

Java8で導入された java.util.concurrent.ConcurrentHashMap#computeIfAbsent メソッドでは、computeIfAbsentメソッドから呼出される計算処理中から、再帰処理によって同ConcurrentHashMapオブジェクトのcomputeIfAbsentメソッドを再度呼び出してはならない。

ConcurrentHashMapクラスの仕様上、このような制約が課されている。Java8 API Specificationより該当箇所引用（下線部は強調）。

public V computeIfAbsent(K key,
　　Function<? super K,? extends V> mappingFunction)
(snip) 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.
ConcurrentHashMap (Java Platform SE 8 )

JDK-8062841にて報告されている通り、OpenJDKバージョンによっては処理ストールを引き起こす。2015年3月現在、JSR-166上では修正済みだが、JDKへの修正適用は未リリースとのこと。

Map<Integer, Integer> cache = new ConcurrentHashMap<>();

int cached_fib(int i) {
  if (i < 2) {
    return 1;
  } else {
    return cache.computeIfAbsent(i, (key) -> {
      return cached_fib(i - 2) + cached_fib(i - 1);
      // NG: cached_fib()メソッドの再帰呼び出しにより
      // cache.computeIfAbsentが再び呼出される
    });
  }
}

yohhoyの日記

技術的メモをしていきたい日記

ConcurrentHashMap computeIfAbsent再帰呼び出しはNG