Biorąc pod uwagę, że HashMapy w jdk1.6 i nowszych powodują problemy z wielowątkowością, jak mam naprawić mój kod

Niedawno zadałem pytanie w stackoverflow, a potem znalazłem odpowiedź. Początkowe pytanie brzmiało: Jakie mechanizmy inne niż muteksy lub czyszczenie pamięci mogą spowolnić mój wielowątkowy program Java?

Ku mojemu przerażeniu odkryłem, że HashMap został zmodyfikowany między JDK1.6 a JDK1.7. Ma teraz blok kodu, który powoduje synchronizację wszystkich wątków tworzących HashMaps.

Wiersz kodu w JDK1.7.0_10 to

 /**A randomizing value associated with this instance that is applied to hash code of  keys to make hash collisions harder to find.     */
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);

Co kończy się dzwonieniem

 protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
 }    

Patrząc na inne zestawy JDK, stwierdzam, że nie ma tego w JDK1.5.0_22 lub JDK1.6.0_26.

Wpływ na mój kod jest ogromny. To sprawia, że ​​gdy uruchamiam się na 64 wątkach, uzyskuję mniejszą wydajność niż podczas uruchamiania na 1 wątku. JStack pokazuje, że większość wątków spędza większość czasu w tej pętli w trybie Random.

Więc wydaje mi się, że mam kilka opcji:

• Przepisz mój kod, abym nie używał HashMap, ale użyj czegoś podobnego
• Jakoś pomieszaj z rt.jar i wymień hashmap w nim
• Zepsuć w jakiś sposób ścieżkę klasy, więc każdy wątek otrzymuje własną wersję HashMap

Zanim rozpocznę którąkolwiek z tych ścieżek (wszystkie wyglądają na bardzo czasochłonne i potencjalnie duże), zastanawiałem się, czy nie przegapiłem oczywistej sztuczki. Czy ktoś z was może zasugerować, która z przepełnionych stosów jest lepszą ścieżką, lub może zidentyfikować nowy pomysł.

Dzięki za pomoc

Jestem oryginalnym autorem poprawki, która pojawiła się w 7u6, CR # 7118743: Alternatywne haszowanie ciągów znaków z mapami opartymi na skrótach‌.

Od razu przyznaję, że inicjalizacja hashSeed jest wąskim gardłem, ale nie jest to problem, który spodziewaliśmy się, ponieważ dzieje się to tylko raz na instancję Hash Map. Aby ten kod był wąskim gardłem, musiałbyś tworzyć setki lub tysiące map skrótów na sekundę. To z pewnością nie jest typowe. Czy naprawdę istnieje uzasadniony powód, dla którego Twoja aplikacja to robi? Jak długo działają te mapy skrótów?

Niezależnie od tego, prawdopodobnie zbadamy przejście na ThreadLocalRandom zamiast Random i prawdopodobnie jakiś wariant leniwej inicjalizacji, jak sugeruje cambecc.

EDYCJA 3

Poprawka dotycząca wąskiego gardła została wprowadzona do repozytorium Mercurial repo aktualizacji JDK7:

http://hg.openjdk.java.net/jdk7u/jdk7u-dev/jdk/rev/b03bbdef3a88

Poprawka będzie częścią nadchodzącej wersji 7u40 i jest już dostępna w wydaniach IcedTea 2.4.

Niemal ostateczne wersje testowe 7u40 są dostępne tutaj:

https://jdk7.java.net/download.html

Opinie są nadal mile widziane. Wyślij go na http://mail.openjdk.java.net/mailman/listinfo/core-libs-dev, aby mieć pewność, że zostanie on zauważony przez deweloperów openJDK.

To wygląda na „błąd”, który można obejść. Istnieje właściwość, która wyłącza nową funkcję „alternatywnego mieszania”:

jdk.map.althashing.threshold = -1

