Vor einiger Zeit habe ich über eine Java 8-Methode zur rekursiven Berechnung von Fibonacci-Zahlen mit einem ConcurrentHashMap
Cache 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, ConcurrentHashMap
weil 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 8
bis 25
und 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?
quelle
transfer
und es war ein verpasster Fall. Können Sie eine E-Mail senden[email protected]
, um Dougs Aufmerksamkeit zu erregen?Dies ist natürlich eine "Funktion" . Der
ConcurrentHashMap.computeIfAbsent()
Javadoc liest: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()
oderMap.computeIfAbsent()
Javadoc verbieten solche rekursiven Berechnungen nicht, was natürlich lächerlich ist, wie es der Typ des Caches istMap<Integer, Integer>
, nichtConcurrentHashMap<Integer, Integer>
. Für Subtypen ist es sehr gefährlich, Super-Typ-Verträge drastisch neu zu definieren (Set
vs.SortedSet
Begrüßung). Es sollte daher auch bei Supertypen verboten sein, eine solche Rekursion durchzuführen.quelle
ConcurrentHashMap
aufgrund 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.IllegalStateException - if the computation detectably attempts a recursive update to this map that would otherwise never complete
HashMap
es nicht OK ist. bugs.openjdk.java.net/browse/JDK-8172951Dies 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
CHM
anfängliche Kapazität auf einen sehr hohen Wert erhöht hatten, verschwand dies. Bis wir unseren Code