递归 ConcurrentHashMap.computeIfAbsent() 调用永远不会终止。错误还是 "feature"？

Question

不久前，I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively，使用 ConcurrentHashMap 缓存和新的有用的 computeIfAbsent() 方法：

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Test {
    static Map<Integer, Integer> cache = new ConcurrentHashMap<>();

    public static void main(String[] args) {
        System.out.println(
            "f(" + 8 + ") = " + fibonacci(8));
    }

    static int fibonacci(int i) {
        if (i == 0)
            return i;

        if (i == 1)
            return 1;

        return cache.computeIfAbsent(i, (key) -> {
            System.out.println(
                "Slow calculation of " + key);

            return fibonacci(i - 2) + fibonacci(i - 1);
        });
    }
}

我选择 ConcurrentHashMap 是因为我想通过引入并行性（我最终没有这样做）使这个例子更加复杂。

现在，让我们将数字从 8 增加到 25 并观察会发生什么：

        System.out.println(
            "f(" + 25 + ") = " + fibonacci(25));

程序永远不会停止。在方法内部，有一个永远运行的循环：

for (Node<K,V>[] tab = table;;) {
    // ...
}

我正在使用：

C:\Users\Lukas>java -version
java version "1.8.0_40-ea"
Java(TM) SE Runtime Environment (build 1.8.0_40-ea-b23)
Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)

Matthias, a reader of that blog post also confirmed the issue (he actually found it).

这很奇怪。我会期望以下两个中的任何一个：

有效
它抛出一个 ConcurrentModificationException

但就是永不停止？这看起来很危险。这是一个错误吗？还是我误解了某些合同？

Answer 1

这当然是一个"feature"。 ConcurrentHashMap.computeIfAbsent() Javadoc 显示：

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.

"must not" 的措辞是明确的约定，我的算法违反了，尽管不是出于相同的并发原因。

仍然有趣的是没有ConcurrentModificationException。相反，程序永远不会停止——在我看来这仍然是一个相当危险的错误（即 infinite loops. or: anything that can possibly go wrong, does）。

注：

HashMap.computeIfAbsent() or Map.computeIfAbsent() Javadoc 不禁止这种递归计算，这当然很荒谬，因为缓存的类型是 Map<Integer, Integer>，而不是 ConcurrentHashMap<Integer, Integer>。子类型彻底重新定义超类型契约是非常危险的（Set vs. SortedSet 是问候语）。 因此也应该禁止在超类型中执行这种递归。

Answer 2

这已在 JDK-8062841 中修复。

在 2011 proposal 中，我在代码审查期间发现了这个问题。更新了 JavaDoc 并添加了临时修复程序。由于性能问题，它在进一步重写中被删除。

2014 discussion, we explored ways to better detect and fail. Note that some of the discussion was taken offline to private email for considering the low-level changes. While not every case can be covered, the common cases will not livelock. These fixes 位于 Doug 的存储库中，但尚未进入 JDK 版本。

Answer 3

这与错误非常相似。因为，如果您创建容量为 32 的缓存，您的程序将运行到 49。有趣的是，参数 sizeCtl =32 + (32 >>> 1) + 1) =49！可能是调整大小的原因？

递归 ConcurrentHashMap.computeIfAbsent() 调用永远不会终止。错误还是 "feature"？

Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?

java

recursion

concurrenthashmap

java-8

注：