Welche Opcodes sind auf CPU-Ebene schneller? [geschlossen]

19

In jeder Programmiersprache gibt es Opcode-Sätze, die anderen vorzuziehen sind. Ich habe versucht, sie hier in der Reihenfolge ihrer Geschwindigkeit aufzulisten.

  1. Bitweise
  2. Ganzzahlige Addition / Subtraktion
  3. Ganzzahlige Multiplikation / Division
  4. Vergleich
  5. Kontrollfluss
  6. Float Addition / Subtraktion
  7. Float-Multiplikation / Division

Wenn Sie leistungsstarken Code benötigen, kann C ++ in der Assembly von Hand optimiert werden, um SIMD-Anweisungen oder einen effizienteren Steuerungsfluss, Datentypen usw. zu verwenden. Ich versuche also zu verstehen, ob der Datentyp (int32 / float32 / float64) oder der Betrieb verwendet wird ( *, +, &) beeinflusst die Leistung auf CPU - Ebene.

  1. Ist eine einzelne Multiplikation auf der CPU langsamer als eine Addition?
  2. In der MCU-Theorie lernen Sie, dass die Geschwindigkeit von Opcodes durch die Anzahl der CPU-Zyklen bestimmt wird, die zur Ausführung erforderlich sind. Bedeutet dies, dass das Multiplizieren 4 Zyklen und das Addieren 2 Zyklen dauert?
  3. Was genau sind die Geschwindigkeitsmerkmale der grundlegenden mathematischen und Kontrollfluss-Opcodes?
  4. Wenn zwei Opcodes die gleiche Anzahl von Zyklen benötigen, um ausgeführt zu werden, können beide ohne Leistungsgewinn / -verlust austauschbar verwendet werden.
  5. Alle anderen technischen Details, die Sie zur x86-CPU-Leistung mitteilen können, sind willkommen
Robinicks
quelle
17
Das klingt nach vorzeitiger Optimierung, und denken Sie daran, dass der Compiler nicht ausgibt, was Sie eingeben, und Sie wirklich keine Assembly schreiben möchten, es sei denn, Sie haben es wirklich auch.
Roy T.
3
Float-Multiplikation und Division sind völlig verschiedene Dinge, Sie sollten sie nicht in dieselbe Kategorie einordnen. Bei n-Bit-Zahlen ist die Multiplikation ein O (n) -Prozess und die Division ein O (nlogn) -Prozess. Dies macht die Division auf modernen CPUs etwa 5-mal langsamer als die Multiplikation.
Sam Hocevar
1
Die einzig wahre Antwort ist "profile it".
Tetrad
1
Nach Roys Antwort wird die Handoptimierung der Montage fast immer einen Nettoverlust bedeuten, es sei denn, Sie sind wirklich wirklich außergewöhnlich. Moderne CPUs sind sehr komplexe Monster und gute, optimierende Compiler lösen Code-Transformationen aus, die völlig unübersehbar und für den Code von Hand nicht trivial sind. Verwenden Sie auch für SSE / SIMD immer intrinsics in C / C ++ und lassen Sie den Compiler deren Verwendung für Sie optimieren. Wenn Sie Raw Assembly verwenden, werden die Compiler-Optimierungen deaktiviert, und Sie verlieren viel.
Sean Middleditch
Sie müssen die Baugruppe nicht manuell optimieren, um SIMD zu verwenden. Die Optimierung von SIMD ist abhängig von der jeweiligen Situation sehr nützlich. Für die Verwendung von SSE2 gibt es jedoch meistens eine Standardkonvention (sie funktioniert mindestens für GCC und MSVC). Was Ihre Liste betrifft, verursachen Datenabhängigkeit und Registerdruck auf einem modernen superskalaren Multi-Pipeline-Prozessor mehr Probleme als eine rohe Ganzzahl und manchmal eine Gleitkommaleistung. Gleiches gilt für die Datenlokalität. Übrigens ist die Ganzzahldivision die gleiche wie die Multiplikation auf einem modernen x86
OrgnlDave

Antworten:

26

Die Optimierungsleitfäden von Agner Fog sind ausgezeichnet. Er verfügt über Handbücher, Tabellen mit Befehlszeiten und Dokumente zur Mikroarchitektur aller neueren x86-CPU-Designs (bis hin zu Intel Pentium). Siehe auch einige andere Ressourcen, die von /programming//tags/x86/info verlinkt sind

