From leitner@convergence.de Tue May 29 12:44:50 2001
Date: Tue, 29 May 2001 12:44:50 +0200
From: Felix von Leitner <leitner@convergence.de>
To: developers@convergence.de
Subject: Optimizing with gcc 101
Message-ID: <20010529124450.A6788@convergence.de>
Mail-Followup-To: developers@convergence.de
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
User-Agent: Mutt/1.3.16i
Status: RO
Content-Length: 10775
Lines: 273

Wer sich schonmal gcc-generierten Assembler-Code angeschaut hat, war
wahrscheinlich beeindruckt.  Wer das noch nicht getan hat, für den mach
ich das hier mal eben stellvertretend:

  $ cat > t.c
  int foo(int bar) {
    return bar*7;
  }
  $ gcc -O3 -fomit-frame-pointer -S t.c
  $ cat t.s
  [...]
  foo:
        movl 4(%esp),%eax
	sall $3,%eax
	subl 4(%esp),%eax
	ret
  [...]
  $

Was tut dieser Code?  Er bewegt bar in das Register %eax (movl), shiftet
das Register um drei Bits nach links (sall) und zieht vom Ergebnis ein
bar ab.  Das ist ausgesprochen beeindruckend für einen Compiler, weil er
erkannt hat, daß hier keine Multiplikation notwendig ist, sondern das
mit einfacheren (d.h. schneller ausführbaren) Befehlen machbar ist.  Ein
shift um drei Bits ist äquivalent zu einer Multiplikation mit 8, d.h.
der Compiler hat hier eine arithmetische Optimierung gemacht.

Die meisten Leute, die das sehen, glauben gcc ab sofort, daß er einen
perfekten Optimizer hat und schreiben ihre Code ab dann frei nach
Schnauze.  gcc wird's schon richten.  Richtig?  Falsch!

Das Beispiel oben fällt in die Kategorie "peephole Optimization", d.h.
kleine, sehr lokale Codefragmente.  Nehmen wir mal als anderes Beispiel
folgende Routine:

  $ cat > t.c
  void copy(char* dest,const char* source,unsigned int length) {
    int i;
    for (i=0; i<length; i++)
      dest[i]=source[i];
  }


Und hier ist mein Meßprogramm:

  $ cat > t1.c
  #include <stdio.h>

  #define rdtscl(low) \
      __asm__ __volatile__ ("rdtsc" : "=a" (low) : : "edx")

  main() {
    char buf[100];
    long a,b,c;
    rdtscl(a);
    copy(buf,"frobnicate",50);
    rdtscl(b);
    copy(buf,"frobnicate",50);
    rdtscl(c);
    printf("first took %lu cycles, second took %lu cycles\n",b-a,c-b);
  }
  $ gcc -O3 -fomit-frame-pointer -o t t.c t1.c
  $ ./t
  first took 234 cycles, second took 208 cycles
  $

Wie man sieht, eine relativ überschaubare Routine, die einfach n Bytes
kopiert.  Ich rufe sie zweimal auf, weil das erste Mal die Daten noch
nicht im Cache sind.  Jetzt versuchen wir mal, die Routine zu
optimieren.

  $ cat > t.c
  void copy(char* dest,const char* source,unsigned int length) {
    while (length--)
      *dest++=*source++;
  }
  $ gcc -O3 -fomit-frame-pointer -o t t.c t1.c
  $ ./t
  first took 287 cycles, second took 256 cycles
  $

Ui!  Ist sogar langsamer geworden!  Klar, man kann jetzt argumentieren,
daß der gcc-Optimizer halt cool ist und die erste Variante toll
optimiert hat, aber wäre der Optimizer wirklich cool, wären beide
Varianten gleich schnell.

Wir testen weiter:

  $ cat > t.c
  void copy(char* dest,const char* source,unsigned int length) {
    ++length;
    while (--length)
      *dest++=*source++;
  }
  $ gcc -O3 -fomit-frame-pointer -o t t.c t1.c
  $ ./t
  first took 236 cycles, second took 205 cycles
  $

