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

问题描述

前段时间，我已经在博客上写了一篇关于递归计算斐波那契数的 Java 8 函数式方法，带有 ConcurrentHashMap 缓存和新的、有用的 computeIfAbsent() 方法:

import java.util.Map;导入 java.util.concurrent.ConcurrentHashMap;公共类测试{静态映射<整数，整数>cache = new ConcurrentHashMap<>();公共静态无效主(字符串 [] args){System.out.println("f(" + 8 + ") = " + 斐波那契(8));}静态 int fibonacci(int i) {如果(我== 0)返回我；如果(我== 1)返回 1；return cache.computeIfAbsent(i, (key) -> {System.out.println("+键的"慢计算);返回斐波那契(i - 2) + 斐波那契(i - 1);});}}

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

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

 System.out.println("f(" + 25 + ") = " + 斐波那契(25));

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

for (Node[] tab = table;;) {//...}

我正在使用:

C:UsersLukas>java -versionjava版本1.8.0_40-ea"Java(TM) SE 运行时环境(构建 1.8.0_40-ea-b23)Java HotSpot(TM) 64 位服务器 VM(构建 25.40-b25，混合模式)

马蒂亚斯，那篇博文的一位读者也证实了这个问题(他确实发现了).

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

• 有效
• 它抛出一个 ConcurrentModificationException

但就是从不停止?那看起来很危险.这是一个错误吗?还是我误解了一些合同?

解决方案

此问题已在 JDK-8062841 中修复

一>.

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

在 2014 年的讨论中，我们探索了更好地检测并失败.请注意，为了考虑低级别更改，一些讨论已离线发送到私人电子邮件中.虽然不是每个案例都可以涵盖，但普通案例不会活锁.这些 修复 位于 Doug 的存储库中，但尚未包含在 JDK 版本中.

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);
        });
    }
}

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

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;;) {
    // ...
}

I'm using:

C:UsersLukas>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).

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

• It works
• It throws a ConcurrentModificationException

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

解决方案

This is fixed in JDK-8062841.

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.

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屋！