Rekursive ConcurrentHashMap.computeIfAbsent () - Aufruf nie beendet. Bug oder "feature"?

Einige Zeit her, Gebloggt habe ich über einen Java 8 funktionale Art und Weise der Berechnung der fibonacci-zahlen rekursiv, mit einem ConcurrentHashMap cache und die neue, nützliche computeIfAbsent() Methode:

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

Wählte ich ConcurrentHashMap weil ich dachte, dieses Beispiel noch raffinierter durch die Einführung von Parallelität (was ich nicht am Ende).

Nun vergrößern wir die Anzahl von 8 zu 25 und beobachten, was passiert:

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

Das Programm nie unterbrochen. Innerhalb der Methode gibt es eine Schleife, die läuft einfach immer:

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

Ich bin mit:

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 von diesem blog-post auch bestätigt das Problem (er fand es sogar).

Dies ist seltsam. Ich hätte erwartet, dass eine der folgenden zwei:

  • Es funktioniert
  • Es wirft ein ConcurrentModificationException

Aber eben nie aufzuhalten? Das scheint gefährlich. Ist es ein bug? Oder habe ich missverstanden, einige Vertrag?

InformationsquelleAutor Lukas Eder | 2015-03-03
  1. 51

    Dies ist fest in JDK-8062841.

    In der Vorschlag von 2011, identifizierte ich dieses Problem bei der code-überprüfung. Die JavaDoc aktualisiert wurde und ein temporärer fix wurde Hinzugefügt. Es wurde entfernt, in einer weiteren rewrite-aufgrund der performance-Probleme.

    In der 2014-Diskussion, wir erkunden Wege, um besser zu erkennen und scheitern. Beachten Sie, dass einige der Diskussion wurde offline genommen, um private E-Mail für die Prüfung der low-level-änderungen. Während nicht jeder Fall abgedeckt werden kann, die in häufigen Fällen nicht livelock. Diese behebt sind in Doug ' s repository, aber haben es nicht geschafft in das JDK-release.

    • Sehr interessant, vielen Dank für das teilen! Mein Bericht wurde auch akzeptiert als JDK-8074374
    • sorry für offtop, aber ich bin wirklich überrascht, wie niedrig, SO dass Bewertung, die Sie haben, trotz der so bedeutenden Beitrag in der knowledge base über so komplizierte Sache wie lock-freien (und in der Nähe der lock-free) Parallelität.
    • Danke. Ich bieten oft eine schnelle Antwort in den Kommentaren statt einen verbringen die Zeit auf eine längere, ausführliche Antwort. Kommentar erreicht souverän nicht zur Erhöhung der reputation, obwohl. Ich habe wahrscheinlich weniger als der Durchschnitt Interesse verfolgen rep, obwohl.
    • nicht ganz behoben: boom
    • schönen Fang! Es sieht aus wie die gleiche Behauptung angewendet werden konnte transfer und es war eine verpasste Fall. Können Sie E-Mail - [email protected] um Doug ' s Aufmerksamkeit?
    • klar, kein prob. Ich fand das nach der Integration von Koffein in meinem cache-backend, wo sich der cache loader können rekursiv sein. Mein Erster Versuch dies zu beheben, war, den cache setzen der anfänglichen Kapazität der cache-Größe. Dies behebt die meisten der Probleme, einschließlich der Tests, die ich im Zusammenhang mit oben, aber ich fürchte, es gibt noch mehr vergessene Fällen über, dass man. Ich werde versuchen, Sie zu isolieren und bieten schmalen tests.
    • Eine hässliche, aber umgehen Koffein ist die Verwendung AsyncLoadingCache so dass die Berechnungen durchgeführt werden, die außerhalb der Karte operation (auf die Zukunft), wahlweise mit der synchronous() anzeigen.
    • danke für die Anregung. Ich habe gegriffen, um mit einem Cache anstatt von einem LoadingCache, wo meine Fassade Klasse schließt den Cache und die CacheLoader, seine get () - Methode Delegierten zu Cache#getIfPresent() / put () Aufruf der CacheLoader, wenn nötig. zucken

    InformationsquelleAutor Ben Manes
  2. 53

    Dies ist natürlich eine "feature". Die ConcurrentHashMap.computeIfAbsent() Javadoc liest:

    Wenn der angegebene Schlüssel nicht bereits im Zusammenhang mit einem Wert, versucht zu berechnen, dessen Wert mit dem angegebenen mapping-Funktion und gibt Sie in dieser Karte, sofern nicht null. Der gesamte Methodenaufruf erfolgt atomar, so wird die Funktion angewendet wird höchstens einmal pro Schlüssel. Einige versuchten update-Operationen auf dieser Karte durch andere threads gesperrt werden kann, während die Berechnung läuft, also die Berechnung sollte kurz und einfach sein, und darf nicht versuchen, aktualisieren Sie alle anderen Zuordnungen, die von dieser Karte.

    Den "muss nicht" Formulierung ist eine klare Vereinbarung, die mein Algorithmus verletzt, zwar nicht für die gleiche Parallelität Gründen.

    Was noch interessant ist, dass es keine ConcurrentModificationException. Stattdessen wird das Programm nur nie die halte - was immer noch ein ziemlich gefährlicher Fehler meiner Meinung nach (d.h. Endlosschleifen. oder: alles kann schief gehen, tut).

    Hinweis:

    Den HashMap.computeIfAbsent() oder Gekennzeichnet.computeIfAbsent() Javadoc nicht verbieten, eine solche rekursive Berechnung, was natürlich lächerlich ist, wie die Art des Caches ist Map<Integer, Integer>, nicht ConcurrentHashMap<Integer, Integer>. Es ist sehr gefährlich für die Subtypen drastisch zu re-definieren super Typ Verträgen (Set vs. SortedSet ist Gruß). Sollte es daher verboten werden, auch in super-Typen, führen solche Rekursion.

    • Gute zu finden. Ich würde vorschlagen, einen bug-report/RFE gegen JDK.
    • Fertig, mal sehen, ob es angenommen wird... ich werde zu aktualisieren, mit einem link, wenn es ist.
    • Es scheint mir, dass diese Art der rekursiven Modifikation anderer Zuordnungen ist nicht erlaubt in ConcurrentHashMap weil der andere wichtige Bestandteil seines Vertrags: "Das gesamte Methodenaufruf erfolgt atomar, so wird die Funktion angewendet wird höchstens einmal pro Schlüssel." Es ist wahrscheinlich, dass Sie Ihr Programm, indem Sie die Verletzung der "keine rekursiven modifiction" Vertrag, der versucht, eine Sperre erwerben, die es bereits hält, und ist Deadlock-mit sich selbst, nicht läuft in einer Endlosschleife.
    • Aus der JavaDoc: IllegalStateException - if the computation detectably attempts a recursive update to this map that would otherwise never complete
    • Das ist eher implizit. Die Methode invocation konnte noch durchgeführt werden atomar und update keys mehrere. Obwohl, dass würde wahrscheinlich nicht eine gute Idee sein, eine gleichzeitige Kontext, weil der deadlock-potential.
    • Der Bericht akzeptiert wurde als JDK-8074374. Es ist wohl ein Duplikat von JDK-8062841, wie die Ben Manes
    • es scheint mir, dass wenn Aufruf ist, bleiben Atom-und immer noch in der Lage sein zu aktualisieren, mehrere Schlüssel, als wohl alle Teile der Karte würde gesperrt werden müssen
    • Meiner Meinung nach, dass sollte in Ordnung sein. Natürlich, es führen könnte, zu einem dead-lock, das wäre ebenso schlecht, wie eine nicht-terminierende Schleife
    • Sie empfehlen HashMap, ist die put-Methode auf HashMap thread-safe? so ist es garantiert nicht zu einer Beschädigung der Karte Stand, wenn Sie angerufen werden gleichzeitig von mehreren threads? mit beschädigt meine ich, dass man ein "lost update" oder eine Ausnahme auf setzen. Das ist auch ok so, wenn zwei threads berechnen den gleichen Wert und nur einer setzen-operation der solche threads eigentlich ist die Aktualisierung der Karte (zum Beispiel last one wins)
    • Siehe die ursprüngliche Frage. In diesem Fall hat der Algorithmus ist single-threaded.
    • auch mit HashMap es ist nicht OK. bugs.openjdk.java.net/browse/JDK-8172951
    • Danke, ich habe entfernt die Bemerkung.
    • das ist gut, aber ich denke, deine Letzte "Bemerkung" könnten noch verstanden werden als "... aber für HashMap es funktioniert". Wir formulieren es so: "obwohl Map javadocs nicht explizit verbieten, dass die Funktion sollte nicht ändern Sie die Karte in irgendeiner Weise"
    • Wollen Sie mich hinzufügen, dass einige interrobang nach dem letzten Satz in Fettschrift? 🙂

    InformationsquelleAutor Lukas Eder
  3. 4

    Dies ist sehr ähnlich zu dem Fehler.
    Weil, wenn Sie erstellen Sie Ihre cache mit einer Kapazität 32, funktioniert zwar das Programm, bis 49.
    Und es ist interessant, dass der parameter sizeCtl =32 + (32 >>> 1) + 1) =49!
    Kann der Grund in der Größenänderung?

    • Ich habe keine Zeit zu Graben, durch den source-code, aber ich denke, dass Sie Recht haben. Wir schlagen dies in der Produktion, ständig. Sobald wir erhöhten die CHM anfänglichen Kapazität zu einer sehr hohen Zahl, das ging Weg. Bis wir überarbeiten unseren code, das ist, was wir tun...
    InformationsquelleAutor Павел Бивойно
Schreibe einen Kommentar