재귀 ConcurrentHashMap.computeIfAbsent () 호출은 종료되지 않습니다.

재귀 ConcurrentHashMap.computeIfAbsent () 호출은 종료되지 않습니다. 버그 또는 "기능"?

---

몇 시간 전, 나는 반복적으로 피보나치 숫자를 계산하는 자바 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)

해당 블로그 게시물의 독자 인 Matthias도 문제를 확인했습니다 (실제로 발견했습니다) .

이것은 이상합니다. 다음 두 가지 중 하나를 예상했을 것입니다.

• 효과가있다
• 그것은 던졌습니다 ConcurrentModificationException

하지만 절대 멈추지 않나요? 위험 해 보입니다. 버그입니까? 아니면 계약을 오해 했습니까?

---

이것은 JDK-8062841 에서 수정되었습니다 .

에서 2,011 제안 , 나는 코드 검토 중에이 문제를 확인했다. JavaDoc이 업데이트되고 임시 수정이 추가되었습니다. 성능 문제로 인해 추가 재 작성에서 제거되었습니다.

에서 2014 토론 , 우리는 더 나은 감지하고 실패 할 수있는 방법을 탐구. 일부 토론은 낮은 수준의 변경 사항을 고려하여 비공개 이메일로 오프라인으로 전환되었습니다. 모든 케이스를 다룰 수있는 것은 아니지만 일반적인 케이스는 라이브 락이 아닙니다. 이러한 수정 사항 은 Doug의 저장소에 있지만 JDK 릴리스에는 포함되지 않았습니다.

---

This is of course a "feature". The ConcurrentHashMap.computeIfAbsent() Javadoc reads:

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.

The "must not" wording is a clear contract, which my algorithm violated, although not for the same concurrency reasons.

What's still interesting is that there is no ConcurrentModificationException. Instead, the program just never halts - which still is a rather dangerous bug in my opinion (i.e. infinite loops. or: anything that can possibly go wrong, does).

Note:

The HashMap.computeIfAbsent() or Map.computeIfAbsent() Javadoc don't forbid such recursive computation, which is of course ridiculous as the type of the cache is Map<Integer, Integer>, not ConcurrentHashMap<Integer, Integer>. It is very dangerous for subtypes to drastically re-define super type contracts (Set vs. SortedSet is greeting). It should thus be forbidden also in super types, to perform such recursion.

---

This is very similar to the bug. Because, if you create your cache with capacity 32, your program will work until 49. And it is interesting, that parameter sizeCtl =32 + (32 >>> 1) + 1) =49! May be the reason in resizing?

참고URL : https://stackoverflow.com/questions/28840047/recursive-concurrenthashmap-computeifabsent-call-never-terminates-bug-or-fea