Nur zum Spaß beantworte ich einige der Fragen (Zahlen von aktuellen Intel-CPUs). Die Wahl der Ops ist nicht der Hauptfaktor für die Optimierung des Codes (es sei denn, Sie können eine Aufteilung vermeiden.)

Ist eine einzelne Multiplikation auf der CPU langsamer als eine Addition?

Ja (es sei denn, es ist durch eine Potenz von 2). (3-4-fache Latenz mit nur einem Durchsatz pro Takt bei Intel.) Gehen Sie jedoch nicht zu weit, um dies zu vermeiden, da es nur 2 oder 3 Mal schneller ist.

Was genau sind die Geschwindigkeitsmerkmale der grundlegenden mathematischen und Kontrollfluss-Opcodes?

Siehe Agner Fog Instruktionstabellen und Mikroarchitektur Anleitung , wenn Sie wissen wollen , genau : P. Sei vorsichtig mit bedingten Sprüngen. Bedingungslose Sprünge (wie Funktionsaufrufe) haben einen geringen Overhead, aber nicht viel.

Wenn zwei Opcodes die gleiche Anzahl von Zyklen benötigen, um ausgeführt zu werden, können beide ohne Leistungsgewinn / -verlust austauschbar verwendet werden.

Nein, sie konkurrieren möglicherweise um den gleichen Ausführungsport wie etwas anderes, oder sie konkurrieren möglicherweise nicht. Dies hängt davon ab, an welchen anderen Abhängigkeitsketten die CPU parallel arbeiten kann. (In der Praxis ist in der Regel keine sinnvolle Entscheidung zu treffen. Gelegentlich kann es vorkommen, dass Sie eine Vektorverschiebung oder eine Vektorverschiebung verwenden, die auf verschiedenen Ports von Intel-CPUs ausgeführt werden. Das gesamte Register wird jedoch byteweise verschoben.) PSLLDQetc.) läuft in der Shuffle Unit.)

Alle anderen technischen Details, die Sie zur x86-CPU-Leistung mitteilen können, sind willkommen

In den Microarch-Dokumenten von Agner Fog werden die Pipelines von Intel- und AMD-CPUs detailliert genug beschrieben, um genau zu bestimmen, wie viele Zyklen eine Schleife pro Iteration dauern soll und ob es sich um einen UOP-Durchsatz, eine Abhängigkeitskette oder einen Konflikt um einen Ausführungsport handelt. Sehen Sie sich einige meiner Antworten auf StackOverflow an, wie diese oder diese .

Auch http://www.realworldtech.com/haswell-cpu/ (und ähnliches für frühere Designs) macht das Lesen Spaß, wenn Sie CPU-Design mögen.

Hier ist Ihre Liste, sortiert nach einer Haswell-CPU, basierend auf meinen besten Gästezahlen. Dies ist jedoch keine wirklich nützliche Methode, um über Dinge nachzudenken, außer eine ASM-Schleife abzustimmen. Cache- / Verzweigungsvorhersageeffekte dominieren normalerweise. Schreiben Sie Ihren Code, um gute Muster zu erhalten. Zahlen sind sehr wellenförmig und versuchen, eine hohe Latenz zu berücksichtigen, auch wenn der Durchsatz kein Problem darstellt, oder mehr Uops zu generieren, die die Pipe verstopfen, damit andere Dinge parallel ablaufen. Esp. Die Cache / Branch-Nummern sind sehr zusammengesetzt. Latenz ist wichtig für schleifenbasierte Abhängigkeiten, Durchsatz ist wichtig, wenn jede Iteration unabhängig ist.

