Ich habe etwas Seltsames bei der Implementierung von bemerkt HashMap.clear(). So sah es in OpenJDK 7u40 aus :
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
Und so sieht es ab OpenJDK 8u40 aus :
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
Ich verstehe, dass das jetzt tablefür das Leeren einer Karte null sein kann, daher ist die zusätzliche Überprüfung und Zwischenspeicherung in einer lokalen Variablen erforderlich. Aber warum wurde Arrays.fill()durch eine for-Schleife ersetzt?
Es scheint, dass die Änderung in diesem Commit eingeführt wurde . Leider habe ich keine Erklärung dafür gefunden, warum eine Plain-for-Schleife besser sein könnte als Arrays.fill(). Ist es schneller Oder sicherer?
fillAnruf nicht inline undtabkurz ist. Unter HotSpot führen sowohl die Schleife als auch der explizitefillAufruf zu einem schnellen Compiler (in einem Happy-Day-Szenario).java.util.Arraysals Nebeneffekt dieser Methode geladen wird. Für Anwendungscode ist dies normalerweise kein Problem.Antworten:
Ich werde versuchen, drei mehr als vernünftige Versionen zusammenzufassen, die in Kommentaren vorgeschlagen wurden.
@ Holger sagt :
Dies ist am einfachsten zu testen. Lassen Sie uns ein solches Programm kompilieren:
public class HashMapTest { public static void main(String[] args) { new java.util.HashMap(); } }Führen Sie es mit
java -verbose:class HashMapTest. Dadurch werden die Klassenladeereignisse gedruckt, sobald sie auftreten. Mit JDK 1.8.0_60 werden mehr als 400 Klassen geladen:... 155 lines skipped ... [Loaded java.util.Set from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.AbstractSet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.Collections$EmptySet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.Collections$EmptyList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.Collections$EmptyMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.Collections$UnmodifiableCollection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.Collections$UnmodifiableList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.Collections$UnmodifiableRandomAccessList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded sun.reflect.Reflection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] **[Loaded java.util.HashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.HashMap$Node from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.lang.Class$3 from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.lang.Class$ReflectionData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.lang.Class$Atomic from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded sun.reflect.generics.repository.AbstractRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded sun.reflect.generics.repository.GenericDeclRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded sun.reflect.generics.repository.ClassRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.lang.Class$AnnotationData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded sun.reflect.annotation.AnnotationType from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.util.WeakHashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.lang.ClassValue$ClassValueMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.lang.reflect.Modifier from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded sun.reflect.LangReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] [Loaded java.lang.reflect.ReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] **[Loaded java.util.Arrays from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar] ...Wie Sie sehen können,
HashMapwird lange vor dem AnwendungscodeArraysgeladen und nur 14 Klassen danachHashMap. DasHashMapLaden wird durchsun.reflect.ReflectionInitialisierung ausgelöst, da esHashMapstatische Felder enthält. DieArraysLast wird wahrscheinlich durch dieWeakHashMapLast ausgelöst , die tatsächlichArrays.fillin derclear()Methode vorhanden ist. DieWeakHashMapLast wird ausgelöst, durchjava.lang.ClassValue$ClassValueMapdie sich erstrecktWeakHashMap. DasClassValueMapist in jedemjava.lang.ClassFall vorhanden. Mir scheint also, dassArraysdas JDK ohne Klasse überhaupt nicht initialisiert werden kann. Auch derArraysstatische Initialisierer ist sehr kurz, er initialisiert nur den Assertionsmechanismus. Dieser Mechanismus wird in vielen anderen Klassen verwendet (einschließlich beispielsweisejava.lang.Throwablewelches sehr früh geladen wird). In werden keine weiteren statischen Initialisierungsschritte ausgeführtjava.util.Arrays. Daher scheint mir die @ Holger-Version falsch zu sein.Hier fanden wir auch sehr interessante Sache. Das
WeakHashMap.clear()benutzt nochArrays.fill. Es ist interessant, als es dort erschien, aber leider geht dies in prähistorische Zeiten (es war bereits im allerersten öffentlichen OpenJDK-Repository vorhanden).Als nächstes sagt @MarcoTopolnik :
Es war tatsächlich überraschend für mich, dass
Arrays.filles nicht direkt intrinsisch ist (siehe intrinsische Liste, die von @apangin generiert wurde ). Es scheint, dass eine solche Schleife von JVM ohne explizite intrinsische Behandlung erkannt und vektorisiert werden kann. Es ist also richtig, dass ein zusätzlicher Anruf in ganz bestimmten Fällen nicht eingebunden werden kann (z. B. wenn dasMaxInlineLevelLimit erreicht ist). Auf der anderen Seite ist es eine sehr seltene Situation und es ist nur ein einzelner Anruf, es ist kein Anruf innerhalb der Schleife und es ist ein statischer, kein virtueller / Schnittstellenaufruf, daher könnte die Leistungsverbesserung nur geringfügig und nur in bestimmten Szenarien sein. Nicht das, was die JVM-Entwickler normalerweise interessieren.Es sollte auch beachtet werden, dass sogar der C1-Client-Compiler (Tier 1-3) inline
Arrays.fillaufgerufen werden kann, beispielsweise inWeakHashMap.clear(), wie inlining log (-XX:+UnlockDiagnosticVMOptions -XX:+PrintCompilation -XX:+PrintInlining) sagt:36 3 java.util.WeakHashMap::clear (50 bytes) !m @ 4 java.lang.ref.ReferenceQueue::poll (28 bytes) @ 17 java.lang.ref.ReferenceQueue::reallyPoll (66 bytes) callee is too large @ 28 java.util.Arrays::fill (21 bytes) !m @ 40 java.lang.ref.ReferenceQueue::poll (28 bytes) @ 17 java.lang.ref.ReferenceQueue::reallyPoll (66 bytes) callee is too large @ 1 java.util.AbstractMap::<init> (5 bytes) inline (hot) @ 1 java.lang.Object::<init> (1 bytes) inline (hot) @ 9 java.lang.ref.ReferenceQueue::<init> (27 bytes) inline (hot) @ 1 java.lang.Object::<init> (1 bytes) inline (hot) @ 10 java.lang.ref.ReferenceQueue$Lock::<init> (5 bytes) unloaded signature classes @ 62 java.lang.Float::isNaN (12 bytes) inline (hot) @ 112 java.util.WeakHashMap::newTable (8 bytes) inline (hot)Natürlich kann es auch leicht von einem intelligenten und leistungsstarken C2-Server-Compiler integriert werden. Somit sehe ich hier keine Probleme. Scheint, dass die @ Marco-Version auch falsch ist.
Zum Schluss haben wir noch ein paar Kommentare von @StuartMarks (der JDK-Entwickler ist, also eine offizielle Stimme):
Tatsächlich ist die
HashMap.clear()die Schleife vieler Jahre enthielt, wurde ersetzt mitArrays.fillam 10. April 2013 und blieb weniger ein ein halbes Jahr bis zum 4. September , wenn die diskutiert commit eingeführt wurde. Das besprochene Commit war tatsächlich eine wichtige Neufassung derHashMapInterna, um das JDK-8023463- Problem zu beheben . Es war eine lange Geschichte über die Möglichkeit, dieHashMapmit Schlüsseln zu vergiften, die doppelte Hashcodes haben, wodurch die SuchgeschwindigkeitHashMapauf linear reduziert wird , was sie für DoS-Angriffe anfällig macht. Die Versuche, dies zu lösen, wurden in JDK-7 durchgeführt, einschließlich einer Randomisierung des String-HashCodes. So scheint dasHashMapDie Implementierung wurde aus dem früheren Commit herausgearbeitet, unabhängig entwickelt und dann in den Hauptzweig integriert, wobei mehrere dazwischen eingeführte Änderungen überschrieben wurden.Wir können diese Hypothese unterstützen, indem wir einen Diff durchführen. Nehmen Sie die Version, in
Arrays.fillder sie entfernt wurde (04.09.2013), und vergleichen Sie sie mit der vorherigen Version (30.07.2013). Derdiff -U0Ausgang hat 4341 Zeilen. Lassen Sie uns nun gegen die Version vor einer Version unterscheiden , dieArrays.fillhinzugefügt wurde (2013-04-01).diff -U0Enthält jetzt nur noch 2680 Zeilen. Somit ähnelt die neuere Version tatsächlich eher der älteren als der unmittelbaren Eltern.Fazit
Abschließend würde ich Stuart Marks zustimmen. Es gab keinen konkreten Grund zum Entfernen
Arrays.fill, nur weil die dazwischen liegende Änderung versehentlich überschrieben wurde. Die VerwendungArrays.fillist sowohl im JDK-Code als auch in Benutzeranwendungen vollkommen in Ordnung und wird beispielsweise in verwendetWeakHashMap. DasArraysKlasse wird sowieso ziemlich früh während der JDK-Initialisierung geladen, verfügt über einen sehr einfachen statischen Initialisierer und dieArrays.fillMethode kann auch vom Client-Compiler problemlos integriert werden, sodass kein Leistungsnachteil zu beachten ist.quelle
HashMap.clear(), um den allerersten (JVM-internen) Aufruf abzufangen, und ja, zu diesem Zeitpunktjava.util.Arrayswurde bereits geladen. Für mich hat Stuart Marks die Antwort bereits vor zwei Tagen gegeben. Es gibt tatsächlich die Tendenz, das Gegenteil zu tun, manuelle SchleifenArrays.fillaus guten Gründen durch zu ersetzen, und hier haben wir nur zusammenstoßende Updates. Übrigens.Arrays.fillkönnte intrinsisch werden, so wie esArrays.copyOfbereits ist ...Arrayswird nur dann geladen werden beim Laden ,WeakHashMapwennWeakHashMapeine statische Initialisierung von hatArrays, nur mitArrays.fill()inclearMethode nicht das Laden von auslösenArrays. Ich denke, eine andere Klasse löst die Last von ausArrays.Arrays.fillkönnte schneller sein (wegen der Gründen im Zusammenhang mit Läden von Klassen und Verfahren inlining an anderer Stelle erwähnt), und da die Schleife ganz einfach und klein ist, ging es zu tun.ArraysKlasse ein Initialisierer hinzugefügt wird, der den Call-Stack-Trace aufzeichnet. In der von mir getesteten JDK ist es der Konstruktor,String(char[])der aufruftArrays.copy. Es wurde von angerufensun.nio.cs.FastCharsetProvider, aber ich denke, es gibt viele andere Orte, die es initialisiert haben, wenn dieser Anrufer nicht der erste war ...Arrayses nicht geladen wird,sun.nio.cs.FastCharsetProviderweilArrayses viel vorher geladen wird. Wie pro meinem Wissen wird eine Klasse bald nach der Klasse geladen werden , die es verweist, so von dieser Logik geht,Arrayssoll wegen geladen wurdesun.reflect.misc.ReflectUtiloderjava.util.concurrent.atomic.AtomicReferenceFieldUpdaterweil diese Klassen geladen werden, kurz bevorArraysWeil es viel schneller ist!
Ich habe einige gründliche Benchmarking-Tests für reduzierte Versionen der beiden Methoden durchgeführt:
void jdk7clear() { Arrays.fill(table, null); } void jdk8clear() { Object[] tab; if ((tab = table) != null) { for (int i = 0; i < tab.length; ++i) tab[i] = null; } }Arbeiten an Arrays verschiedener Größen, die zufällige Werte enthalten. Hier sind die (typischen) Ergebnisse:
Map size | JDK 7 (sd)| JDK 8 (sd)| JDK 8 vs 7 16| 2267 (36)| 1521 (22)| 67% 64| 3781 (63)| 1434 ( 8)| 38% 256| 3092 (72)| 1620 (24)| 52% 1024| 4009 (38)| 2182 (19)| 54% 4096| 8622 (11)| 4732 (26)| 55% 16384| 27478 ( 7)| 12186 ( 8)| 44% 65536| 104587 ( 9)| 46158 ( 6)| 44% 262144| 445302 ( 7)| 183970 ( 8)| 41%Und hier sind die Ergebnisse, wenn Sie über ein Array arbeiten, das mit Nullen gefüllt ist (damit Probleme mit der Speicherbereinigung behoben werden):
Map size | JDK 7 (sd)| JDK 8 (sd)| JDK 8 vs 7 16| 75 (15)| 65 (10)| 87% 64| 116 (34)| 90 (15)| 78% 256| 246 (36)| 191 (20)| 78% 1024| 751 (40)| 562 (20)| 75% 4096| 2857 (44)| 2105 (21)| 74% 16384| 13086 (51)| 8837 (19)| 68% 65536| 52940 (53)| 36080 (16)| 68% 262144| 225727 (48)| 155981 (12)| 69%Die Zahlen sind in Nanosekunden
(sd)angegeben. Dies ist 1 Standardabweichung, ausgedrückt als Prozentsatz des Ergebnisses (zu Ihrer Information, eine "normalverteilte" Population hat eine SD von 68).vsist das JDK 8-Timing relativ zu JDK 7.Es ist interessant, dass es nicht nur deutlich schneller ist, sondern auch die Abweichung etwas geringer ist, was bedeutet, dass die JDK 8-Implementierung etwas konsistenter ist Leistung .
Die Tests wurden auf jdk 1.8.0_45 über eine große (Millionen) Anzahl von Malen auf Arrays ausgeführt, die mit zufälligen
IntegerObjekten gefüllt waren . Um herausliegende Zahlen zu entfernen, wurden bei jedem Ergebnissatz die schnellsten und langsamsten 3% der Timings verworfen. Die Speicherbereinigung wurde angefordert, und der Thread gab unmittelbar vor jedem Aufruf der Methode nach und schlief ein. Das Aufwärmen der JVM wurde bei den ersten 20% der Arbeit durchgeführt und diese Ergebnisse wurden verworfen.quelle
clear()Methodenversionen feststellen (unter JDK 1.8.0_45 32-Bit). Diese Antwort muss also den vollständigen Quellcode für den Benchmark anzeigen, sonst kann man ihm einfach nicht vertrauen.Für mich ist der Grund eine wahrscheinliche Leistungsverbesserung zu vernachlässigbaren Kosten in Bezug auf die Codeklarheit.
Beachten Sie, dass die Implementierung der
fillMethode trivial ist. Eine einfache for-Schleife setzt jedes Array-Element auf null. Das Ersetzen eines Aufrufs durch die tatsächliche Implementierung führt also nicht zu einer signifikanten Verschlechterung der Klarheit / Prägnanz der Aufrufermethode.Die potenziellen Leistungsvorteile sind nicht so unbedeutend, wenn Sie alles berücksichtigen, was dazu gehört:
Die JVM muss die
ArraysKlasse nicht auflösen und bei Bedarf laden und initialisieren. Dies ist ein nicht trivialer Prozess, bei dem die JVM mehrere Schritte ausführt. Zunächst wird der Klassenlader überprüft, um festzustellen, ob die Klasse bereits geladen ist. Dies geschieht jedes Mal, wenn eine Methode aufgerufen wird. Natürlich sind hier Optimierungen erforderlich, aber es sind noch einige Anstrengungen erforderlich. Wenn die Klasse nicht geladen ist, muss die JVM den teuren Prozess des Ladens durchlaufen, den Bytecode überprüfen, andere erforderliche Abhängigkeiten auflösen und schließlich eine statische Initialisierung der Klasse durchführen (was beliebig teuer sein kann). Vorausgesetzt, dasHashMapist eine solche Kernklasse, und dasArrayssolche Kernklasse handelt es sich um eine so große Klasse handelt (mehr als 3600 Zeilen), kann die Vermeidung dieser Kosten zu spürbaren Einsparungen führen.Da es keinen
Arrays.fill(...)Methodenaufruf gibt, muss die JVM nicht entscheiden, ob / wann die Methode in den Körper des Aufrufers eingefügt werden soll. DaHashMap#clear()die JVM häufig aufgerufen wird, führt sie schließlich das Inlining durch, was eine JIT-Neukompilierung derclearMethode erfordert . Ohne Methodenaufrufe,clearWird immer mit Höchstgeschwindigkeit ausgeführt (einmal anfänglich JITed).Ein weiterer Vorteil des Nichtaufrufens von Methoden
Arraysbesteht darin, dass das Abhängigkeitsdiagramm imjava.utilPaket vereinfacht wird , da eine Abhängigkeit entfernt wird.quelle
Ich werde hier im Dunkeln schießen ...
Ich vermute, dass es geändert wurde, um den Grundstein für die Spezialisierung zu legen (auch bekannt als Generika über primitive Typen). Vielleicht (und ich bestehe vielleicht darauf ) soll diese Änderung den Übergang zu Java 10 erleichtern, falls die Spezialisierung Teil des JDK ist.
Wenn man sich den Blick Status des Dokuments Spezialisierung , Sprache Einschränkungen Abschnitt, sagt er folgendes:
(Der Schwerpunkt liegt bei mir).
Und weiter oben im Abschnitt " Specializer-Transformationen " heißt es:
Später, gegen Ende des Dokuments, heißt es im Abschnitt Weitere Untersuchungen :
Nun zur Änderung ...
Wenn die
Arrays.fill(Object[] array, Object value)Methode spezialisiert werden soll, sollte sich ihre Signatur in ändernArrays.fill(T[] array, T value). Dieser Fall ist jedoch speziell im Abschnitt ( bereits erwähnte) Sprachbeschränkungen aufgeführt (dies würde die hervorgehobenen Elemente verletzen). Also vielleicht jemand entschieden , dass es besser wäre, nicht aus der VerwendungHashMap.clear()Methode, vor allem , wennvalueistnull.quelle
Es gibt keinen tatsächlichen Unterschied in der Funktionalität zwischen der Schleife der 2-Version.
Arrays.fillmacht genau das gleiche.Die Entscheidung, ob Sie es verwenden oder nicht, muss also nicht unbedingt als Fehler angesehen werden. Es ist dem Entwickler überlassen, zu entscheiden, wann es um diese Art von Mikromanagement geht.
Für jeden Ansatz gibt es zwei separate Bedenken:
Arrays.fillwird der Code weniger ausführlich und lesbarer.HashMapEs ist tatsächlich eine bessere Option, die Leistung des Codes (wie in Version 8) direkt zu wiederholen. Während der Aufwand für das Einfügen derArraysKlasse vernachlässigbar ist, kann er geringer werden, wenn es um etwas geht, das so weit verbreitet ist, wieHashMapwenn jede Leistungsverbesserung einen großen Effekt hat (stellen Sie sich die geringste Reduzierung des Platzbedarfs einer HashMap in einer vollständigen Webanwendung vor). Berücksichtigen Sie die Tatsache, dass die Arrays-Klasse nur für diese eine Schleife verwendet wurde. Die Änderung ist klein genug, um die klare Methode nicht weniger lesbar zu machen.Der genaue Grund kann nicht herausgefunden werden, ohne den Entwickler zu fragen, der dies tatsächlich getan hat. Ich vermute jedoch, dass es sich entweder um einen Fehler oder um eine kleine Verbesserung handelt. bessere Option.
Meiner Meinung nach kann es als Verbesserung angesehen werden, wenn auch nur durch Zufall.
quelle