Recursive ConcurrentHashMap.wywołanie computeIfAbsent () nigdy się nie kończy. Bug czy "feature"?

Jakiś czas temu, pisałem na blogu o Java 8 functional way obliczania liczb Fibonacciego rekurencyjnie , z ConcurrentHashMap cache i nową, użyteczną computeIfAbsent() metodą:

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

Wybrałem ConcurrentHashMap, ponieważ myślałem o tym, aby ten przykład był jeszcze bardziej wyrafinowany, wprowadzając paralelizm (którego w końcu nie zrobiłem).

Teraz zwiększ liczbę z 8 do 25 i obserwuj, co się dzieje:

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

Program nigdy się nie zatrzymuje. Wewnątrz metody, jest pętla, która po prostu biegnie w nieskończoność:

for (Node<K,V>[] tab = table;;) {
    // ...
}

Używam:

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, czytelnik tego wpisu na blogu również potwierdził problem (faktycznie go znalazł) .

To dziwne. Spodziewałbym się jednego z następujących dwóch:
  • to działa
  • rzuca ConcurrentModificationException

Ale nigdy się nie zatrzymujesz? To wydaje się niebezpieczne. Czy to robak? Czy źle zrozumiałem jakiś kontrakt?

Author: Lukas Eder, 2015-03-03

3 answers

Jest to ustalone w JDK-8062841 .

We wniosku 2011 wskazałem ten problem podczas przeglądu kodu. Zaktualizowano JavaDoc i dodano tymczasową poprawkę. Został on usunięty w kolejnej przeróbce z powodu problemów z wydajnością.

W dyskusji 2014 zbadaliśmy sposoby na lepsze wykrywanie i niepowodzenie. Zauważ, że część dyskusji została przeniesiona do prywatnego e-maila w celu rozważenia zmian niskiego poziomu. Chociaż nie każdy przypadek może być objęty, typowe przypadki nie będą livelock. Te poprawki są w repozytorium Douga, ale nie zostały wprowadzone do wydania JDK.

 40
Author: Ben Manes,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-03-04 08:29:45

Jest to oczywiście "funkcja" . Na ConcurrentHashMap.computeIfAbsent() Javadoc czyta:

Jeśli podany klucz nie jest już skojarzony z wartością, próbuje obliczyć jego wartość za pomocą podanej funkcji mapowania i wprowadza ją do tej mapy, chyba że null. Całe wywołanie metody jest wykonywane atomicznie, więc funkcja jest stosowana co najwyżej raz na Klawisz. Niektóre próby aktualizacji na tej mapie przez inne wątki mogą zostać zablokowane podczas obliczeń, więc obliczenia powinny być krótkie i proste, a nie wolno próbować aktualizować żadnych innych map.

Sformułowanie "must not" jest wyraźną umową, którą mój algorytm naruszył, chociaż nie z tych samych powodów współbieżności.

Ciekawe jest to, że nie ma ConcurrentModificationException. Zamiast tego program po prostu nigdy się nie zatrzymuje - co nadal jest moim zdaniem dość niebezpiecznym błędem (tj. nieskończonych pętli. lub: wszystko, co może pójść wrong, does ).

Uwaga:

The HashMap.computeIfAbsent() lub Map.computeIfAbsent() Javadoc nie zabrania takich rekurencyjnych obliczeń, co jest oczywiście śmieszne, ponieważ Typ pamięci podręcznej to Map<Integer, Integer>, a nie ConcurrentHashMap<Integer, Integer>. Bardzo niebezpieczne dla podtypów jest drastyczne definiowanie kontraktów typu super (Set vs. SortedSet jest powitanie). powinno być więc zabronione również w super typach, wykonywanie takiej rekurencji.

 47
Author: Lukas Eder,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-22 09:32:28

To jest bardzo podobne do błędu. Ponieważ, jeśli utworzysz swoją pamięć podręczną o pojemności 32, Twój program będzie działał do 49. I ciekawe, że parametr sizeCtl =32 + (32 >>> 1) + 1) =49! Może być powodem zmiany rozmiaru?

 2
Author: Павел Бивойно,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-03-11 21:53:22