Seht mal genau hin.  Die einzige Transformation, die ich gemacht habe,
ist daß ich das Postinkrement von length zu einem Preinkrement gemacht
habe!  Ich habe sogar Code einfügen müssen, damit das Programm noch
richtig arbeitet.  Trotzdem ist das Ergebnis deutlich schneller.  Warum?
Überlegt euch doch mal, was Postinkrement tut.  Es liest den Wert der
Variablen, zählt eins drauf, aber liefert den alten Wert.  Normalerweise
gibt gcc ein Register dafür aus, diese Variable zu beinhalten.  Wenn er
eins draufgezählt hat, ist also der alte Wert nicht mehr in dem
Register.  Wenn man mit dem alten Wert also irgend etwas kompizierteres
tut als ihn mit einer Konstanten zu vergleichen, muß gcc entweder ein
Register verschwenden, oder am Ende wieder 1 abziehen/draufzählen.
Beides verschwendet eine Instruktion und einen Taktzyklus.  gcc ist
intelligent genug, beim Vergleich mit einer Konstanten (wie hier mit
Null) die Konstante zu verändern, d.h. in diesem Fall mit -1 zu
vergleichen.  Aber bei Fällen wie

  foo(source++);

wenn foo() extern und nicht inline ist bleibt gcc gar nichts übrig.

Ist das auf allen Architekturen so?  Nein.  Auf manchen Architekturen
gibt es z.B. eingebautes Postinkrement.  68k ist ein Beispiel für sowas.
Auf RISC-Architekturen gibt es gewöhnlich ausreichend viele Register, um
mal eben einen Zwischenwert zu speichern, weil die Prozeduren zu klein
sind, als das der Compiler anständig Register vergeben könnte.


Wenn man auf PowerPC ein paar Messungen macht, stellt man fest, daß
selbst mit Präinkrement obiger Code nicht schneller ist als die naive
Implementation "for (i=0; i<length; i++) dest[i]=source[i];".  Warum?
Weil "Strength Reduction" eine seit Jahrzehnten bekannte und
wohlverstandene Optimierungstechnik ist.  Die Multiplikation hier kann
gcc erkennen und von sich aus in die Variante mit Zeigerarithmetik
umwandeln.

Bleibt also zusammenfassend die Aussage, daß Zeigerarithmetik nur in
Ausnahmefällen für schnelleren Code sorgt (und der Unterschied ist auch
dann nur marginal).  Zeigerarithmetik sorgt aber häufig für schlechtere
Lesbarkeit, weshalb ich empfehle, im Zweifelsfall lieber auf
Zeigerarithmetik zu verzichten, und in jedem Fall ein Meßprogramm zu
benutzen, um zu schauen, ob der Performancegewinn lohnt.

Wenn ich jetzt in euch den Eindruck erweckt habe, daß sich
Hand-Optimierungen generell nicht lohnen, dann ist das auch falsch.  Es
gibt drei Klassen von Optimierungen, mit denen man den gcc-Optimizer
deutlich deklassieren kann:

  1. Schnellerer Algorithmus
     Zuerst muß man sich über das Problem und die für die Laufzeit
     kritischen Bereiche im Klaren sein.  Dann wählt man an den
     zeitkritischen Bereichen den schnellsten bekannten und an den
     anderen Bereichen den kleinsten/einfachsten Algorithmus.
     Will sagen: nicht immer einfach qsort zum Sortieren benutzen.
  2. "Hirn einschalten"
     Arithmetische Optimierungen kann gcc nur durchführen, wenn
     mit Konstanten gerechnet wird, d.h. "mal sieben".  Sachen wie die
     Alpha-Channel Optimierung, die ich bei DirectFB neulich gemacht
     habe, kann gcc nicht leisten.  Ich nutzte dabei aus, daß man mehr
     als eine 8-Bit Zahl auf einmal mit der gleichen anderen 8-Bit Zahl
     multiplizieren kann, indem man sie in eine 32-Bit Zahl tut und
     zwischen ihnen ein paar Bits Platz läßt.
  3. Loop Unrolling
     Diese Transformation ist "halbmechanisch" durchführbar, und gcc hat
     auch einen Schalter dafür (-funroll-loops), der aber nicht wirklich
     toll funktioniert.  Weiteres erkläre ich weiter unten.

Hier ist eine Variante der obigen Funktion mit Loop Unrolling:

  $ cat > t.c
  void copy(char* dest,const char* source,unsigned int length) {
    ++length;
    while (length>4) {
      dest[0]=source[0];
      dest[1]=source[1];
      dest[2]=source[2];
      dest[3]=source[3];
      length-=4; source+=4; dest+=4;
    }
    while (--length)
      *dest++=*source++;
  }
  $ gcc -O3 -fomit-frame-pointer -o t t.c t1.c
  $ ./t
  first took 240 cycles, second took 159 cycles
  $

