递归ConcurrentHashMap.computeIfAbsent（）调用永远不会终止。错误或“功能”？ [英] Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?

问题描述

前一段时间，我已经关于以递归方式计算斐波纳契数的Java 8函数方法的博客，带有 ConcurrentHashMap 缓存和新的，有用的 computeIfAbsent（）方法：

Some time ago, I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively, with a ConcurrentHashMap cache and the new, useful computeIfAbsent() method:

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 因为我想通过引入并行性使这个例子变得更复杂（我最后没有）。

I chose ConcurrentHashMap because I was thinking of making this example even more sophisticated by introducing parallelism (which I didn't in the end).

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

Now, let's increase the number from 8 to 25 and observe what happens:

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

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

The program never halts. Inside the method, there's a loop that just runs forever:

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，该博客文章的读者也证实了这个问题（他实际上找到了它）。

这很奇怪。我原本期望以下两种中的任何一种：

This is weird. I would have expected any of the following two:

• 工作原理


• 它会抛出 ConcurrentModificationException

• It works
• It throws a ConcurrentModificationException

但是从不停止？这似乎很危险。这是一个错误吗？或者我是否误解了一些合同？

But just never halting? That seems dangerous. Is it a bug? Or did I misunderstand some contract?

推荐答案

这在 JDK-8062841 。

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

In the 2011 proposal, I identified this issue during the code review. The JavaDoc was updated and a temporary fix was added. It was removed in a further rewrite due to performance issues.

在 2014讨论，我们探索了更好地检测和失败的方法。请注意，有些讨论是针对私人电子邮件进行的，以便考虑低级别的更改。虽然不是每个案例都可以涵盖，但常见案例不会活锁。这些修复在Doug的存储库中，但尚未进入JDK版本。

In the 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 are in Doug's repository but have not made it into a JDK release.

这篇关于递归ConcurrentHashMap.computeIfAbsent（）调用永远不会终止。错误或“功能”？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！