Warum ist der Schleifenbefehl langsam? Konnte Intel es nicht effizient implementiert haben?

LOOP ( manueller Eintrag von Intel ref ) dekrementiert ecx / rcx und springt dann, wenn er nicht Null ist . Es ist langsam, aber konnte Intel nicht billig es schnell gemacht haben? dec/jnz verschmilzt bereits zu einem einzigen Uop der Sandybridge-Familie; Der einzige Unterschied ist, dass das Flags setzt.

loop auf verschiedenen Mikroarchitekturen, von Agner Fogs statementstabellen :

  • K8 / K10: 7 m-ops
  • Bulldozer-Familie / Ryzen : 1 m-op (gleiche Kosten wie macro-fusionierter Test-and-Branch, oder jecxz )

  • P4: 4 Ups (dasselbe wie jecxz )

  • P6 (PII / PIII): 8 Ups
  • Pentium M, Core2: 11 Stück
  • Nehalem: 6 Ups. (11 für loope / loopne ). Durchsatz = 4c ( loop ) oder 7c ( loope/ne ).
  • SnB-Familie : 7 Ups. (11 für loope / loopne ). Durchsatz = einer pro 5 Zyklen , so viel wie ein Flaschenhals, wie Sie Ihren Schleifenzähler im Speicher halten! jecxz ist nur 2 Ups mit dem gleichen Durchsatz wie normale jcc
  • Silvermont: 7 Ups
  • AMD Jaguar (Low-Power): 8 Ups, 5c Durchsatz
  • Via Nano3000: 2 Stück

Könnten die Decoder nicht gleich lea rcx, [rcx-1] wie lea rcx, [rcx-1] / jrcxz ? Das wären 3 Ups. Zumindest wäre das bei keinem Präfix der Adressgröße der Fall, andernfalls muss ecx und RIP auf EIP abgeschnitten werden, wenn der Sprung ausgeführt wird. vielleicht erklärt die seltsame Wahl der Adressgröße, die die Breite des Dekrements steuert, die vielen Ups?

Oder besser, dekodieren Sie es einfach als einen fusionierten Dec-and-Branch, der keine Flags setzt? dec ecx / jnz auf SnB dekodiert zu einem einzigen Uop (der Flags setzt).

Ich weiß, dass echter Code es nicht benutzt (weil es seit mindestens P5 oder so langsam war), aber AMD entschied, dass es sich gelohnt hat, es für Bulldozer schnell zu machen. Wahrscheinlich weil es einfach war.


  • Wäre es für die SnB-Familie leicht, eine schnelle loop zu haben? Wenn ja, warum nicht? Wenn nicht, warum ist es schwer? Viele Decoder-Transistoren? Oder zusätzliche Bits in einem fusionierten Dec & Branch-UOP, um aufzuzeichnen, dass es keine Flags setzt? Was könnten diese 7 Ups tun? Es ist eine wirklich einfache statement.

  • Was ist das Besondere an Bulldozer, das eine schnelle loop einfach gemacht hat? Oder hat AMD eine Reihe von Transistoren verschwendet, um loop schnell zu machen? Wenn dem so war, dachte vermutlich jemand, dass es eine gute Idee war.


Wenn die loop schnell wäre , wäre sie perfekt für adc Loops mit BigInteger- adc , um adc / Verlangsamungen bei adc zu vermeiden (siehe meine Kommentare zu meiner Antwort), oder in jedem anderen Fall, in dem man ohne Flags Schleifen machen möchte. Es hat auch einen geringen Code-Größenvorteil gegenüber dec/jnz . (Und dec/jnz nur Macro-Fuses auf SnB-Familie).

Bei modernen CPUs, bei denen dec/jnz in einer ADC-Schleife in Ordnung ist, wäre die loop immer noch für ADCX / ADOX-Schleifen geeignet (um OF zu erhalten).

Wenn die loop schnell gewesen wäre, würden Compiler sie bereits als Guckloch-Optimierung für Code-Größe + Geschwindigkeit auf CPUs ohne Makro-Fusion verwenden.


Es würde mich nicht davon abhalten, mich bei all den Fragen mit schlechtem 16-Bit-Code zu ärgern, der loop für jede Schleife verwendet, selbst wenn sie auch einen anderen Zähler innerhalb der Schleife benötigen. Aber es wäre zumindest nicht so schlimm.

