Hintergrund:
Beim Optimieren von Pascal- Code mit eingebetteter Assemblersprache bemerkte ich eine unnötige MOVAnweisung und entfernte sie.
Zu meiner Überraschung wurde mein Programm durch das Entfernen der nicht erforderlichen Anweisungen langsamer .
Ich fand heraus, dass das Hinzufügen beliebiger, nutzloser MOVAnweisungen die Leistung noch weiter steigerte .
Der Effekt ist unregelmäßig und ändert sich je nach Ausführungsreihenfolge: Dieselben Junk-Anweisungen , die von einer einzelnen Zeile nach oben oder unten transponiert werden, führen zu einer Verlangsamung .
Ich verstehe, dass die CPU alle Arten von Optimierungen und Rationalisierungen vornimmt, aber dies scheint eher schwarze Magie zu sein.
Die Daten:
Eine Version meines Codes kompiliert bedingt drei Junk-Operationen in der Mitte einer Schleife, die 2**20==1048576mal ausgeführt wird. (Das umgebende Programm berechnet nur SHA-256- Hashes).
Die Ergebnisse auf meiner ziemlich alten Maschine (Intel (R) Core (TM) 2 CPU 6400 bei 2,13 GHz):
avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without: 1836.44 msDie Programme wurden 25 Mal in einer Schleife ausgeführt, wobei sich die Ausführungsreihenfolge jedes Mal zufällig änderte.
Auszug:
{$asmmode intel}
procedure example_junkop_in_sha256;
var s1, t2 : uint32;
begin
// Here are parts of the SHA-256 algorithm, in Pascal:
// s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
// s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
// Here is how I translated them (side by side to show symmetry):
asm
MOV r8d, a ; MOV r9d, e
ROR r8d, 2 ; ROR r9d, 6
MOV r10d, r8d ; MOV r11d, r9d
ROR r8d, 11 {13 total} ; ROR r9d, 5 {11 total}
XOR r10d, r8d ; XOR r11d, r9d
ROR r8d, 9 {22 total} ; ROR r9d, 14 {25 total}
XOR r10d, r8d ; XOR r11d, r9d
// Here is the extraneous operation that I removed, causing a speedup
// s1 is the uint32 variable declared at the start of the Pascal code.
//
// I had cleaned up the code, so I no longer needed this variable, and
// could just leave the value sitting in the r11d register until I needed
// it again later.
//
// Since copying to RAM seemed like a waste, I removed the instruction,
// only to discover that the code ran slower without it.
{$IFDEF JUNKOPS}
MOV s1, r11d
{$ENDIF}
// The next part of the code just moves on to another part of SHA-256,
// maj { r12d } := (a and b) xor (a and c) xor (b and c)
mov r8d, a
mov r9d, b
mov r13d, r9d // Set aside a copy of b
and r9d, r8d
mov r12d, c
and r8d, r12d { a and c }
xor r9d, r8d
and r12d, r13d { c and b }
xor r12d, r9d
// Copying the calculated value to the same s1 variable is another speedup.
// As far as I can tell, it doesn't actually matter what register is copied,
// but moving this line up or down makes a huge difference.
{$IFDEF JUNKOPS}
MOV s1, r9d // after mov r12d, c
{$ENDIF}
// And here is where the two calculated values above are actually used:
// T2 {r12d} := S0 {r10d} + Maj {r12d};
ADD r12d, r10d
MOV T2, r12d
end
end;Versuch es selber:
Der Code ist online bei GitHub, wenn Sie ihn selbst ausprobieren möchten.
Meine Fragen:
- Warum sollte das unnötige Kopieren des Inhalts eines Registers in den Arbeitsspeicher jemals die Leistung steigern?
- Warum sollte dieselbe nutzlose Anweisung in einigen Zeilen eine Beschleunigung und in anderen eine Verlangsamung bewirken?
- Ist dieses Verhalten etwas, das von einem Compiler vorhersehbar ausgenutzt werden könnte?
quelle
Antworten:
Die wahrscheinlichste Ursache für die Geschwindigkeitsverbesserung ist:
Ihr Core2 führt nicht für jeden bedingten Sprung einen separaten Verlaufsdatensatz. Stattdessen wird ein gemeinsamer Verlauf aller bedingten Sprünge gespeichert. Ein Nachteil der globalen Verzweigungsvorhersage besteht darin, dass der Verlauf durch irrelevante Informationen verwässert wird, wenn die verschiedenen bedingten Sprünge nicht korreliert sind.
Dieses kleine Tutorial zur Verzweigungsvorhersage zeigt, wie Verzweigungsvorhersagepuffer funktionieren. Der Cache-Puffer wird durch den unteren Teil der Adresse des Verzweigungsbefehls indiziert. Dies funktioniert gut, es sei denn, zwei wichtige unkorrelierte Zweige teilen sich die gleichen unteren Bits. In diesem Fall kommt es zu einem Aliasing, das viele falsch vorhergesagte Verzweigungen verursacht (wodurch die Anweisungspipeline blockiert und Ihr Programm verlangsamt wird).
Wenn Sie wissen möchten, wie sich Branchenvorhersagen auf die Leistung auswirken, sehen Sie sich diese hervorragende Antwort an: https://stackoverflow.com/a/11227902/1001643
Compiler verfügen normalerweise nicht über genügend Informationen, um zu wissen, welche Zweige einen Alias haben und ob diese Aliase von Bedeutung sind. Diese Informationen können jedoch zur Laufzeit mit Tools wie Cachegrind und VTune ermittelt werden .
quelle
Möglicherweise möchten Sie http://research.google.com/pubs/pub37077.html lesen
TL; DR: Das zufällige Einfügen von NOP-Anweisungen in Programme kann die Leistung leicht um 5% oder mehr steigern, und nein, Compiler können dies nicht einfach ausnutzen. Es ist normalerweise eine Kombination aus Verzweigungsprädiktor und Cache-Verhalten, aber es kann genauso gut z. B. ein Reservierungsstationsstillstand sein (selbst wenn es keine unterbrochenen Abhängigkeitsketten oder offensichtliche Ressourcenüberbelegungen gibt).
quelle
Ich glaube, in modernen CPUs sind die Montageanweisungen, obwohl sie für einen Programmierer die letzte sichtbare Schicht für die Bereitstellung von Ausführungsanweisungen für eine CPU sind, tatsächlich mehrere Schichten von der tatsächlichen Ausführung durch die CPU entfernt.
Moderne CPUs sind RISC / CISC- Hybride, die CISC x86-Anweisungen in interne Anweisungen mit mehr RISC-Verhalten übersetzen. Darüber hinaus gibt es Ausführungsanalysatoren außerhalb der Reihenfolge, Verzweigungsprädiktoren und Intels "Micro-Ops-Fusion", die versuchen, Anweisungen in größeren Chargen gleichzeitiger Arbeit zu gruppieren (ähnlich wie beim VLIW / Itanium- Titanic). Es gibt sogar Cache-Grenzen, die dazu führen können, dass der Code schneller ausgeführt wird, wenn er größer ist (möglicherweise steckt der Cache-Controller ihn intelligenter ein oder hält ihn länger).
CISC hatte schon immer eine Übersetzungsschicht von Assembler zu Mikrocode, aber der Punkt ist, dass mit modernen CPUs die Dinge viel, viel komplizierter sind. Mit all den zusätzlichen Transistorflächen in modernen Halbleiterfertigungsanlagen können CPUs wahrscheinlich mehrere Optimierungsansätze parallel anwenden und dann den am Ende auswählen, der die beste Beschleunigung bietet. Die zusätzlichen Anweisungen können die CPU dazu veranlassen, einen Optimierungspfad zu verwenden, der besser als andere ist.
Die Auswirkung der zusätzlichen Anweisungen hängt wahrscheinlich vom CPU-Modell / der Generation / dem Hersteller ab und ist wahrscheinlich nicht vorhersehbar. Die Optimierung der Assemblersprache auf diese Weise würde die Ausführung für viele Generationen der CPU-Architektur erfordern, möglicherweise unter Verwendung von CPU-spezifischen Ausführungspfaden, und wäre nur für wirklich sehr wichtige Codeabschnitte wünschenswert, obwohl Sie dies wahrscheinlich bereits wissen, wenn Sie Assembler ausführen.
quelle
Cache vorbereiten
Verschiebungsvorgänge in den Speicher können den Cache vorbereiten und nachfolgende Verschiebungsvorgänge beschleunigen. Eine CPU hat normalerweise zwei Ladeeinheiten und eine Speichereinheit. Eine Ladeeinheit kann aus dem Speicher in ein Register lesen (ein Lesevorgang pro Zyklus), eine Speichereinheit speichert von Register zu Speicher. Es gibt auch andere Einheiten, die Operationen zwischen Registern ausführen. Alle Einheiten arbeiten parallel. Daher können wir in jedem Zyklus mehrere Operationen gleichzeitig ausführen, jedoch nicht mehr als zwei Ladevorgänge, einen Speicher und mehrere Registeroperationen. Normalerweise sind es bis zu 4 einfache Operationen mit einfachen Registern, bis zu 3 einfache Operationen mit XMM / YMM-Registern und 1-2 komplexe Operationen mit jeder Art von Registern. Ihr Code hat viele Operationen mit Registern, so dass eine Dummy-Speicheroperation frei ist (da es sowieso mehr als 4 Registeroperationen gibt). Es bereitet jedoch den Speichercache für den nachfolgenden Speichervorgang vor. Informationen zur Funktionsweise von Speicherspeichern finden Sie in derReferenzhandbuch zur Optimierung von Intel 64- und IA-32-Architekturen .
Die falschen Abhängigkeiten brechen
Dies bezieht sich zwar nicht genau auf Ihren Fall, aber manchmal werden 32-Bit-Mov-Operationen unter dem 64-Bit-Prozessor (wie in Ihrem Fall) verwendet, um die höheren Bits (32-63) zu löschen und die Abhängigkeitsketten zu unterbrechen.
Es ist bekannt, dass unter x86-64 die Verwendung von 32-Bit-Operanden die höheren Bits des 64-Bit-Registers löscht. Bitte lesen Sie den entsprechenden Abschnitt - 3.4.1.1 - des Entwicklerhandbuchs für Intel® 64- und IA-32-Architekturen, Band 1 :
Die Mov-Anweisungen, die auf den ersten Blick nutzlos erscheinen, löschen also die höheren Bits der entsprechenden Register. Was gibt es uns? Es unterbricht Abhängigkeitsketten und ermöglicht die parallele Ausführung der Anweisungen in zufälliger Reihenfolge durch den seit Pentium Pro 1995 intern von CPUs implementierten Out-of-Order-Algorithmus .
Ein Zitat aus dem Referenzhandbuch zur Optimierung von Intel® 64- und IA-32-Architekturen , Abschnitt 3.5.1.8:
MOVZX und MOV mit 32-Bit-Operanden für x64 sind äquivalent - sie alle unterbrechen Abhängigkeitsketten.
Deshalb wird Ihr Code schneller ausgeführt. Wenn keine Abhängigkeiten bestehen, kann die CPU die Register intern umbenennen, obwohl es auf den ersten Blick so aussieht, als ob der zweite Befehl ein vom ersten Befehl verwendetes Register modifiziert und die beiden nicht parallel ausgeführt werden können. Aber aufgrund der Umbenennung des Registers können sie.
Das Umbenennen von Registern ist eine Technik, die intern von einer CPU verwendet wird und die falschen Datenabhängigkeiten beseitigt, die sich aus der Wiederverwendung von Registern durch aufeinanderfolgende Anweisungen ergeben, zwischen denen keine echten Datenabhängigkeiten bestehen.
Ich denke, Sie sehen jetzt, dass es zu offensichtlich ist.
quelle