Jednak wyłączenie alternatywnego haszowania nie jest wystarczające, ponieważ nie wyłącza generowania losowego ziarenka skrótu (choć naprawdę powinno). Więc nawet jeśli wyłączysz alt haszowanie, nadal masz rywalizację wątków podczas tworzenia instancji mapy skrótów.

Jednym ze szczególnie nieprzyjemnych sposobów obejścia tego problemu jest wymuszone zastąpienie wystąpienia Randomużywanego do generowania zarodka skrótu własną niezsynchronizowaną wersją:

// Create an instance of "Random" having no thread synchronization.
Random alwaysOne = new Random() {
    @Override
    protected int next(int bits) {
        return 1;
    }
};

// Get a handle to the static final field sun.misc.Hashing.Holder.SEED_MAKER
Class<?> clazz = Class.forName("sun.misc.Hashing$Holder");
Field field = clazz.getDeclaredField("SEED_MAKER");
field.setAccessible(true);

// Convince Java the field is not final.
Field modifiers = Field.class.getDeclaredField("modifiers");
modifiers.setAccessible(true);
modifiers.setInt(field, field.getModifiers() & ~Modifier.FINAL);

// Set our custom instance of Random into the field.
field.set(null, alwaysOne);

Dlaczego (prawdopodobnie) jest to bezpieczne? Ponieważ alt haszowanie zostało wyłączone, powodując ignorowanie losowych nasion mieszania. Nie ma więc znaczenia, że ​​nasze wystąpienie Randomnie jest w rzeczywistości przypadkowe. Jak zawsze w przypadku takich paskudnych hacków, należy zachować ostrożność.

(Podziękowania dla https://stackoverflow.com/a/3301720/1899721 za kod ustawiający statyczne pola końcowe).

--- Edytować ---

FWIW, następująca zmiana w celu HashMapwyeliminowania rywalizacji o wątki, gdy funkcja skrótu alt jest wyłączona:

-   transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+   transient final int hashSeed;

...

         useAltHashing = sun.misc.VM.isBooted() &&
                 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+        hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0;
         init();

Podobne podejście można zastosować do ConcurrentHashMapitp.

Istnieje wiele aplikacji, które tworzą przejściową HashMap na rekord w aplikacjach Big Data. Na przykład te parsery i serializatory. Umieszczenie jakiejkolwiek synchronizacji w niezsynchronizowanych klasach kolekcji to prawdziwy problem. Moim zdaniem jest to niedopuszczalne i należy to naprawić jak najszybciej. Zmiana, która najwyraźniej została wprowadzona w 7u6, CR # 7118743, powinna zostać cofnięta lub naprawiona bez konieczności synchronizacji lub operacji atomowej.

W jakiś sposób przypomina mi to kolosalny błąd synchronizacji StringBuffer i Vector oraz HashTable w JDK 1.1 / 1.2. Ludzie drogo płacili za ten błąd przez lata. Nie ma potrzeby powtarzania tego doświadczenia.

Zakładając, że twój wzorzec użycia jest rozsądny, będziesz chciał użyć własnej wersji Hashmap.

Ten fragment kodu sprawia, że ​​kolizje skrótów są znacznie trudniejsze do wywołania, uniemożliwiając atakującym tworzenie problemów z wydajnością ( szczegóły ) - zakładając, że problem został już rozwiązany w inny sposób, nie sądzę, aby w ogóle potrzebna była synchronizacja. Jednak nie ma znaczenia, czy używasz synchronizacji, czy nie, wydaje się, że chciałbyś użyć własnej wersji Hashmap, aby nie polegać tak bardzo na tym, co dostarcza JDK.

Więc albo po prostu piszesz coś podobnego i wskazujesz na to, albo nadpisujesz klasę w JDK. Aby to zrobić, możesz zastąpić ścieżkę klasy bootstrap -Xbootclasspath/p:parametrem. Takie postępowanie będzie jednak „sprzeczne z licencją na kod binarny Java 2 Runtime Environment” ( źródło ).