Jetzt, nachdem ich meine Frage gegoogelt hatte, stellte sich heraus, dass es sich um ein exaktes Duplikat von einem auf comp.arch handelte , das sofort auftauchte. Ich habe erwartet, dass es schwer zu googlen (viele “warum ist meine Schleife langsam” Treffer), aber mein erster Versuch ( why is the x86 loop instruction slow ) hat Ergebnisse.

Dies ist keine gute oder vollständige Antwort.

Es könnte das Beste sein, was wir bekommen, und es wird reichen müssen, wenn nicht jemand mehr Licht darauf casting kann. Ich habe mich nicht dazu entschlossen, dies als Antwort-Frage-Post zu schreiben.


Gute Beiträge mit verschiedenen Theorien in diesem Thread:

Robert

LOOP wurde bei einigen der frühesten Maschinen (ca. 486) langsam, als ein signifikantes Pipelining begann, und es war technologisch unpraktisch, nur die einfachste statement in der Pipeline auszuführen. So war LOOP für eine Reihe von Generationen langsam. Also hat niemand es benutzt. Als es dann möglich wurde, die Geschwindigkeit zu erhöhen, gab es keinen wirklichen Anreiz, dies zu tun, da niemand es tatsächlich benutzte.


Anton Ertl :

IIRC LOOP wurde in einigen Software für Zeitschleifen verwendet; Es gab (wichtige) Software, die auf CPUs nicht funktioniert hat, wo LOOP zu schnell war (das war in den frühen 90ern oder so). CPU-Hersteller haben also gelernt, LOOP langsam zu machen.


(Paul und alle anderen: Gern kannst du deine eigenen Texte als deine eigene Antwort veröffentlichen. Ich werde sie aus meiner Antwort entfernen und dir deine Stimme geben.)

@Paul A. Clayton (gelegentlich SO-Poster und CPU-Architektur-Typ) schätzte, wie man so viele Uops verwenden könnte . (Das sieht wie loope/ne die sowohl den Counter als auch ZF überprüft):

Ich könnte mir eine möglicherweise sinnvolle 6-μop-Version vorstellen:

 virtual_cc = cc; temp = test (cc); rCX = rCX - temp; // also setting cc cc = temp & cc; // assumes branch handling is not // substantially changed for the sake of LOOP branch cc = virtual_cc 

(Beachten Sie, dass dies 6 Ups sind, nicht Snb’s 11 für LOOPE / LOOPNE, und es ist eine totale Schätzung, die nicht einmal versucht, irgendetwas zu berücksichtigen, das von SnB perf Indikatoren bekannt ist.)

Dann sagte Paulus:

Ich stimme zu, dass eine kürzere Sequenz möglich sein sollte, aber ich habe versucht, an eine aufgeblähte Sequenz zu denken, die Sinn machen könnte, wenn minimale mikroarchitektonische Anpassungen erlaubt wären.

Zusammenfassung: Die Entwickler wollten, dass die loop nur über Mikrocode unterstützt wird, ohne irgendwelche Anpassungen an die Hardware vorzunehmen.

Wenn ein unbrauchbarer Nur-Kompatibilitäts-Befehl an die Mikrocode-Entwickler übergeben wird, können sie vernünftigerweise nicht in der Lage oder bereit sein, geringfügige Änderungen an der internen Mikroarchitektur vorzuschlagen, um einen solchen Befehl zu verbessern. Sie würden nicht nur ihr “Änderungsvorschlagskapital” produktiver nutzen, sondern der Vorschlag einer Änderung für einen nutzlosen Fall würde die Glaubwürdigkeit anderer Vorschläge verringern.

(Meine Meinung: Intel macht es wahrscheinlich immer noch langsam und hat sich nicht die Mühe gemacht, ihren Mikrocode für eine lange Zeit neu zu schreiben. Moderne CPUs sind wahrscheinlich zu schnell für alles, was loop auf naive Weise benutzt, um richtig zu funktionieren.)

… Paul fährt fort:

