Jakie szczegóły dotyczące implementacji powodują, że kod ten zawodzi tak łatwo?

Question

To pytanie nie dotyczy dobrze znanego i udokumentowanego faktu, że HashMap nie jest bezpieczne dla wątków, ale o jego specyficznych trybach awarii w HotSpot i kodzie JDK. Jestem zaskoczony tym, jak łatwo ten kod nie powiedzie się z 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(); 
} 

nie jest tajemnicą to, gdzie NPE pochodzi z: w etapie .map(m::get) podczas próby unbox się null. Zawodzi w około 4 na 5 serii.

Na moim komputerze Runtime#availableProcessors() raporty 8, więc przypuszczalnie zakres długości 5 jest podzielony na 5 podzadań, z których każdy ma tylko jeden element. Zakładam również, że mój kod działa w trybie interpretacji. Może to być wywołanie metodami JIT-kompilowanymi HashMap lub Stream, ale najwyższy poziom jest interpretowany, co wyklucza wszelkie warianty, w których stan HashMap jest ładowany do pamięci lokalnej wątku (rejestry/stos), co opóźnia obserwację aktualizacji przez inny wątek. Jeśli niektóre z pięciu operacji nie wykonują dosłownie w tym samym czasie na różnych rdzeniach, nie oczekuję, że to zniszczy wewnętrzną strukturę. Czas wykonania poszczególnych zadań musi być niezwykle precyzyjny, biorąc pod uwagę niewielką ilość pracy.

Czy to naprawdę dokładne wyczucie czasu (wątki commonPool muszą zostać odznaczone), czy istnieje inna droga, aby spowodować niepowodzenie na Oracle/OpenJDK HotSpot? Moja obecna wersja jest

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: Uważam, że nawet co tylko dwa wstawki ma podobnie wysoką awaryjność:

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

Answer 1

Po pierwsze, to nie jest zepsuty niezawodnie. Udało mi się wykonać kilka uruchomień bez żadnego wyjątku. To jednak nie oznacza, że ​​wynikowa mapa jest prawidłowa. Możliwe jest również, że każda nić świadczy o pomyślnym umieszczeniu własnej wartości, a wynikowa mapa pomija kilka mapowań.

Rzeczywiście, nieudana próba z NullPointerException zdarza się dość często. I stworzył poniższy kod diagnostyczny do zilustrowania HashMap „s pracy:

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

Stosując to z prostego sekwencyjnego for(int i=0; i<5; i++) debugPut(m, i, i); drukowanej:

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 

Jak widać, z powodu początkowej pojemności 0, istnieją trzy różne tablice podkładowe utworzone nawet podczas operacji sekwencyjnej. Za każdym razem, gdy pojemność jest zwiększana, istnieje większa szansa, że ​​niezręczny współbieżny put pominie aktualizację tablicy i utworzy własną tablicę.

Jest to szczególnie istotne w początkowym stanie pustej mapy i kilku wątków próbujących umieścić swój pierwszy klucz, ponieważ wszystkie wątki mogą napotkać początkowy stan tabeli null i utworzyć własne. Ponadto, nawet podczas odczytu stanu ukończonego pierwszego put, jest również nowa tablica utworzona dla drugiego put.

Ale krok po kroku debugowania ujawniła jeszcze więcej szans na łamanie:

Inside the method putVal widzimy na koniec:

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

Innymi słowy, po pomyślne Wstawienie nowy klucz, tabela zostanie zmieniona, jeśli nowy rozmiar przekroczy threshold. Tak więc na pierwszym put, resize() jest nazywany na początku, ponieważ tabela jest null a ponieważ Twój określona początkowa pojemność jest 0, czyli zbyt niskie, aby zapisać jedno mapowanie, nowa pojemność będzie 1 i nowy threshold będzie 1 * loadFactor == 1 * 0.75f == 0.75f, w zaokrągleniu do 0. Tak więc na samym końcu pierwszego put, nowy threshold został przekroczony i uruchomiono inną operację resize(). Tak więc z początkową wydajnością 0, pierwszy put już tworzy i zapełnia dwie tablice, co daje znacznie większe szanse na zerwanie, jeśli wiele wątków wykonuje tę akcję jednocześnie, wszystkie napotykają stan początkowy.

I jest jeszcze jeden punkt. Patrząc into the resize() operation widzimy 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) 

Innymi słowy, nowa referencja tablica jest przechowywana w stercie przed została wypełniona starych wpisów, więc nawet bez zmiany kolejności czyta i pisze, jest szansa, że ​​inny wątek odczyta to odwołanie, nie widząc starych wpisów, w tym tego, który sam napisał wcześniej. W rzeczywistości optymalizacje zmniejszające dostęp do sterty mogą obniżyć szanse na to, że wątek nie zobaczy własnej aktualizacji w następnym zapytaniu.

Należy jednak zauważyć, że założenie, że wszystko działa interpretowane tutaj, nie jest uzasadnione. Od HashMap również wewnętrznie używany JRE, nawet przed uruchomieniem aplikacji, istnieje również możliwość napotkania już skompilowanego kodu podczas korzystania z HashMap.