Welche Art von Optimierungen nehmen moderne Compiler vor?

Was tatsächlich gemacht wird, kann sich von Compiler zu Compiler Version ändern. Es gibt wenig "generelle", grosse Optimierungen, sondern viele kleine Dinge die getan werden. Es hängt auch ein bisschen von der Programmiersprache ab, je "höher" die Programmiersprache, desto mehr Optimierungspotential einsteht.

Relativ simple Optimierungen betreffen die Optimierung von mathematischen Operationen. Beispielsweise kann eine Division (oder Multiplikation) durch 2, 4, 8, 16, usw bei Ganzzahlen durch Bitverschiebung schneller gemacht werden:

x = y / 16 macht ein Compiler zu x = y >> 4.

Oder manche Rechnungen können bereits zur Kompilizierzeit vorgenommen werden: pi = 3.14159; u = 2 * pi * r wird zu u = 6.28318 * r. Sollte Pi in dem Programm später nicht mehr verwendet werden, dann wird der Compiler die Variable eliminieren.

Dann gibt es relativ viele Optimierungen die Schleifen betreffen:

for (i=0; i < 10; ++i) {
     a[i] = 17 * i;
 }

Kann der Compiler die (langsame) Multiplikation durch eine schnellere Addition ersetzen:

tmp = -17;
 for (i = 0; i < 10; ++i) {
     tmp = tmp + 17;
     a[i] = tmp;
 }

Gerade bei Schleifen mit fixer Grösser kann der Compiler dann auch die Schleife durch "Copy&Paste" ersetzen ("Loop unwinding"):

for( i=0 ; i<8 ; i=i+1 ) {
    dest[i] = src[i];
}

wird zu

dest[0] = src[0];
dest[1] = src[1];
dest[2] = src[2];
dest[3] = src[3];
dest[4] = src[4];
dest[5] = src[5];
dest[6] = src[6];
dest[7] = src[7];

Je nach dem kann der Compiler auch Dinge etwas umordnen. Beispielsweise:

u = (b + c) * x;
v = (b + c) * y;

wird der gemeinsame Teil rausgenommen und nur 1x berechnet, anstatt zweimal:

tmp = b + c;
u = tmp * x;
v = tmp * y;

Oder eine If-Abfrage in der Schleife die jedes mal das gleich funktioniert kann rausgenommen werden, so dass die Überprüfung nur einmal stattfindet:

int result = 0;
boolean do_plus = ...;
for( i=0 ; i<100 ; i=i+1 ) {
  if(do_plus == true) {
    result = result + i;
  } else {
    result = result - i;
  }
}

wird zu

int result = 0;
boolean do_plus = ...;
if(do_plus == true) {
  for( i=0 ; i<100 ; i=i+1 ) {
    result = result + i;
  }
} else {
  for( i=0 ; i<100 ; i=i+1 ) {
    result = result - i;
  }
}
}

Das sind ein paar (imho) anschauliche Beispiele, hab die meisten aus der Wikipedia geklaut: https://en.wikipedia.org/wiki/Optimizing_compiler

Die Liste von möglichen Optimierungen ist aber riesig, insbesondere auch wenn es um das Generieren von Maschinen- oder Bytecode geht.

• Auf Intel-Plattformen (x86) gibt es z.B. einen Maschinenbefehl der Addition und Multiplikation um 2,4,8 kombiniert: x = a * 4 + c kann in einem einzigen Assemblerbefehl gemacht werden, anstatt zwei (zuerst Multiplikation, dann Addition).
  
• Spezielle SSE-Instruktionen können verwendet werden, wenn der Compiler merkt dass die gleiche Opteration mehrmals ausgeführt wird:
  
  Code

  for (i=0; i<8; i++){
      a[i] = b[i] + c[i];
    }

  Anstatt da eine Schleife zu verwenden kann der Compiler da etwa dem Prozessor dank SSE-Instruktionen sagen, er solle alle 8 Rechnungen gleichzeitig ausführen, anstatt eine nach der anderen (nennt sich Schleifen Vektorisierung).

• In Programmiersprachen wie Java kann manchmal die Überprüfung wegfallen, ob ein Zugriff im Array ist, wenn der Compiler garantieren kann, dass dies nicht der Fall ist, so dass weniger Überprüfungscode ausgeführt werden muss.
  
