|                                                                                                        |
[english] [index] [back] [mail]

 

Copyright © 2001 h-peter Recktenwald, Berlin
Unter Beachtung des allgemein geltenden Ausschlußvermerks frei zu beliebiger Verwendung bei nur kostenloser Weitergabe.

 

Grundlegendes zur Code-Optimierung bei K6/Pentium Processoren
im "protected" Modus, bei durchgängiger 32-bit-Adressierung.

Quellen

  1. "AMD K6-2 processor data sheet", Nr. 21850H/0, und "AMD-K6 Processor Code Optimization", Nr. 21924D/0.
  2. Zu den vergleichbaren Typen Intel Pentium (bis P-II) gibt es Entsprechendes, da aber dort im Text kein Hinweis auf die Dokumenten-Spezifikation gegeben wird (und ich die Quelle vergessen habe), hilft ggf. nur Suchen...
  3. "intel 'pentium' type cpu optimization", pentopt.html, von
  4. Beispiele in "nasm"/intel-Syntax. Eigene Versuche nur mit K6/2 von AMD, hier kurz "K6", die dafür und als Beispielsammlung herangezogene "lib4th" (Forth DLL in asm) ist verfügbar unter

Im wesentlichen zählen folgende Faktoren:

Erstmal:
Viel Glück, insofern, als die gerade herangezogene Dokumentation hält, was ihre Autoren versprechen; selbst in o.g. authentischen Unterlagen fanden sich Fehler! noch dazu in einer Form, die nicht gerade auf gehobene Sorgfalt bei Erstellung jener Texte schließen läßt (z.B. AMD 21924D/0). Secundaer-Quellen sind immer mit Vorsicht zu genießen, selbst wenn sie noch so sorgfältig zusammengestellt wurden, da sich dort auch Interpretationsfehler finden können - wovon ich trotz aller Bemühungen diesen Text keineswegs ausschließe.
Aus eigener (subjektiver!) Erfahrung sei vor allem auch vor dem Autorennamen "Floegel", den Verlagen "Elektor" und "Hofacker" gewarnt (wenn's die denn noch gibt), und vor den "Motorola"-Unterlagen.
  1. -> Sorgfalt, Sicherheit, profunde Erfahrung und grenzenlose Geduld
  2. -> "cache"-Treffer, Localität
  3. -> Anordnung von Daten & Code - "alignment"
  4. -> Einsprungs-Verzögerung - "first time penalty"
  5. -> Sprung-Vorhersage - "branch prediction"
  6. -> Befehls-Decodierung - "instruction fetch ..."
  7. -> Register-Verriegelung - "register stall"
  8. -> Abhängige Ketten - "dependency chains"
  9. -> Besondere Empfehlungen
  10. -> in beiden cpu-pipes ausfürbare Operationen

Im einzelnen:

  1. Trivia (Lyrik):

    1. Aufmerksamkeit und Pedanterie
      Die Code-Optimierung hat nichts Spektakuläres, sie ist in erster Linie mühsames und stumpfsinniges Pedantenwerk, das erst in der Summe vieler einzelner Maßnahmen zum u.U. recht eindrucksvollen Erfolg führt.
    2. Gewissenhaftigkeit
      auch wenn sowas nicht "angesagt" scheint - doch wer Assembly programmiert, wird sich ohnehin kaum nach irgendwelchen lächerlichen Conferenciers richten.
      Würden etwa Kraftfahrzeuge mit der jämmerlichen Berufsauffassung des gewöhnlichen Erzeugers von Weichware gebaut, hätte die unversehrt davongekommene Bevölkerung Orte wie Redroit oder Düsselsheim vermutlich längst dem Erdboden gleichgemacht... Will sagen, wenn auch "der gemeine Programmanwender" von kaum zu übertreffendem Leidenswillen geprägt scheint, ist ohne sichere Funktion jede "Optimierung" von Programmen reine Wahnvorstellung.
    3. Bereits während des Programmierens das Codierte richtig und den #Zweck# betreffend ausführlich beschreiben. Viele Fehler fallen sofort in's Auge, wenn man sein Tun zugleich konkret in Worte faßt. Nebenbei ergibt sich ziemlich mühelos auch noch eine brauchbare Dokumentation.
    4. "Selbstmodifizierender Code" zerstört jeden Nutzeffekt der betr. Processor-Caches.
    5. Subroutinen ordentlich abschließen, CALL und RET paarweise, ohne vorher im Return-Stack herumzufummeln.
    6. Widereintrittstauglicher Code ist auf der sicheren Seite, "hart" gegenüber Interrupts und im Multitasking.
    7. Positionsunabhängiger Code hat u.a. den Vorteil beliebiger Wiederverwendbarkeit in neuen Programmen; eine Sammlung sicherer, geprüfter Programmteile hilft ungemein.
    8. Verifikation: Nichts, rein garnichts muß richtig sein, nur weil irgendein "Experte" das abgesondert hat! Abgeschriebene Dokumente (wie dieses!) sind Hinweise, nicht "Wahrheit", selbst Herstellerunterlagen sind mitunter grauenvoll zusammengeschlampt.
    9. Den "primär-rechner" nicht vernachlässigen: "Denken" ist eine höchst effiziente Optimierungsmethode!
      Sorgfältige Programm-Planung erleichtert die anschließende Optimierung ungemein, und selbst raffinierteste "Optimierung" kann Fehler darin kaum ausgleichen. Dabei zählen nicht nur geistvolle Algorithmen, sondern vor allem auch Programmablauf und -Anordnung, bis hin zur Registerzuweisung. Sind die nicht halbwegs "optimal", gerät die mühsame Code-Optimierung von Hand bestenfalls zur Neutralisierung des ungeschickten Ansatzes ("C"!).

     

  2. Cache:

  3. Code-/Datenanordnung:

    gehen zusammen, da die Arbeit der Processor-Cache eng mit der Lage von Code und Daten - je getrennt - zusammenhängt.
    1. Code
      Einsprung möglichst auf 16-Byte-Grenze.
      Wahrung des möglichst engen Code-Zusammenhanges steht dem bei größeren Programmen u.U. entgegen. Die Ergebnisse hängen stark vom jeweiligen Programmaufbau ab. Meist genügt es offenbar schon, wenn etwa der Datenteil eines "call near" an einer 4-byte-Grenze beginnt und evtl. zusammen mit dem Op-Code-Byte innerhalb eines 32-Byte-Blocks: Mit K6 und "lib4th" ergaben größere Posten keinerlei Nutzen (s.u.), was jedoch vom jeweiligen Processor abhängt - die betr. Handbücher geben entspr. Auskunft.
      Da alle (mir bekannten) Assembler in dieser Hinsicht hoffnungslos veraltet sind und keine Möglichkeit "vorausschauender" Justierung bieten, hilft ggf. nur geduldige "Handarbeit".
    2. Localität
      ist ein allzuoft völlig vernachlässigter Faktor. Generell spielt der enge Zusammenhang aller Daten und Codeteile (je für sich) innerhalb des Speichers eine große Rolle. Er kann die Wirkung der Processor-"cache(s)" entscheidend fördern. Optimierung auf möglichst kurze Sprungcodierung wird dies unterstützen, ist jedoch gegenüber anderen Einflüssen eher von untergeordneter Bedeutung - wobei gezieltes Codieren der Länge einer Instruktion auch "kostenloses" Hilfsmittel zum Alignment ist.
      Beispiel "      lib4th": Mit Alignment 16 statt 4 für (nahezu) alle Einsprungstellen wächst der Codebereich um ca 10%; dabei wird zugleich die Programmausführung entgegen allen langläufigen Prognosen deutlich langsamer!
    3. Daten
      1. nicht direkt hinter auszuführendem Code anordnen (5.1).
      2. Für die Adressenjustierung wählt man das nächste auf eine Zweier-Potenz aufgerundete Vielfache der Postengröße, etwa "fword" (6 bytes) auf Alignment 8 gelegen. - Werte über 8 ohne zusätzlichen Vorteil.

     

  4. Einsprungsverzögerung:

    • CALL NEAR wird sehr schnell abgearbeitet (ein Takt) und mag Verwendung vieler kurzer Subroutinen nahelegen. Dabei ist abzuwägen, ob die beim Einsprung in u.U. "neuen" Code erfolgende Auffrischung der Processor-Cache (L1) das trotz der dadurch bedingten Verzögerung sinnvoll erscheinen läßt.

     

  5. Sprung-Vorhersage:

    1. Man lege hinter Sprüngen - wozu auch CALL und RET zählen - nur ausführbaren Code ab: Beim "op-code prefetching" nimmt der Processor sonst unbrauchbare Daten auf, deren Auswertung sinnlos die Decodierung durchläuft und den Ablauf entsprechend hemmt.
    2. SET benutzen, wenn dadurch eine Verzweigung vermieden werden kann (K6: SET erwies sich als sehr ungünstig!).
    3. CMOVE wie .2 (K6: nicht anwendbar).
    4. Sprung auf unmittelbar vorangehende Operation vermeiden.
    5. Sprünge überlegt anordnen:
      Zuerst gilt die "statische" Bewertung, d.h. der Zustand, in dem der Sprung noch nicht in der speziellen "branch prediction cache" verzeichnet ist. Ab Pentium II(?) stehen dort die jüngsten 16 Sprünge.
      • Statisch werden Sprünge richtig vorhergesagt
        1. als genommen, wenn sie unbedingt sind: CALL, JMP, RET
        2. wenn ein bedingter VORwärtsprung nicht genommen wird.
        3. wenn ein bedingter RÜCKwärtsprung genommen wird.
      • Dynamische Vorhersage ist richtig, wenn
        1. die statischen Richtlinien zutreffen
        2. der Ablauf der vier jüngsten Sprungbefehle einem regelmäßigen Muster folgt.
        3. besondere Muster eingehalten werden, s. Quelle 2.
      Diese Einflüsse sind nicht zu unterschätzen, auch hierzu gibt es in der "lib4th" ein überaus deutliches Beispiel: Die bitweise Division einer 128-Bit-Zahl durch eine 64-Bit-Zahl (Aufruf "uqd/mod") wurde ohne Veränderung im eigentlichen Code allein durch die günstigere Anordnung nur zweier bedingter Sprung-Paare um ca 10% schneller!
    6. CALL/RET
      beim K6 und ähnlichen Modellen ist der Rücksprung aus <CALL subroutine> selbst nach Stackmanipulationen mit RET deutlich schneller als mit JMP REG:
       POP ECX  ==>MOV ECX,[ESP]
       POP EDX  MOV EDX,[ESP+4]
       JMP ECX  MOV [ESP+4],ECX
          LEA ESP,[ESP+4]
          RET

     

  6. Befehls-Decodierung:

    1. Vorzugsweise Ein-Byte-Operationen verwenden, oder solche, die innerhalb eines Mikro-Zyklus verarbeitet werden (K6: "Risc86", Intel hat entsprechende Hinweise im Handbuch) Etwa INC und DEC statt ADD, SUB.
    2. Auf paarweise Ausführbarkeit, "op-code pairing", in beiden Recheneinheiten achten - Was auf die "Risc86" und (nahezu) alle sonstigen Ein-Byte-Operationen zutrifft. Ausnahmen s.u. Geeignete Anordnung (Reihenfolge) ist insbes bei solchen Operationen bedeutsam, die nur in einer der beiden Einheiten ausgeführt werden können. Welche das sind, ist den jeweiligen cpu-Handbüchern zu entnehmen (Processor-spezifisch).
    3. Möglichst keine Operationen einsetzen, die mehr als vier Mikro-Zyklen oder 7 Bytes Speicherplatz benötigen.
    4. LEA läßt sich oft außerordentlich effizient für einfache arithmetische Operationen verwenden - aber s. auch 8.4!
    5. Praefix hex 0F hat als einziges keine schädliche Wirkung. Und auch das nur, wenn die Befehlscodierung unter 8 Bytes bleibt. Bei K6 sind außerdem noch 66h und 67h unschädlich.
    6. Lesen/schreiben im selben Speicherblock (Vielfache von 4K) unmittelbar nacheinander nur in gleichgroßen Posten.
       d.h. MOV EAX,[MEM]  
         MOV EAX,[MEM+4]etc.
      Kontrolle z.B. durch
      			( abs ((mem1 & -32 ) - (mem2 & -32 )) mod 4096
      soll für volle L1-cache-Tauglichkeit Werte =/= 0 liefern, ist das Ergebnis Null, gilt obige Bedingung.
    7. Speicheradressen für die Daten-Ablage möglichst frühzeitig ermitteln, und auch beim Lesen nicht in der Operation selbst.

     

  7. Register-Verriegelung:

    1. Zusammen mit Verwendung eines Teil-Registers Zugriff auf ein größeres Format desselben Registers vermeiden
       z.B.XOR  EAX,EAXersetzen durch   MOVZX  EAX,BL
        MOV  AL,BL  
           
    2. Ein Zielregister sollte unmittelbar vorher nicht als Basisregister einer Operation verändert worden sein,
       z.B.SUB  ESP,12 
        PUSH EBP 

     

  8. Abhängige Ketten:

    • Ein Beispiel
        MOV  EAX,[MEM1] 
        ADD  EAX,[MEM2] 
        ADD  EAX,[MEM3] 
        ADD  EAX,[MEM4] 
        MOV  [MEM5],EAX 
      wo das zweite ADD erst ausgeführt werden kann, wenn das erste Ergebnis vorliegt. Bei ADD entsteht nur ein Takt Wartezeit, wogegen z.b. (I)MUL und (I)DIV weit größere "Strafzeiten" zur Folge haben können. Geeignete Anordnung vermeidet dergleichen. Im obigen Falle etwa Einfügen anderer einfacher MOV-Befehle, die später und hiervon unabhängig ggf. ohnehin benutzt würden. Oder Aufspaltung in mehrere Operations-Zweige:
        MOV  EAX,[MEM1]; erster zweig
        MOV  EBX,[MEM2]; zweiter zweig, anderer accu
        IMUL EAX,[MEM3] 
        IMUL EBX,[MEM4] 
        IMUL EAX,EBX ; zum schluß zweige verbinden
        MOV  [MEM5],EAX 

     

  9. Besondere Empfehlungen:

    • EAX ist (historisch bedingt, als "das" Accumulator-Register) in vielen Fällen vom Processor-Entwurf her begünstigt, d.h. einige erfahrungsgemäß besonders häufige Operationen erfahren bereits im Processor selbst eine gewisse Optimierung, die gerade darum sehr wirkungsvoll ausfallen kann, XOR oder TEST als Beispiele.
       
    • Einige Operationen, die nicht oder nur selten paarweise mit anderen ausgeführt werden können. Sonderfälle nicht berücksichtigt, ggf. s. Handbuch der betr. cpu:
      •  Operation(en) ersetzen durchOperation(en)
      1.  CDQ =>MOV EDX,EAX
            SAR EDX,31
        wobei der Ersatz für sich genommen dieselbe Zeit braucht, aber im Unterschied zu CDQ die gleichzeitige Ausführung mit andern OP-s ermöglicht.
         
      2.  CMP src,0 => TEST src,-1
           oderTEST reg,reg
        insbes. kann TEST eax,reg/imm paarig ausgeführt werden.
         
      3.  CPUID   
         EMMS   
         FEMMS   
         XCHG mem,reg  XCHG reg,mem  
         XLATE   
        nur verwenden, wo unvermeidich (hohe "Strafzeit", rsp. ineffizient)
         
      4.  LEA   
        ist anfällig auf "address generation interlock" oder "AGI stall", Verriegelung durch Warten auf das Ende der Adressenermittlung, und sollte weder auf Register angewandt werden, die unmittelbar zuvor verändert wurden, noch unmittelbar vor Operationen stehen, die das Ergebnis verarbeiten.
        So ist auch ein einzelnes STOSD keineswegs immer so "ineffizient" wie allgemein behauptet (K6, lib4th):
         STOSD   LEA EDI,[EDI+4]
         MOVZX AL,[EDI]  MOVZX AL,[EDI]
        STOSD & MOVZX wird hier in einem Takt ausgeführt rsp. abhängig vom vorangehenden Code auch ganz ohne Verzögerung, die Kombination mit LEA benötigt dagegen mindestens drei Takte.
         
      5.  MOV EAX,0  => XOR EAX,EAX
        s.o, EAX-Optimierung im Processor - evtl. cpu-abhängig
        K6: erste Form schneller, "immediate"-Werte sind stets sofort verfügbar!
         
      6.  MOVSX   
        möglichst vermeiden (nicht K6).
         
      7.  MOVZX   
        vorzugsweise verwenden, wenn dadurch eine Gruppe anderer Operationen ersetzt werden kann.
         
      8.  MOV reg,[ESP+disp]  => POP
         ...    
         ADD ESP,imed    
        sofern nicht mehr als 8 Bytes vom Stack geholt werden.
         
      9.  PUSH mem   
        Intel: generell vermeiden
        AMD  : PUSH mem spart ggf. eine Registeroperation ein, wird "short" ausgeführt und ist dem Umweg über ein Register vorzuziehen, hier ist POP mem der ungüstigere Fall, "vector"-codiert.
         
      10.  XLATE   
        existiert eher als Compatibilitäts-Fossil, außerordentlich ineffizient.
         
      11. K6:
         MOV [ESI],EAX => MOV [ESI+0],EAX
        Ziel-Adressierung "[ESI]" vermeiden.
        Wenn der betr. Assembler die Null weg"optimiert", hilft evtl. Hinschreiben in der Form
        • MOV [byte ESI+0],EAX

         
      12. (K6)
         XCHG src,reg => ADD src,reg
         oderXCHG reg,src  SUB reg,src
            ADD src,reg
            NEG reg
        Die Alternative wird in einem Sechstel der Zeit abgearbeitet (5 statt 33 Zyklen), wenn "src" im Speicher liegt; Zeit für reg,reg gleich (stets 2 Zyklen), dann aber mit anderen Operationen paarig ausführbar und ebenfalls ohne besondere Wartezeit:
         XCHG reg1,reg2 => LEA reg1,[reg1+reg2]
         oderXCHG reg2,reg1  SUB reg2,reg1
            LEA reg1,[reg1+reg2]
            NEG reg2
        Ersatz immer zweckmäßig, wo nur ein Processor existiert rsp. wenn die synchronisierende Eigenschaft des XCHG nicht erforderlich ist - und der Speicherbedarf nicht die absolut übergeordnete Rolle spielt.
         
      13. K6:
         SHL reg,1 => ADD reg,reg
        Schiebeoperationen nur "alux" rsp. "vector"-codiert,
        ADD arbeitet in beiden alu, paarig ausführbar (per byte-Register nur "alux").
         
      14.  TEST reg1,reg1 => TEST reg1,reg1
         MOV reg2,reg3 Jcc label
         Jcc label ...
         ... label:
         label:  MOV reg2,reg3
        Flag-Auswertung unmittelbar nach TEST spart einen Taktzyklus.
         
      15.  CMP reg,[mem] => CMP [mem],reg
        Die Alternative wird oft scheller ausgeführt. Auswertung anlog, mit complementären Flags. Allerdings, dies gilt keineswegs immer, ihr Einsatz sollte darum stets überprüft werden. Ansich wäre die erste Form optimal, da die damit verbundene "read-modify-write"-Operation dann ohne Speicher-Zugriff auskommt - soweit die Theorie...
         
      16. K6:
         STC  => OR reg, byte 1
            NEG reg
        CLC,CMC,STC kosten 'Strafzeit' von 1 rsp. 2(CMC) Takten, die Folge OR/NEG dagegen ist 'umsonst': OR stellt reg =/= 0 sicher, NEG erzeugt dann stets gesetztes Carry. Oder:
         STC  => NEG reg
            NEG reg
        Ist irgendein Register mit Wert =/= 0 sicher voraussetzbar, kann das C-Flag mit doppelter Negation gesetzt werden und der Registerwert bleibt unverändert.
        Für die anderen Konstellationen der Arithmetik-Flags lassen sich oft ähnliche Ersatzoperationen finden, die sämtlich schneller sind, als die direkte Änderung.
         CLC  => TEST reg,reg
        setzt NC und zugleich auch NO(verflow).
         
        Ohne Effekt war der CMC- oder STC-Ersatz nur bei derartigen Sequenzen:
            LEA reg,[mem]
            stosd
            NEG reg
            NEG reg
        ...was vermuten läßt, daß STC u.dgl. die 'AGI stall'-Lücke nach LEA füllen.
         

     

  10. -> in beiden cpu-pipes ausführbare Operationen
    • ADD
    • AND
    • CMP
    • DEC
    • INC
    • LEA
    • MOV - nicht mit ctrl/debug/segment-Registern
    • NOP
    • OR
    • POP - reg
    • PUSH - reg und imed
    • SUB
    • TEST - reg,reg; mem,reg; EAX,immediate
    • XOR

     

H.-Peter Recktenwald, Berlin, 5.Feb 2002

lhpk6opt.txt : 475