Recursive ConcurrentHashMap.computeIfAbsent() 调用永远不会终止。错误或“功能”?

2022-08-31 13:11:42

前段时间,我在博客上写了一篇关于Java 8函数式方法的博客,它使用缓存和新的有用方法递归计算斐波那契数列ConcurrentHashMapcomputeIfAbsent()

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

现在,让我们将数字从 增加到 to 并观察会发生什么:825

        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)也证实了这个问题(他实际上发现了这个问题)。

这很奇怪。我本来以为以下两个中的任何一个:

  • 它的工作原理
  • 它抛出一个ConcurrentModificationException

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


答案 1

这当然是一个“功能”。ConcurrentHashMap.computeIfAbsent() Javadoc 读取:

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

“不得”的措辞是一个明确的契约,我的算法违反了这个契约,尽管不是出于相同的并发原因。

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

注意:

HashMap.computeIfAbsent()Map.computeIfAbsent() Javadoc 不禁止这种递归计算,这当然是荒谬的,因为缓存的类型是 ,而不是。子类型大幅重新定义超类型协定( vs. 是问候)。因此,在超类型中也应该禁止执行此类递归。Map<Integer, Integer>ConcurrentHashMap<Integer, Integer>SetSortedSet


答案 2

此问题已在 JDK-8062841 中修复。

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

2014年的讨论中,我们探索了更好地检测和失败的方法。请注意,某些讨论已脱机到私人电子邮件,以考虑低级更改。虽然不是每个案例都可以涵盖,但普通案例不会活锁。这些修复程序位于 Doug 的存储库中,但尚未将其发布到 JDK 版本中。


推荐