• In Programmiersprachen mit bekannten Funktionen wie C kann der Compiler auch Funktionen strlen (Länge eines Strings berechnen) bereits zur Kompilierzeit ausführen, strlen("hallo") kann der Compiler ausrechnen dass das 5 ist, weil der String keine Variablen ist.
  
• Weitere Optimierungen wären etwa das Rauslöschen von Funktionen die niemals aufgerufen werden, oder Schleifen die niemals ausgeführt werden usw.
  
• In anderen Sprachen wo Rekursion wichtig kann der Compiler auch rekursive Funktionsaufrufe durch "Tail-Call-Optimization" wegoptimieren, damit die so schnell sind wie Schleifen.

Grundsätzlich gilt dass der Compiler häufig auch Dinge optimiert, wo der Mensch auch drauf gekommen wäre, also lieber mal eine Variable mehr verwenden wenn es den Code lesbarer macht.

Nachtrag: Eine leider etwas gar technische, aber kurze Übersicht findet auch in den LLVM-Dokus: http://llvm.org/docs/Passes.html

+1 für gandro

etwas OT: lohnt sich Loop Unrolling denn überhaupt in nennenswertem Umfang? also für zwei iterationen leuchtet mir das ja noch ein, aber den gesamten schleifenrumpf irgendwie 8x oder so zu replizieren bläßt den code doch ungemein auf und verschlechtert damit die cache-lokalität deutlich. bei moderenen sprungvorhersagen ist es doch bestimmt einfacher die schleife schleife sein zu lassen, sodass sie komplett im Cache abläuft und anderen Krams nicht verdrängt

Zitat von oreissig

etwas OT: lohnt sich Loop Unrolling denn überhaupt in nennenswertem Umfang? also für zwei iterationen leuchtet mir das ja noch ein, aber den gesamten schleifenrumpf irgendwie 8x oder so zu replizieren bläßt den code doch ungemein auf und verschlechtert damit die cache-lokalität deutlich. bei moderenen sprungvorhersagen ist es doch bestimmt einfacher die schleife schleife sein zu lassen, sodass sie komplett im Cache abläuft und anderen Krams nicht verdrängt

Glaube wo es der Compiler es darf, wird teilweise Loop-Unwinding auch gemacht um den Instruction Level Parallelism zu erhöhen:

for(i=0; i < 1000; i++) { 
  sum += a[i]
}

könnte ja mit Partial Loop Unwinding umgeschrieben werden als

for(i=0; i < 500 ; i+=2) { 
  sum1 += a[i];
  sum2 += a[i+1];
}
 sum = sum1 + sum2;

Erlaubt es dem Prozessor jetzt explizit zumindest zwei Additionen zu parallelisieren. Ich hab ehrlich gesagt aber keine Ahnung inwiefern sowas wirklich von Compilern gemacht wird (korrekt wäre es ja nur für Ints, nicht for Floats), oder ob Prozessoren evtl. inzwischen sogar in der Lage sind sowas selber zu erkennen.

Wobei ich mir auch vorstellen kann dass gerade solche Trade-Off Optimierungen (Cache vs. Branchprediction) auch schlicht sehr prozessorspezifisch sind.
Erinnere mich an ein Beispiel im GCC wo die Schleifenbedingung in while-Loops zweimal generiert wurde, einmal für die initiale Überprüfung, einmal für die Überprüfung während der Iteration, weil das dem Branch-Predictor vom P6 (Pentium Pro und aufwärts) besser gefallen hat. Wurde dann irgendwann aber geändert, weil spätere Intels sich da anders verhalten haben.

Zitat von oreissig

etwas OT: lohnt sich Loop Unrolling denn überhaupt in nennenswertem Umfang? also für zwei iterationen leuchtet mir das ja noch ein, aber den gesamten schleifenrumpf irgendwie 8x oder so zu replizieren bläßt den code doch ungemein auf und verschlechtert damit die cache-lokalität deutlich. bei moderenen sprungvorhersagen ist es doch bestimmt einfacher die schleife schleife sein zu lassen, sodass sie komplett im Cache abläuft und anderen Krams nicht verdrängt

In meiner Erfahrung: Wenn du MMX/SSE zum Vektorisieren kriegst haste halt je nach wordsize nen deutlich höheren Durchsatz (bei 128 bit halt 4 Instruktionen auf einmal, also fast Faktor 4 Speedup, das kann sich in engen inneren Loops durchaus lohnen). Loop unrolling bringt normalerweise nicht sooo arg viel, aber ich hab hier und da auch schon 10% damit rausgeholt.

