Die Ausführung des folgenden Java-Programms dauert durchschnittlich zwischen 0,50 und 0,55 Sekunden:
public static void main(String[] args) {
long startTime = System.nanoTime();
int n = 0;
for (int i = 0; i < 1000000000; i++) {
n += 2 * (i * i);
}
System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");
System.out.println("n = " + n);
}
Wenn ich ersetzen 2 * (i * i)
mit 2 * i * i
, dauert es zwischen 0,60 und 0,65 Sekunden zu laufen. Woher?
Ich habe jede Version des Programms 15 Mal ausgeführt, abwechselnd zwischen den beiden. Hier sind die Ergebnisse:
2*(i*i) | 2*i*i
----------+----------
0.5183738 | 0.6246434
0.5298337 | 0.6049722
0.5308647 | 0.6603363
0.5133458 | 0.6243328
0.5003011 | 0.6541802
0.5366181 | 0.6312638
0.515149 | 0.6241105
0.5237389 | 0.627815
0.5249942 | 0.6114252
0.5641624 | 0.6781033
0.538412 | 0.6393969
0.5466744 | 0.6608845
0.531159 | 0.6201077
0.5048032 | 0.6511559
0.5232789 | 0.6544526
Der schnellste Lauf von 2 * i * i
dauerte länger als der langsamste Lauf von 2 * (i * i)
. Wenn sie die gleiche Effizienz hätten, wäre die Wahrscheinlichkeit, dass dies geschieht, geringer als 1/2^15 * 100% = 0.00305%
.
java
performance
benchmarking
bytecode
jit
Stefan
quelle
quelle
2 * i * i
ist es langsamer. Ich werde auch versuchen, mit Graal zu laufen.i * i * 2
schneller als2 * i * i
? " Umbenennen, um die Klarheit zu verbessern, dass das Problem in der Reihenfolge der Vorgänge liegt.Antworten:
Es gibt einen kleinen Unterschied in der Reihenfolge des Bytecodes.
2 * (i * i)
::vs
2 * i * i
:Auf den ersten Blick sollte dies keinen Unterschied machen; Wenn überhaupt, ist die zweite Version optimaler, da sie einen Steckplatz weniger verwendet.
Wir müssen also tiefer in die untere Ebene (JIT) 1 graben .
Denken Sie daran, dass JIT dazu neigt, kleine Schleifen sehr aggressiv abzuwickeln. In der Tat beobachten wir ein 16-faches Abrollen für den
2 * (i * i)
Fall:Wir sehen, dass es 1 Register gibt, das auf den Stapel "verschüttet" wird.
Und für die
2 * i * i
Version:Hier beobachten wir viel mehr "Verschütten" und mehr Zugriffe auf den Stapel
[RSP + ...]
, da mehr Zwischenergebnisse erhalten bleiben müssen.Die Antwort auf die Frage ist daher einfach: Sie
2 * (i * i)
ist schneller als2 * i * i
weil die JIT für den ersten Fall einen optimaleren Assembler-Code generiert.Aber natürlich ist es offensichtlich, dass weder die erste noch die zweite Version etwas Gutes ist; Die Schleife könnte wirklich von der Vektorisierung profitieren, da jede x86-64-CPU mindestens SSE2-Unterstützung bietet.
Es ist also ein Problem des Optimierers. Wie so oft rollt es sich zu aggressiv ab und schießt sich in den Fuß, während es verschiedene andere Möglichkeiten verpasst.
Tatsächlich zerlegen moderne x86-64-CPUs die Anweisungen weiter in Micro-Ops (µops). Mit Funktionen wie Registerumbenennung, µop-Caches und Loop-Puffern erfordert die Loop-Optimierung viel mehr Finesse als ein einfaches Abrollen, um eine optimale Leistung zu erzielen. Laut dem Optimierungsleitfaden von Agner Fog :
In Bezug auf diese Ladezeiten kostet selbst der schnellste L1D-Treffer 4 Zyklen , ein zusätzliches Register und µop. Ja, selbst ein paar Zugriffe auf den Speicher beeinträchtigen die Leistung in engen Schleifen.
Aber zurück zur Vektorisierungsmöglichkeit - um zu sehen, wie schnell es sein kann, können wir eine ähnliche C-Anwendung mit GCC kompilieren , die sie direkt vektorisiert (AVX2 wird gezeigt, SSE2 ist ähnlich) 2 :
Mit Laufzeiten:
1 Um eine von JIT generierte Assembly-Ausgabe zu erhalten, rufen Sie eine Debug-JVM ab und führen Sie sie aus
-XX:+PrintOptoAssembly
2 Die C-Version wird mit dem
-fwrapv
Flag kompiliert , wodurch GCC den Überlauf von vorzeichenbehafteten Ganzzahlen als Wrap-Around mit zwei Komplementen behandeln kann.quelle
ret
Anweisung aus, oder geben Sie ein Label und keine Ret-Anweisung aus, damit die Ausführung einfach durchfällt. GCC verhält sich in der Tat manchmal so, wenn es auf UB trifft. Zum Beispiel: Warum mit der Optimierung verschwinden? . Sie möchten auf jeden Fall wohlgeformten Code kompilieren, um sicherzugehen, dass der Asm gesund ist.mov
/ verwendetadd-immediate
. zBmovl RBX, R9
/addl RBX, #8
sollte seinleal ebx, [r9 + 8]
, 1 uop zum Kopieren und Hinzufügen. Oderleal ebx, [r9 + r9 + 16]
zu tunebx = 2*(r9+8)
. Also ja, das Abrollen bis zum Verschütten ist dumm, ebenso wie naiver Braindead-Codegen, der ganzzahlige Identitäten und assoziative ganzzahlige Mathematik nicht ausnutzt.Wenn die Multiplikation ist
2 * (i * i)
, kann die JVM die Multiplikation mit2
aus der Schleife herausrechnen, was zu diesem äquivalenten, aber effizienteren Code führt:Wenn die Multiplikation jedoch erfolgt
(2 * i) * i
, wird sie von der JVM nicht optimiert, da die Multiplikation mit einer Konstanten nicht mehr unmittelbar vor der Addition erfolgt.Hier sind einige Gründe, warum ich denke, dass dies der Fall ist:
if (n == 0) n = 1
Anweisung am Anfang der Schleife führt dazu, dass beide Versionen genauso effizient sind, da das Ausklammern der Multiplikation nicht mehr garantiert, dass das Ergebnis dasselbe ist2 * (i * i)
VersionHier ist der Testcode, mit dem ich diese Schlussfolgerungen gezogen habe:
Und hier sind die Ergebnisse:
quelle
n *= 2000000000;
2*1*1 + 2*2*2 + 2*3*3
. Es ist offensichtlich, dass das Berechnen1*1 + 2*2 + 3*3
und Multiplizieren mit 2 korrekt ist, während das Multiplizieren mit 8 nicht korrekt wäre.2(1²) + 2(2²) + 2(3²) = 2(1² + 2² + 3²)
. Das war sehr einfach und ich habe es einfach vergessen, weil die Schleife inkrementiert wurde.2 * (i * i)
aber nicht aus(2 * i) * i
herausrechnen? Ich würde denken, dass sie gleichwertig sind (das könnte meine schlechte Annahme sein). Wenn ja, würde die JVM den Ausdruck nicht vor der Optimierung kanonisieren?Bytecodes: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Bytecodes Viewer: https://github.com/Konloch/bytecode-viewer
Auf meinem JDK (Windows 10 64 Bit, 1.8.0_65-b17) kann ich Folgendes reproduzieren und erklären:
Ausgabe:
Warum also? Der Bytecode lautet wie folgt:
Der Unterschied ist: Mit Klammern (
2 * (i * i)
):Ohne Klammern (
2 * i * i
):Das Laden aller Daten auf den Stapel und das anschließende Zurückarbeiten ist schneller als das Umschalten zwischen dem Auflegen des Stapels und dem Bearbeiten des Stapels.
quelle
Kasperd fragte in einem Kommentar zur akzeptierten Antwort:
Ich habe nicht genug Ruf, um dies in den Kommentaren zu beantworten, aber dies sind die gleichen ISA. Es sei darauf hingewiesen, dass die GCC-Version eine 32-Bit-Ganzzahllogik verwendet und die JVM-kompilierte Version intern eine 64-Bit-Ganzzahllogik verwendet.
R8 bis R15 sind nur neue X86_64- Register . EAX to EDX sind die unteren Teile der RAX to RDX-Allzweckregister. Der wichtige Teil der Antwort ist, dass die GCC-Version nicht abgewickelt wird. Es wird einfach eine Runde der Schleife pro tatsächlicher Maschinencode-Schleife ausgeführt. Während die JVM-Version 16 Runden der Schleife in einer physischen Schleife enthält (basierend auf der Rustyx-Antwort habe ich die Assembly nicht neu interpretiert). Dies ist einer der Gründe, warum mehr Register verwendet werden, da der Schleifenkörper tatsächlich 16-mal länger ist.
quelle
*2
die Schleife verlassen kann. Obwohl es in diesem Fall nicht einmal ein Gewinn ist, dies zu tun, weil es mit LEA kostenlos ist. Hat auf Intel-CPUslea eax, [rax+rcx*2]
die gleiche 1c-Latenz wieadd eax,ecx
. Bei AMD-CPUs erhöht jedoch jeder skalierte Index die LEA-Latenz auf 2 Zyklen. Die durch Schleifen übertragene Abhängigkeitskette verlängert sich also auf 2 Zyklen und wird zum Engpass bei Ryzen. (Derimul ecx,edx
Durchsatz beträgt 1 pro Takt bei Ryzen und Intel).Obwohl dies nicht direkt mit der Umgebung der Frage zusammenhängt, habe ich aus Neugier den gleichen Test im Release-Modus von .NET Core 2.1, x64 durchgeführt.
Hier ist das interessante Ergebnis, das ähnliche Phonomen (umgekehrt) bestätigt, die über der dunklen Seite der Kraft auftreten. Code:
Ergebnis:
2 * (i * i)
2 * i * i
quelle
Ich habe ähnliche Ergebnisse erhalten:
Ich habe die gleichen Ergebnisse erhalten, wenn sich beide Schleifen im selben Programm befanden oder sich jede in einer separaten Java-Datei / Klasse befand, die in einem separaten Lauf ausgeführt wurde.
Zum Schluss hier eine
javap -c -v <.java>
Dekompilierung von jedem:vs.
Zu Ihrer Information -
quelle
-XX:+PrintOptoAssembly
. Oder verwenden Sie einfach vtune oder ähnliches.Interessante Beobachtung mit Java 11 und Ausschalten des Schleifens mit der folgenden VM-Option:
Die Schleife mit dem
2 * (i * i)
Ausdruck führt zu einem kompakteren nativen Code 1 :im Vergleich zur
2 * i * i
Version:Java-Version:
Benchmark-Ergebnisse:
Benchmark-Quellcode:
1 - Verwendete VM-Optionen:
-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0
quelle
i
vor dem Kopieren zu erhöhen2*i
, um es zu berechnen , wird es danach ausgeführt, sodass eine zusätzlicheadd r11d,2
Anweisung erforderlich ist . (Außerdem fehlt dasadd same,same
Guckloch anstelleshl
von 1 (Hinzufügen von Läufen an mehr Ports). Außerdem fehlt ein LEA-Guckloch fürx*2 + 2
(lea r11d, [r8*2 + 2]
), wenn aus einem verrückten Grund für die Befehlsplanung wirklich Dinge in dieser Reihenfolge ausgeführt werden sollen Die ungerollte Version, die LEA verpasst hat, hat viel Geld gekostet, genau wie beide Loops hier.lea eax, [rax + r11 * 2]
würde 2 Anweisungen (in beiden Schleifen) ersetzen, wenn der JIT-Compiler Zeit hätte, diese Optimierung in lang laufenden Schleifen zu suchen. Jeder anständige Compiler, der der Zeit voraus ist, würde es finden. (Es sei denn, es wird möglicherweise nur für AMD eingestellt, wo LEA mit skaliertem Index eine Latenz von 2 Zyklen aufweist, die sich also möglicherweise nicht lohnt.)Ich habe einen JMH mit dem Standard-Archetyp ausprobiert: Ich habe auch eine optimierte Version hinzugefügt, die auf Runemoros Erklärung basiert .
Das Ergebnis ist hier:
Auf meinem PC ( Core i7 860 - es macht nichts anderes als das Lesen auf meinem Smartphone):
n += i*i
dannn*2
ist zuerst2 * (i * i)
ist an zweiter Stelle.Die JVM optimiert eindeutig nicht auf die gleiche Weise wie ein Mensch (basierend auf Runemoros Antwort).
Lesen Sie nun den Bytecode:
javap -c -v ./target/classes/org/sample/MyBenchmark.class
Ich bin kein Experte für Bytecode, aber wir
iload_2
vor unsimul
: Hier liegt wahrscheinlich der Unterschied: Ich kann davon ausgehen, dass die JVM das Leseni
zweimal optimiert (i
ist bereits vorhanden und muss nicht erneut geladen werden), während sie sich in der2*i*i
Dose befindet. ' t.quelle
Eher ein Nachtrag. Ich habe das Experiment mit der neuesten Java 8 JVM von IBM wiederholt:
Und das zeigt sehr ähnliche Ergebnisse:
(zweite Ergebnisse mit 2 * i * i).
Interessanterweise, wenn Sie auf demselben Computer ausgeführt werden, aber Oracle Java verwenden:
Ergebnisse sind im Durchschnitt etwas langsamer:
Lange Rede, kurzer Sinn: Auch die geringe Versionsnummer von HotSpot spielt hier eine Rolle, da subtile Unterschiede innerhalb der JIT-Implementierung bemerkenswerte Auswirkungen haben können.
quelle
Die beiden Methoden zum Hinzufügen generieren leicht unterschiedlichen Bytecode:
Für
2 * (i * i)
vs:Zum
2 * i * i
.Und wenn Sie einen JMH- Benchmark wie diesen verwenden:
Der Unterschied ist klar:
Was Sie beobachten, ist korrekt und nicht nur eine Anomalie Ihres Benchmarking-Stils (dh kein Aufwärmen, siehe Wie schreibe ich einen korrekten Mikro-Benchmark in Java? )
Wieder laufen mit Graal:
Sie sehen, dass die Ergebnisse viel näher liegen, was Sinn macht, da Graal ein insgesamt leistungsfähigerer, modernerer Compiler ist.
Das hängt also wirklich davon ab, wie gut der JIT-Compiler in der Lage ist, einen bestimmten Code zu optimieren, und hat nicht unbedingt einen logischen Grund dafür.
quelle