TL: DR Diese Zahlen basieren auf dem, was ich mir für einen "typischen" Anwendungsfall vorstelle, was die Kompromisse zwischen Latenz, Ausführungsport-Engpässen und Front-End-Durchsatz (oder Verzögerungen bei Zweigniederlassungen) betrifft ). Bitte verwenden Sie diese Zahlen nicht für ernsthafte Perfektionsanalysen .

  • 0,5 bis 1 Bitweise / Ganzzahlige Addition / Subtraktion /
    Verschieben und Drehen ( konstante Anzahl zur Kompilierungszeit) /
    Vektorversionen von all diesen (1 bis 4 pro Zyklusdurchsatz, 1 Zykluslatenz )
  • 1 Vektor min, max, vergleiche-gleich, vergleiche-größer (um eine Maske zu erstellen)
  • 1,5 Vektormischungen. Haswell und neuere Versionen haben nur einen Shuffle-Port, und meiner Meinung nach ist es üblich, viel zu mischen, wenn Sie etwas benötigen. Deshalb gewichte ich es etwas höher, um zum Nachdenken über die Verwendung von weniger Mischen anzuregen. Sie sind nicht frei, esp. Wenn Sie eine pshufb-Kontrollmaske aus dem Speicher benötigen.
  • 1,5 Laden / Speichern (L1-Cache-Treffer. Durchsatz besser als Latenz)
  • 1,75 Integer Multiplication (3 c Latenz / 1 c Tput bei Intel, 4 c Lat bei AMD und nur 1 c Tput bei Intel). Kleine Konstanten sind mit LEA und / oder ADD / SUB / shift noch günstiger . Aber natürlich sind Konstanten zur Kompilierungszeit immer gut und können oft in andere Dinge optimiert werden. (Und Multiplikation in einer Schleife kann oft vom Compiler auf tmp += 7eine Schleife reduziert werden anstatt tmp = i*7)
  • 1,75 einige 256b-Vektor-Shuffle (zusätzliche Latenz auf Insns, die Daten zwischen 128b-Spuren eines AVX-Vektors verschieben können). (Oder 3 bis 7 auf Ryzen, wo Spurwechsel viel mehr Uops benötigen)
  • 2 fp add / sub (und Vektorversionen davon) (1 oder 2 pro Zyklusdurchsatz, 3 bis 5 Zykluslatenz). Kann langsam sein, wenn Sie einen Engpass bei der Latenz haben, z. B. wenn Sie ein Array mit nur einer sumVariablen summieren . (Ich könnte dies und fp mul so niedrig wie 1 oder so hoch wie 5 je nach Anwendungsfall wiegen).
  • 2 vektor fp mul oder FMA. (x * y + z ist so günstig wie mul oder add, wenn Sie mit aktivierter FMA-Unterstützung kompilieren).
  • 2 Einfügen / Extrahieren von Allzweckregistern in Vektorelemente ( _mm_insert_epi8usw.)
  • 2,25 vector int mul (16-Bit-Elemente oder pmaddubsw tun 8 * 8 -> 16-Bit). Bei Skylake billiger, mit besserem Durchsatz als bei Scalar Mul
  • 2,25 verschieben / drehen durch variable Anzahl (2 c Latenz, 1 pro 2 c Durchsatz bei Intel, schneller bei AMD oder mit BMI2)
  • 2.5 Vergleich ohne Verzweigung ( y = x ? a : b, oder y = x >= 0) ( test / setccoder cmov)
  • 3 int-> float umwandlung
  • 3 Perfekt vorhergesagter Kontrollfluss (vorhergesagte Verzweigung, Aufruf, Rückkehr).
  • 4 vector int mul (32-bit elements) (2 uops, 10c latenz bei Haswell)
  • 4 Ganzzahldivision oder %durch eine Konstante zur Kompilierungszeit (keine Potenz von 2).
  • 7 horizontale Vektoroperationen (z. B. PHADDHinzufügen von Werten innerhalb eines Vektors)
  • 11 (Vektor) FP Division (10-13 c Latenz, einer pro 7 c Durchsatz oder schlechter). (Kann billig sein, wenn selten verwendet, aber der Durchsatz ist 6 bis 40x schlechter als bei FP mul)
  • 13? Kontrollfluss (schlecht vorhergesagter Zweig, möglicherweise zu 75% vorhersehbar)
  • 13 int division ( ja wirklich , es ist langsamer als die FP-Division und kann nicht vektorisieren). (Beachten Sie, dass Compiler durch eine Konstante mit mul / shift / add mit einer magischen Konstante dividieren und div / mod durch Potenzen von 2 sehr billig ist.)
  • 16 (Vektor) FP sqrt
  • 25? Laden (L3-Cache-Treffer). (Cache-Miss-Stores sind billiger als Ladungen.)
  • 50? FP-Trigger / Exp / Log. Wenn Sie viel Exp / Log benötigen und nicht die volle Genauigkeit benötigen, können Sie Genauigkeit gegen Geschwindigkeit mit einem kürzeren Polynom und / oder einer Tabelle tauschen. Sie können auch SIMD vektorisieren.
  • 50-80? Immer - unvorhergesehener Zweig, der 15-20 Zyklen kostet
  • 200-400 & le; Laden / Speichern (Cache-Miss)
  • 3000 ??? Seite aus Datei lesen (OS Disk Cache Hit) (Zahlen hier zusammenstellen)
  • 20000 ??? Disk Read Page (OS-Disk-Cache-Fehler, schnelle SSD) (vollständig erfundene Nummer)