Cache-Lokalität ist hier vllt auch der falsche Begriff, gerade wenn du den Code 8x replizierst gehst du da doch linear durch, also wenn das den Cache nicht freut

Zitat von friedrichheinze

Cache-Lokalität ist hier vllt auch der falsche Begriff, gerade wenn du den Code 8x replizierst gehst du da doch linear durch, also wenn das den Cache nicht freut

es gibt ja auch noch ein Leben nach der Schleife, und wenn der Cache leergeputzt ist, weil er komplett mit entrollter Schleife belegt ist, haste danach ordentlich Mrs.

Zitat von oreissig

etwas OT: lohnt sich Loop Unrolling denn überhaupt in nennenswertem Umfang? also für zwei iterationen leuchtet mir das ja noch ein, aber den gesamten schleifenrumpf irgendwie 8x oder so zu replizieren bläßt den code doch ungemein auf und verschlechtert damit die cache-lokalität deutlich. bei moderenen sprungvorhersagen ist es doch bestimmt einfacher die schleife schleife sein zu lassen, sodass sie komplett im Cache abläuft und anderen Krams nicht verdrängt

Gerade bei kleinen Loops bringt das extrem viel. Wenn du zB Videos oder Bilder dekodierst, sind die üblicherweise in Makroblocks unterteilt, was bedeutet dass du zwei verschachtelte Loops hast, die letztendlich in jeder Runder nur eine Handvoll Instruktionen ausführen. Ohne Unrolling hättest du enormen Overhead weil nach jeder Ausführung von zwei oder drei Instruktionen zuerst noch eine Manipulation an der Schleifenvariablen kommt dann ein GOTO, das dazu auch noch konditional ist. Im schlimmsten Fall schlägt also bei Blocks von 8x8 Pixeln die Branching Prediction des Prozessors mindestens alle acht Runden ins leere und die gesamte Pipeline muss ausgeräumt und neu aufgebaut werden. Von dem verbrauchten Cache ergibt sich kaum ein Unterschied, da Code bei dem sich das Unrolling lohnt meistens nur ein paar Instruktionen hat. Dazu kommt, dass der Overhead entfällt und bei diesem Beispiel je vier (oder noch mehr mit AVX/AVX2) Durchläufe in eine Instruktion gepackt werden können.

Zitat von oreissig

es gibt ja auch noch ein Leben nach der Schleife, und wenn der Cache leergeputzt ist, weil er komplett mit entrollter Schleife belegt ist, haste danach ordentlich Mrs.

Wenn es noch ein Leben nach der Schleife gibt das relevant ist dann optimierst du gerade am falschen Code

Zitat von niwax

Ohne Unrolling hättest du enormen Overhead weil nach jeder Ausführung von zwei oder drei Instruktionen zuerst noch eine Manipulation an der Schleifenvariablen kommt dann ein GOTO, das dazu auch noch konditional ist.

die Schleifenvariable muss ja auch im entrollten Zustand zwischen den einzelnen Schritten noch iteriert werden

Zitat von niwax

Im schlimmsten Fall schlägt also bei Blocks von 8x8 Pixeln die Branching Prediction des Prozessors mindestens alle acht Runden ins leere und die gesamte Pipeline muss ausgeräumt und neu aufgebaut werden.

dieser worst case ist sehr hypothetisch, selbst mit ganz einfachen heuristiken (z.B. Branches nach hinten werden genommen, branches nach vorn nicht) kriegt man da nur einen einzigen Miss beim Verlassen der Schleife. Effektiv ist die Branch Prediction heute aber um dimensionen über diesem trivialen Ansatz.

Zitat von niwax

Von dem verbrauchten Cache ergibt sich kaum ein Unterschied, da Code bei dem sich das Unrolling lohnt meistens nur ein paar Instruktionen hat.

Wie viel Platz belegt wird, hängt auch von der Anzahl der Schleifendurchläufe ab.

Vektorisierung hängt damit zwar zusammen, aber das meine ich hier nicht

Zitat von friedrichheinze

Wenn es noch ein Leben nach der Schleife gibt das relevant ist dann optimierst du gerade am falschen Code

