Welches Implementierungsdetail lässt diesen Code so einfach ausfallen?

Question

Bei dieser Frage geht es nicht um die bekannte und dokumentierte Tatsache, dass HashMap nicht Thread-sicher ist, sondern über seine spezifischen Fehlermodi auf HotSpot- und JDK-Code. Ich bin überrascht, wie leicht dieser Code nicht mit einem NPE:

public static void main(String[] args) { 
    Map<Integer, Integer> m = new HashMap<>(0, 0.75f); 
    IntStream.range(0, 5).parallel().peek(i -> m.put(i, i)).map(m::get).count(); 
} 

Es ist kein Geheimnis, wo der NPE kommt: in dem .map(m::get) Schritt bei dem Versuch, ein null unbox. Es schlägt in etwa 4 von 5 Läufen fehl.

Auf meinem Rechner Runtime#availableProcessors() meldet 8, also ist vermutlich der Bereich der Länge 5 in 5 Teilaufgaben aufgeteilt, jede mit nur einem einzigen Element. Ich nehme auch an, dass mein Code im interpretierten Modus ausgeführt wird. Es kann in JIT-kompilierte HashMap oder Stream Methoden aufgerufen werden, aber die oberste Ebene wird interpretiert und daher alle Variationen ausgeschlossen, wobei HashMap State in thread-lokalen Speicher (Register/Stack) geladen wird, wodurch die Beobachtung von Updates durch einen anderen Thread verzögert. Wenn einige der fünf put-Operationen nicht wörtlich während derselben Zeit auf verschiedenen Kernen ausgeführt werden, erwarte ich nicht, dass es die interne Struktur HashMap zerstört. Das Timing der einzelnen Aufgaben muss angesichts des geringen Arbeitsaufwands äußerst präzise sein.

Ist es wirklich das genaue Timing (commonPool Threads müssen entparkt werden), oder gibt es eine andere Route, um dies auf Oracle/OpenJDK HotSpot scheitern zu lassen? Meine aktuelle Version ist

java version "1.8.0_72" 
Java(TM) SE Runtime Environment (build 1.8.0_72-b15) 
Java HotSpot(TM) 64-Bit Server VM (build 25.72-b15, mixed mode) 

UPDATE: Ich finde, dass selbst macht nur zwei Einfügungen eine ähnlich hohe Ausfallrate hat:

IntStream.range(0, 2).parallel().peek(i -> m.put(i, i)).map(m::get).count(); 

Answer 1

Erstens, es ist nicht zuverlässig ausfällt. Ich habe es geschafft, einige Runs zu haben, bei denen keine Ausnahme aufgetreten ist. Dies bedeutet jedoch nicht, dass die resultierende Karte korrekt ist. Es ist auch möglich, dass jeder Thread seinen eigenen Wert erfolgreich platziert, während die resultierende Map mehrere Zuordnungen verpasst.

Aber in der Tat passiert oft mit einer NullPointerException scheitern. Ich habe den folgenden Debug-Code die HashMap ‚s Arbeiten zu veranschaulichen:

static <K,V> void debugPut(HashMap<K,V> m, K k, V v) { 
    if(m.isEmpty()) debug(m); 
    m.put(k, v); 
    debug(m); 
} 
private static <K, V> void debug(HashMap<K, V> m) { 
    for(Field f: FIELDS) try { 
     System.out.println(f.getName()+": "+f.get(m)); 
    } catch(ReflectiveOperationException ex) { 
     throw new AssertionError(ex); 
    } 
    System.out.println(); 
} 
static final Field[] FIELDS; 
static { 
    String[] name={ "table", "size", "threshold" }; 
    Field[] f=new Field[name.length]; 
    for (int ix = 0; ix < name.length; ix++) try { 
     f[ix]=HashMap.class.getDeclaredField(name[ix]); 
    } 
    catch (NoSuchFieldException ex) { 
     throw new ExceptionInInitializerError(ex); 
    } 
    AccessibleObject.setAccessible(f, true); 
    FIELDS=f; 
} 