Wir haben uns gerade von 205 auf 159 Zyklen verbessert!  Und es geht sogar noch
einen Tick schneller.  Die Schleife am Ende muß nicht über eine Schleife
realisiert werden, weil wir ja genau wissen, daß höchstens noch drei
Bytes zu kopieren sind.  Die folgende Syntax ist an das berüchtigte
"Duff's Device" angelehnt und auf den ersten Blick unklar.  Tip:
Beachtet, daß keine break-Statements da sind.

  $ cat > t.c
  void copy(char* dest,const char* source,unsigned int length) {
    while (length>3) {
      dest[0]=source[0];
      dest[1]=source[1];
      dest[2]=source[2];
      dest[3]=source[3];
      length-=4; source+=4; dest+=4;
    }
    switch (length) {
    case 3: dest[2]=source[2];
    case 2: dest[1]=source[1];
    case 1: dest[0]=source[0];
    }
  }
  $ gcc -O3 -fomit-frame-pointer -o t t.c t1.c
  $ ./t
  first took 233 cycles, second took 145 cycles
  $

Wieso läuft dieser Code denn jetzt schneller ab?  Das Unrolling ist
schneller, weil man pro Schleifendurchlauf sechs Pointer-Änderungen,
drei length-Dekrements und drei Vergleiche zwischen length und Null
spart.  Und, am wichtigsten, man spart Sprünge.  Vergleiche und Sprünge
sind bei heutigen Prozessoren der übelste Performance-Killer, noch
schlimmer als Speicherzugriffe.  Prozessoren führen Befehle heute in
einer Pipeline aus, d.h. während der Prozessor einen Opcode anschaut,
läd er schon den nächsten Opcode aus dem Speicher.  Prozessoren mit sehr
hoher Taktrate haben gewöhnlich auch sehr viele Pipeline-Schritte.  Der
Athlon hat 10 Pipeline-Schritte, der PowerPC sechs (ich spreche nur von
den Integer-Befehlen, die Floating-Point Befehle haben deutlich längere
Pipelines).  Die Krone schießt der Pentium 4 mit 20 (!) Schritten ab.
Wenn ein Sprung genommen wird, von den der Prozessor glaubte, daß er
nicht genommen werden würde, dann fällt dem Prozessor das auf, nachdem
er schon n nachfolgende Befehle angefangen hat auszuführen.  Diese
Befehle müssen dann alle rausgeschmissen werden und das führt zu einer
Verzögerung von zwei-drei oder bis zu 10 Takten.  Daher haben heutige
Prozessoren monströse Vorhersage-Tabellen, mit denen sie sich merken, ob
ein Sprung das letzte Mal genommen wurde oder nicht.  Das hilft auch
enorm, aber ein falsch vorhergesagter Sprung ist immer noch der
schlimmste Performance-Killer.  Wenn wir in sehr engen Schleifen wie
unserer Beispiel-Schleife oben also Sprünge sparen können,
dann hilft das deutlich.

Auf dem PowerPC kosten richtig vorhergesagte Sprünge überhaupt keine
Prozessorzeit.  Das ist ein Alleinstellungsmerkmal des PowerPC.  Auch
falsch vorhergesagte Sprünge sind nicht so teuer, weil die Pipelinetiefe
nicht so groß ist.  Trotzdem hilft Unrolling auch auf dem PowerPC
deutlich.  Das liegt daran, daß der Compiler bei längeren Codefragmenten
Befehle umstellen kann.  Wenn ein gelesener Wert direkt nach dem Lesen
geschrieben wird, dann kann der Compiler nur Code wie diesen hier
generieren:

  LADE nach Register 0
  SCHREIBE aus Register 0

Der Prozessor macht dann vor dem Ausführen des Schreiben-Befehles Pause,
bis das zu ladende Wort tatsächlich vorliegt.  Das dauert mindestens
einen Takt, wenn das Wort im Cache ist.  Beim Unrolling-Fall kann der
Compiler also besseren Code generieren:

  LADE nach Register 0
  LADE nach Register 1
  LADE nach Register 2
  LADE nach Register 3
  SCHREIBE aus Register 0
  SCHREIBE aus Register 1
  SCHREIBE aus Register 2
  SCHREIBE aus Register 3

Hier hat der Prozessor also andere Lade-Befehle in die Pause geschoben,
bis das erste Wort geladen ist.  Das nennt sich Scheduling und es
funktioniert bei Prozessoren mit vielen Registern (d.h. RISC) viel
besser als bei Intel-Prozessoren.

Ich hoffe, diese Ausführungen helfen euch, effizienteren Code zu
schreiben (und keine Zeit mit unnötigen Optimierungen zu verbringen).
Ich würde mich freuen, wenn ich auch mal etwas Feedback auf mein
Geschreibsel kriegen würde...

Felix