Der rekursive ConcurrentHashMap.computeIfAbsent () -Aufruf wird niemals beendet. Fehler oder "Feature"?

76

Vor einiger Zeit habe ich über eine Java 8-Methode zur rekursiven Berechnung von Fibonacci-Zahlen mit einem ConcurrentHashMapCache und der neuen, nützlichen computeIfAbsent()Methode gebloggt :

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

Ich habe mich entschieden, ConcurrentHashMapweil ich daran gedacht habe, dieses Beispiel durch die Einführung von Parallelität (was ich am Ende nicht getan habe) noch komplexer zu machen.

Erhöhen wir nun die Anzahl von 8bis 25und beobachten, was passiert:

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

Das Programm wird nie angehalten. Innerhalb der Methode gibt es eine Schleife, die einfach für immer läuft:

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

Ich benutze:

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, ein Leser dieses Blogposts, bestätigte das Problem ebenfalls (er fand es tatsächlich) .

Das ist komisch. Ich hätte eine der folgenden beiden erwartet:

  • Es klappt
  • Es wirft ein ConcurrentModificationException

Aber einfach nie aufhören? Das scheint gefährlich. Ist es ein Fehler? Oder habe ich einen Vertrag falsch verstanden?

Lukas Eder
quelle

Antworten:

58

Dies ist in JDK-8062841 behoben .

Im Vorschlag von 2011 habe ich dieses Problem während der Codeüberprüfung festgestellt. Das JavaDoc wurde aktualisiert und ein temporärer Fix wurde hinzugefügt. Es wurde aufgrund von Leistungsproblemen in einem weiteren Umschreiben entfernt.

In der Diskussion von 2014 haben wir nach Wegen gesucht, um besser zu erkennen und zu scheitern. Beachten Sie, dass ein Teil der Diskussion offline in private E-Mails verschoben wurde, um die Änderungen auf niedriger Ebene zu berücksichtigen. Obwohl nicht jeder Fall abgedeckt werden kann, werden die häufigsten Fälle nicht leben. Diese Korrekturen befinden sich im Repository von Doug, haben es jedoch nicht in eine JDK-Version geschafft.

Ben Manes
quelle
5
Sehr interessant, danke fürs Teilen! Mein Bericht wurde auch als JDK-8074374
Lukas Eder
1
@Ben Entschuldigung für offtop, aber ich bin wirklich überrascht, wie niedrig die SO-Bewertung ist, obwohl Sie einen so bedeutenden Beitrag zur Wissensbasis in Bezug auf so komplizierte Dinge wie sperrenfreie (und nahezu sperrenfreie) Parallelität leisten.
Alex Salauyou
@ SashaSalauyou Danke. Ich gebe oft eine schnelle Antwort in Kommentaren, anstatt die Zeit für eine längere, vollständige Antwort aufzuwenden. Kommentar-Scores erhöhen jedoch nicht die Reputation. Ich habe wahrscheinlich ein unterdurchschnittliches Interesse daran, Repräsentanten zu jagen.
Ben Manes
@ Ben nicht ganz behoben: Boom
Scott
@ ScottMcKinney schöner Fang! Es sieht so aus, als könnte dieselbe Behauptung angewendet werden, transferund es war ein verpasster Fall. Können Sie eine E-Mail senden [email protected], um Dougs Aufmerksamkeit zu erregen?
Ben Manes
56

Dies ist natürlich eine "Funktion" . Der ConcurrentHashMap.computeIfAbsent()Javadoc liest:

Wenn der angegebene Schlüssel noch keinem Wert zugeordnet ist, wird versucht, seinen Wert mithilfe der angegebenen Zuordnungsfunktion zu berechnen, und er wird in diese Zuordnung eingegeben, sofern nicht null. Der gesamte Methodenaufruf wird atomar ausgeführt, sodass die Funktion höchstens einmal pro Schlüssel angewendet wird. Einige versuchte Aktualisierungsvorgänge auf dieser Karte durch andere Threads werden möglicherweise während der Berechnung blockiert. Daher sollte die Berechnung kurz und einfach sein und darf nicht versuchen, andere Zuordnungen dieser Karte zu aktualisieren .

Der Wortlaut "darf nicht" ist ein klarer Vertrag, gegen den mein Algorithmus verstoßen hat, allerdings nicht aus den gleichen Gründen der Parallelität.

Interessant ist immer noch, dass es keine gibt ConcurrentModificationException. Stattdessen wird das Programm einfach nie angehalten - was meiner Meinung nach immer noch ein ziemlich gefährlicher Fehler ist (dh Endlosschleifen oder: alles, was möglicherweise schief gehen kann, tut es ).

Hinweis:

Die HashMap.computeIfAbsent()oder Map.computeIfAbsent()Javadoc verbieten solche rekursiven Berechnungen nicht, was natürlich lächerlich ist, wie es der Typ des Caches ist Map<Integer, Integer>, nicht ConcurrentHashMap<Integer, Integer>. Für Subtypen ist es sehr gefährlich, Super-Typ-Verträge drastisch neu zu definieren ( Setvs. SortedSetBegrüßung). Es sollte daher auch bei Supertypen verboten sein, eine solche Rekursion durchzuführen.

Lukas Eder
quelle
3
Guter Fund. Ich würde einen Fehlerbericht / RFE gegen JDK vorschlagen.
Axel
4
Fertig, mal sehen, ob es akzeptiert wird ... Ich werde mit einem Link aktualisieren, wenn es ist.
Lukas Eder
3
Es scheint mir wahrscheinlich, dass diese Art der rekursiven Änderung anderer Zuordnungen ConcurrentHashMapaufgrund des anderen wichtigen Teils des Vertrags nicht zulässig ist : " Der gesamte Methodenaufruf wird atomar ausgeführt, sodass die Funktion höchstens einmal pro Schlüssel angewendet wird. " Es ist wahrscheinlich, dass Ihr Programm durch einen Verstoß gegen den Vertrag "Keine rekursive Änderung" versucht, eine Sperre zu erlangen, die es bereits besitzt, und mit sich selbst festsitzt und nicht in einer Endlosschleife läuft.
Murgatroid99
3
Aus dem JavaDoc:IllegalStateException - if the computation detectably attempts a recursive update to this map that would otherwise never complete
Ben Manes
2
@LukasEder auch wenn HashMapes nicht OK ist. bugs.openjdk.java.net/browse/JDK-8172951
Piotr Findeisen
4

Dies ist dem Fehler sehr ähnlich. Denn wenn Sie Ihren Cache mit der Kapazität 32 erstellen, funktioniert Ihr Programm bis 49. Und es ist interessant, dass der Parameter sizeCtl = 32 + (32 >>> 1) + 1) = 49! Kann der Grund für die Größenänderung sein?

Павел Бивойно
quelle
1
Ich habe keine Zeit, den Quellcode zu durchsuchen, aber ich denke, dass Sie Recht haben. Wir treffen dies ständig in der Produktion. Sobald wir die CHManfängliche Kapazität auf einen sehr hohen Wert erhöht hatten, verschwand dies. Bis wir unseren Code
Eugene