Ich habe das komplett durch Rätselraten erfunden . Wenn etwas falsch aussieht, liegt es entweder daran, dass ich an einen anderen Anwendungsfall gedacht habe, oder an einem Bearbeitungsfehler.

Die relativen Kosten für AMD-CPUs sind ähnlich, mit der Ausnahme, dass sie schnellere Integer-Shifter haben, wenn die Anzahl der Shifts variabel ist. CPUs der AMD Bulldozer-Familie sind auf den meisten Codes aus verschiedenen Gründen natürlich langsamer. (Ryzen ist ziemlich gut in vielen Dingen).

Denken Sie daran, dass es wirklich unmöglich ist, Dinge auf eindimensionale Kosten zu reduzieren . Abgesehen von Cachefehlern und Verzweigungsfehlern kann der Engpass in einem Codeblock die Latenz, der gesamte UOP-Durchsatz (Frontend) oder der Durchsatz eines bestimmten Ports (Ausführungsport) sein.

Eine "langsame" Operation wie die FP-Division kann sehr billig sein, wenn der umgebende Code die CPU mit anderen Arbeiten beschäftigt . (Vektor-FP-Div oder -SQRT sind jeweils 1 UOP, sie haben nur eine schlechte Latenz und einen schlechten Durchsatz. Sie blockieren nur die Divisionseinheit, nicht den gesamten Ausführungsport, auf dem sie sich befindet. Integer-Div sind mehrere UOPs.) Wenn Sie also nur eine FP-Divide haben für jeden ~ 20 mul und add, und es gibt andere arbeit für die CPU zu erledigen (zB eine unabhängige schleifeniteration), dann könnten die "kosten" des FP div ungefähr die gleichen sein wie bei einem FP mul. Dies ist wahrscheinlich das beste Beispiel für etwas, das nur einen geringen Durchsatz aufweist, sich aber aufgrund der geringen Gesamt-Uops sehr gut mit anderem Code vermischt (wenn die Latenz kein Faktor ist).

Beachten Sie, dass die Ganzzahldivision dem umgebenden Code bei weitem nicht so nahe kommt: In Haswell sind es 9 Uops mit einem Durchsatz von 8 bis 11 c und einer Latenz von 22 bis 29 c. (Die 64-Bit-Teilung ist selbst bei Skylake viel langsamer.) Die Latenz und die Durchsatzzahlen sind also ähnlich wie bei FP Div, aber FP Div ist nur ein UOP.

Beispiele zum Analysieren einer kurzen Sequenz von Insns auf Durchsatz, Latenz und Gesamt-Uops finden Sie in einigen meiner SO-Antworten:

IDK, wenn andere SO Antworten einschließlich dieser Art von Analyse schreiben. Es fällt mir viel leichter, mein eigenes zu finden, weil ich weiß, dass ich oft auf dieses Detail gehe und mich an das erinnere, was ich geschrieben habe.

Peter Cordes
quelle
Der "vorhergesagte Zweig" bei 4 ist sinnvoll - was sollte der "vorhergesagte Zweig" bei 20-25 wirklich sein? (Ich hatte gedacht, dass falsch vorhergesagte Zweige (aufgeführt um 13) viel teurer sind, aber genau deshalb bin ich auf dieser Seite, um etwas näher an der Wahrheit zu lernen - danke für die großartige Tabelle!)
Matt
@Matt: Ich denke, es war ein Bearbeitungsfehler und sollte "falsch vorhergesagter Zweig" sein. Vielen Dank für den Hinweis. Beachten Sie, dass 13 für einen unvollständig vorhergesagten Zweig steht, und nicht für einen immer falsch vorhergesagten Zweig. Deshalb habe ich das klargestellt. Ich habe die Handbewegung wiederholt und einige Änderungen vorgenommen. : P
Peter Cordes
16

Das hängt von der jeweiligen CPU ab, aber für eine moderne CPU sieht die Liste ungefähr so ​​aus:

  1. Bitweise Addition, Subtraktion, Vergleich, Multiplikation
  2. Teilung
  3. Kontrollfluss (siehe Antwort 3)

Abhängig von der CPU kann das Arbeiten mit 64-Bit-Datentypen erhebliche Kosten verursachen.

