递归ConcurrentHashMap.computeIfAbsent()调用永远不会终止.错误或"功能"？

Question

前段时间,我发表了一篇关于递归计算斐波纳契数的Java 8函数式方法的博文,其中包含一个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)

该博客文章的读者马蒂亚斯也证实了这个问题(他实际上发现了这个问题).

这很奇怪.我原以为是以下两种:

• 有用
• 它扔了一个 ConcurrentModificationException

但只是永远不会停止？这似乎很危险.这是一个错误吗？还是我误解了一些合同？

Answer 1

这当然是一个"功能".该ConcurrentHashMap.computeIfAbsent()Javadoc中写道:

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

在"绝不能"字眼是一个明确的合同,我的算法侵犯,尽管不是相同的并发原因.

有趣的是,没有ConcurrentModificationException.相反,程序永远不会停止 - 在我看来,这仍然是一个相当危险的错误(即无限循环.或者:任何可能出错的东西,确实如此).

注意:

该HashMap.computeIfAbsent()或Map.computeIfAbsent()的Javadoc不禁止这种循环的计算,这当然是可笑的高速缓存的类型Map<Integer, Integer>,不是ConcurrentHashMap<Integer, Integer>.子类型大幅度重新定义超类型合同是非常危险的(Set与SortedSet问候语相比).因此,在超类型中也应该禁止执行这种递归.

Answer 2

这已在JDK-8062841中修复.

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

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