Die Architekten hinter Nano haben vielleicht herausgefunden, dass die Vermeidung des speziellen Gehäuses von LOOP ihr Design in Bezug auf Fläche oder performance vereinfacht hat. Oder sie haben möglicherweise Anreize von eingebetteten Benutzern erhalten, um eine schnelle Implementierung bereitzustellen (für Codedichte-Vorteile). Das sind nur wilde Vermutungen.

Wenn die Optimierung von LOOP aus anderen Optimierungen herausfiel (wie Fusion von Vergleich und Verzweigung), könnte es einfacher sein, LOOP in einen Fast-Path-Befehl zu ändern, als in Mikrocode, selbst wenn die performance von LOOP unwichtig wäre.

Ich vermute, dass solche Entscheidungen auf spezifischen Details der Implementierung basieren. Informationen über solche Details scheinen nicht allgemein verfügbar zu sein, und die Interpretation solcher Informationen würde über das Qualifikationsniveau der meisten Menschen hinausgehen. (Ich bin kein Hardware-Designer – und habe noch nie einen im Fernsehen oder in einem Holiday Inn Express gespielt. 🙂


Der Thread ging dann in den Bereich von AMD, in dem AMD unsere einzige Chance verpasste, den Cruft in der x86-Instruktionscodierung aufzuräumen. Es ist schwer, ihnen die Schuld zu geben, da jede Änderung ein Fall ist, in dem die Decoder keine Transistoren teilen können. Und bevor Intel x86-64 annahm, war noch nicht einmal klar, ob es sich durchsetzen würde. AMD wollte seine CPUs nicht mit Hardware belasten, die niemand verwendete, wenn AMD64 sich nicht durchsetzen konnte.

Aber trotzdem, es gibt so viele kleine Dinge: setcc könnte auf 32Bits geändert haben. (Normalerweise müssen Sie xor-zero / test / setcc verwenden, um falsche Abhängigkeiten zu vermeiden, oder weil Sie eine null-erweiterte Registrierung benötigen). Shift könnte bedingungslos geschriebene Flags haben, sogar mit einer Nullverschiebungszählung (die Eingabedatenabhängigkeit von eFlags für eine Verschiebung mit variabler Anzahl für eine OOO-Ausführung wird entfernt). Das letzte Mal, als ich diese Liste von Pet Peeves getippt habe, denke ich, dass es eine dritte gab … Oh ja, bt / bts usw. mit Speicheroperanden hat die Adresse abhängig von den oberen Bits des Index (Bitstring, nicht nur Bit innerhalb ein Maschinenwort).

bts statementen sind sehr nützlich für Bit-Feld-Sachen und sind langsamer als sie sein müssen, also möchten Sie fast immer in ein Register laden und dann das verwenden. (Es ist normalerweise schneller, eine Maske zu verschieben, um selbst eine Adresse zu erhalten, anstatt 10 uop bts [mem], reg auf Skylake, zu verwenden, aber es erfordert zusätzliche statementen. Also war es sinnvoll bei 386, aber nicht bei K8). Atom-Bit-Manipulation muss die Speicher-Ziel-Form verwenden, aber die Locked-Version benötigt sowieso viele Ups. Es ist immer noch langsamer, als wenn es nicht auf das dword zugreifen könnte, auf dem es dword .

Bitte lesen Sie den schönen Artikel von Abrash, Michael, veröffentlicht in Dr. Dobbs Journal März 1991 v16 n3 p16 (8): http://archive.gamedev.net/archive/reference/articles/article369.html

Die Zusammenfassung des Artikels lautet wie folgt:

Das Optimieren des Codes für Mikroprozessoren 8088, 80286, 80386 und 80486 ist schwierig, da die Chips signifikant unterschiedliche Speicherarchitekturen und Befehlsausführungszeiten verwenden. Der Code kann nicht für die 80×86-Familie optimiert werden. Vielmehr muss Code so entworfen werden, dass er auf einer Reihe von Systemen eine gute performance erbringt oder für bestimmte Kombinationen von processoren und Speicher optimiert ist. Programmierer müssen die ungewöhnlichen statementen vermeiden, die von der 8088 unterstützt werden, die ihre performancesfähigkeit in nachfolgenden Chips verloren haben. String-statementen sollten verwendet werden, sind aber nicht verlässlich. Es sollten Register anstelle von Speicheroperationen verwendet werden. Die Verzweigung ist auch für alle vier processoren langsam. Speicherzugriffe sollten ausgerichtet werden, um die performance zu verbessern. Im Allgemeinen erfordert die Optimierung eines 80486 genau die entgegengesetzten Schritte wie die Optimierung eines 8088.

Mit “ungewöhnlichen statementen, die vom 8088 unterstützt werden” meint der Autor auch “Schleife”:

Jeder 8088-Programmierer würde instinktiv DEC CX JNZ LOOPTOP durch: LOOP LOOPTOP ersetzen, da LOOP beim 8088 deutlich schneller ist. LOOP ist auch beim 286 schneller. Beim 386 ist LOOP jedoch tatsächlich zwei Zyklen langsamer als DEC / JNZ. Das Pendel schwingt noch weiter auf der 486, wo LOOP etwa doppelt so langsam ist wie DEC / JNZ – und wir denken darüber nach, was ursprünglich die offensichtlichste Optimierung im gesamten 80×86-Befehlssatz war.

Dies ist ein sehr guter Artikel und ich empfehle es sehr. Obwohl es 1991 veröffentlicht wurde, ist es heute überraschend relevant.

Aber dieser Artikel gibt nur Ratschläge, er ermutigt, die Ausführungsgeschwindigkeit zu testen und schnellere Varianten zu wählen. Es erklärt nicht, WARUM einige Befehle sehr langsam werden, so dass es Ihre Frage nicht vollständig anspricht.

Die Antwort ist, dass frühere processoren, wie 80386 (1985 veröffentlicht) und vorher, nacheinander Befehle nacheinander ausgeführt haben.

Spätere processoren haben begonnen, Befehls-Pipelining zu verwenden – anfänglich einfach für 804086, und schließlich brachte Pentium Pro (veröffentlicht 1995) radikal verschiedene interne Pipelines mit der Bezeichnung Out Of Order (OOO) -core, wo Befehle in kleine Fragmente umgewandelt wurden von Operationen, die Mikro-Ops oder μops genannt werden, und dann wurden alle Mikro-Ops verschiedener Befehle in einen großen Pool von Mikro-Ops gebracht, wo sie gleichzeitig ausgeführt werden sollten, solange sie nicht voneinander abhängen. Dieses Prinzip der OOO-Pipeline wird auf modernen processoren fast unverändert beibehalten. In diesem brillanten Artikel finden Sie weitere Informationen zum Befehl Pipelining: https://www.gamedev.net/resources/_/technical/general-programming/a-journey-through-the-cpu-pipeline-r3115

Um das Chip-Design zu vereinfachen, entschied sich Intel dafür, processoren so zu bauen, dass eine statement sehr effizient in Mikro-Operationen umgewandelt wurde, während andere dies nicht waren.

Eine effiziente Umwandlung von Befehlen zu Mikro-Ops erfordert mehr Transistoren, so dass Intel beschlossen hat, Transistoren zu speichern, was eine langsamere Decodierung und die Ausführung einiger “komplexer” oder “selten verwendeter” Befehle kostet.

Im Handbuch “Intel® Architecture Optimization Reference Manual” ( http://download.intel.com/design/PentiumII/manuals/24512701.pdf) wird beispielsweise Folgendes erwähnt: “Vermeiden Sie die Verwendung komplexer statementen (z. B.” Enter “,” Leave “oder” Loop “) ) die im Allgemeinen mehr als vier μops haben und mehrere Zyklen zum Decodieren benötigen. Verwenden Sie stattdessen Sequenzen einfacher statementen. ”

Also, Intel hat irgendwie entschieden, dass die “Schleife” statement “komplex” ist, und seitdem wurde es sehr langsam. Es gibt jedoch keine offizielle Intel-Referenz zur Aufteilung der statementen: Wie viele Mikro-Ops pro Befehl erzeugt werden und wie viele Zyklen benötigt werden, um sie zu dekodieren.

Sie können auch über die Out-of-Order Execution Engine im “Intel® 64 and IA-32 Architectures Optimization Reference Manual” http://www.intel.com/content/dam/www/public/us/en/ nachlesen. Dokumente / Handbücher / 64-ia-32-architectures-optimization-manual.pdf Abschnitt 2.1.2.