Mit diesem mit den einfachen sequentiellen for(int i=0; i<5; i++) debugPut(m, i, i); gedruckt:

table: null 
size: 0 
threshold: 1 

table: [Ljava.util.HashMap$Node;@70dea4e 
size: 1 
threshold: 1 

table: [Ljava.util.HashMap$Node;@5c647e05 
size: 2 
threshold: 3 

table: [Ljava.util.HashMap$Node;@5c647e05 
size: 3 
threshold: 3 

table: [Ljava.util.HashMap$Node;@33909752 
size: 4 
threshold: 6 

table: [Ljava.util.HashMap$Node;@33909752 
size: 5 
threshold: 6 

Wie Sie sehen können, aufgrund der Anfangskapazität von 0, Es gibt drei verschiedene Backing-Arrays, die sogar während der sequentiellen Operation erstellt wurden. Jedes Mal, wenn die Kapazität erhöht wird, besteht eine höhere Wahrscheinlichkeit, dass ein rassiger gleichzeitiger put das Array-Update verpasst und ein eigenes Array erstellt.

Dies ist besonders relevant für den Anfangszustand einer leeren Karte und mehr Threads versuchen, ihren ersten Schlüssel zu setzen, da alle Threads könnten den Ausgangszustand eine null Tabelle begegnen und ihre eigene Gruppe gründen. Auch beim Lesen des Status einer abgeschlossenen ersten put wird ein neues Array für die zweite put erstellt.

Aber Schritt-für-Schritt Debuggen noch mehr Chancen zu brechen offenbart:

Inside the method putVal sehen wir am Ende:

++modCount; 
if (++size > threshold) 
    resize(); 
afterNodeInsertion(evict); 
return null; 

Mit anderen Worten, nach die erfolgreiche Einführung von Wenn die neue Größe den Wert threshold überschreitet, wird die Größe der Tabelle geändert. So auf den ersten put, resize() am Anfang genannt wird, da die Tabelle null ist und seit Ihrer angegebene Anfangskapazität 0 ist, dh zu niedrig ein Mapping zu speichern, wird die neue Kapazität 1 und die neuen threshold werden 1 * loadFactor == 1 * 0.75f == 0.75f sein, aufgerundet auf 0. Also genau am Ende der ersten put wird die neue threshold überschritten und ein weiterer resize() Betrieb ausgelöst. Also mit einer anfänglichen Kapazität von 0, die erste put bereits erstellt und bevölkert zwei Arrays, die viel höhere Chancen zu brechen gibt, wenn mehrere Threads diese Aktion gleichzeitig durchführen, alle auf den Ausgangszustand.

Und es gibt einen anderen Punkt. Suchen into the resize() operation wir sehen the lines:

@SuppressWarnings({"rawtypes","unchecked"}) 
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 
table = newTab; 
if (oldTab != null) { 
    … (transfer old contents to new array) 

Mit anderen Worten, wird das neue Array-Referenz in den Heap gespeichert vor es mit den alten Einträgen gefüllt wurde, so dass auch ohne von liest Neuordnen und schreibt, es ist ein Chance, dass ein anderer Thread diese Referenz liest, ohne die alten Einträge zu sehen, einschließlich desjenigen, den er zuvor selbst geschrieben hat. Tatsächlich können Optimierungen, die den Heap-Zugriff reduzieren, die Wahrscheinlichkeit verringern, dass ein Thread seine eigene Aktualisierung in einer unmittelbar folgenden Abfrage nicht sieht.

Trotzdem muss es auch angemerkt werden, dass die Annahme, dass alles hier interpretiert interpretiert wird, nicht begründet ist. Da HashMap auch von der JRE intern verwendet wird, besteht bereits vor dem Starten der Anwendung die Möglichkeit, bereits kompilierten Code zu finden, wenn Sie HashMap verwenden.