na selbst in der Schleife ist das ja ein Unterschied, ob der Code im Cache liegt, oder so groß ist, dass er sich dauernd neue cache lines ausm RAM pullen muss

Zitat von oreissig

na selbst in der Schleife ist das ja ein Unterschied, ob der Code im Cache liegt, oder so groß ist, dass er sich dauernd neue cache lines ausm RAM pullen muss

1. Instruction prefetch
2. kannst ja ausrechnen wie lange du Instruktionen unrollen kannst bis du 64KB L1 ICache voll hast...

Zitat von oreissig

die Schleifenvariable muss ja auch im entrollten Zustand zwischen den einzelnen Schritten noch iteriert werden

Nein, da das Unrolling meistens nur geht, wenn die Grenzen der Schleife schon bekannt sind, können einfach die entsprechenden Zahlen eingesetzt werden. In diesem Beispiel können zB sogar auch Speicherzugriffe in der Tabelle vereinfacht werden.

for(x = 0; x < blocksize; x++)
                {
                    for(y = 0; y < blocksize; y++)
                    {
                        g += mb1.cb[i][j].data[x][y] * dctcos4[x][u][y][v];
                        g2 += mb1.cr[i][j].data[x][y] * dctcos4[x][u][y][v];
                        g3 += mb1.y[i][j].data[x][y] * dctcos4[x][u][y][v];
                    }
                }


wird zu 


g += mb1.cb[i][j].data[0][0] * dctcos4[0][u][0][v];
g2 += mb1.cr[i][j].data[0][0] * dctcos4[0][u][0][v];
g3 += mb1.y[i][j].data[0][0] * dctcos4[0][u][0][v];
...
g += mb1.cb[i][j].data[8][8] * dctcos4[8][u][8][v];
g2 += mb1.cr[i][j].data[8][8] * dctcos4[8][u][8][v];
g3 += mb1.y[i][j].data[8][8] * dctcos4[8][u][8][v];

Dabei spart man sich zwei Dereferenzierungen pro Zugriff und der Compiler kann sogar im voraus kleinere Puffer aus den Konstanten vorberechnen. Am Ende liegen auch nur 192 Multiplikationen im Cache.

Zitat von oreissig

Wie viel Platz belegt wird, hängt auch von der Anzahl der Schleifendurchläufe ab.

Natürlich, aber durch die kleine Größe wird der Cache dadurch bei weitem nicht voll. 64x256 Bit sind immer noch erst 2 KByte. Damit das dem Cache gefährlich wird, musst du schon auf ner sehr alten Architektur arbeiten.

selbst ein pentium 1 hat 16kb l1 cache

Zitat von niwax

Nein, da das Unrolling meistens nur geht, wenn die Grenzen der Schleife schon bekannt sind, können einfach die entsprechenden Zahlen eingesetzt werden.

achso ja in diesem Fall nicht, ich war in Gedanken noch in gandros beispiel, wo stattdessen die Anzahl der Iterationen dezimiert wird

Zitat von niwax

Damit das dem Cache gefährlich wird, musst du schon auf ner sehr alten Architektur arbeiten.

Interessanterweise hat sich der L1-Cache über die Zeit praktisch nie nennenswert erweitert. Die ganz allerersten CPUs, die überhaupt Caches hatten, hatten sowas kleines wie 512B, aber dann hat sich relativ schnell die Größenordnung 16-32kB für je Code und Daten etabliert.
Beim L2 war die Spanne zwar größer, aber auch da gabs vor 20 Jahren locker schon 2MB L2s. Das waren erst noch externe Chips, die erst im Laufe der Zeit aufs Package und dann aufs Die gewandert sind.

Ich muss hier gerade mal einen 180 pullen und oreissig recht geben: Auf Sandy Bridge und neuer sollte mal Loops wirklich nicht unrollen. Dort gibt es nämlich einen micro-op cache, der ca 1500 micro-ops speichert, und den sollte man echt sparsam einsetzen.

Wieder was gelernt

Zitat von friedrichheinze

Ich muss hier gerade mal einen 180 pullen und oreissig recht geben: Auf Sandy Bridge und neuer sollte mal Loops wirklich nicht unrollen. Dort gibt es nämlich einen micro-op cache, der ca 1500 micro-ops speichert, und den sollte man echt sparsam einsetzen.

Wieder was gelernt

Gentoo Wiki über „Optimierung“ mit -funroll-loops