Deine Fragen:

  1. Auf einer modernen CPU überhaupt nicht oder nicht nennenswert. Abhängig von der CPU.
  2. Diese Informationen sind in etwa 20 bis 30 Jahre veraltet (Schule ist zum Kotzen, Sie haben jetzt Beweise dafür). Moderne CPUs verarbeiten eine variable Anzahl von Befehlen pro Uhr.
  3. Die Division ist etwas langsamer als der Rest, der Steuerungsfluss ist sehr schnell, wenn die Verzweigungsvorhersage korrekt ist, und sehr langsam, wenn sie falsch ist (etwa 20 Zyklen, abhängig von der CPU). Das Ergebnis ist, dass eine Menge Code hauptsächlich durch den Kontrollfluss begrenzt wird. Tun Sie nichts mit dem, ifwas Sie mit Arithmetik vernünftigerweise tun können.
  4. Es gibt keine feste Anzahl für die Anzahl der Zyklen, die ein Befehl benötigt, aber manchmal können zwei verschiedene Befehle gleich ausgeführt werden, sie werden in einen anderen Kontext gestellt und möglicherweise nicht auf einer anderen CPU ausgeführt, und es ist wahrscheinlich, dass Sie ein drittes Ergebnis sehen.
  5. Neben dem Kontrollfluss ist die andere große Zeitverschwendung Cache-Fehlschläge. Wenn Sie versuchen, Daten zu lesen, die sich nicht im Cache befinden, muss die CPU warten, bis sie aus dem Speicher abgerufen werden. Im Allgemeinen sollten Sie versuchen, Datenstücke gleichzeitig nebeneinander zu verarbeiten, anstatt Daten von überall herauszusuchen.

Und schließlich, wenn Sie ein Spiel machen, sorgen Sie sich nicht zu sehr darum, sondern konzentrieren Sie sich lieber darauf, ein gutes Spiel zu machen, als die CPU-Zyklen zu unterbrechen.

aaaaaaaaaaa
quelle
Ich möchte auch darauf hinweisen, dass die FPU verdammt schnell ist: besonders bei Intel - daher wird Festkomma nur dann wirklich benötigt, wenn Sie deterministische Ergebnisse erzielen möchten.
Jonathan Dickinson
2
Ich würde nur den letzten Teil stärker betonen - ein gutes Spiel machen. Es ist hilfreich, den Code klar zu halten - aus diesem Grund gilt 3. nur, wenn Sie tatsächlich ein Leistungsproblem messen. Es ist immer einfach, diese Wenns in etwas Besseres zu verwandeln, wenn es nötig ist. Auf der anderen Seite ist 5. schwieriger - ich stimme definitiv zu, dass dies ein Fall ist, bei dem Sie wirklich zuerst nachdenken möchten, da dies normalerweise eine Änderung der Architektur bedeutet.
Luaan
3

Ich habe einen Test über Integer-Operationen durchgeführt, der millionenfach auf x64_64 geloopt wurde.

addieren --- 116 Mikrosekunden

Sub ---- 116 Mikrosekunden

mul ---- 1036 Mikrosekunden

div ---- 13037 Mikrosekunden

Die obigen Daten haben bereits den durch die Schleife verursachten Overhead verringert.

hxiao
quelle
2

Die Intel-Prozessorhandbücher können kostenlos von der Website heruntergeladen werden. Sie sind ziemlich groß, können aber technisch Ihre Frage beantworten. Insbesondere das Optimierungshandbuch ist genau das, wonach Sie suchen. In der Bedienungsanleitung sind jedoch auch die Timings und Latenzen für die meisten wichtigen CPU-Linien für einfache Anweisungen aufgeführt, da sie von Chip zu Chip variieren.

Im Allgemeinen würde ich sowohl vollständige Zweige als auch Pointer-Chasing (Link-List-Traverals, Aufrufen virtueller Funktionen) als Top-Performance-Killer betrachten, aber die x86 / x64-CPUs sind in beiden Bereichen im Vergleich zu anderen Architekturen sehr gut. Wenn Sie jemals auf eine andere Plattform portieren, werden Sie feststellen, wie groß das Problem sein kann, wenn Sie Hochleistungscode schreiben.

Zoner
quelle
+1, abhängige Lasten (Pointer Chasing) sind eine große Sache. Ein Cache-Miss verhindert, dass zukünftige Ladevorgänge überhaupt erst beginnen. Wenn viele Ladevorgänge gleichzeitig aus dem Hauptspeicher ausgeführt werden, ist die Bandbreite viel besser als bei einer Operation, bei der die vorherige vollständig ausgeführt werden muss.
Peter Cordes