Ich habe 2009 zum ersten Mal festgestellt, dass GCC (zumindest bei meinen Projekten und auf meinen Maschinen) die Tendenz hat, merklich schnelleren Code zu generieren, wenn ich für Größe ( -Os) anstelle von Geschwindigkeit ( -O2oder -O3) optimiere , und ich habe mich seitdem gefragt, warum.
Ich habe es geschafft, (ziemlich albernen) Code zu erstellen, der dieses überraschende Verhalten zeigt und klein genug ist, um hier veröffentlicht zu werden.
const int LOOP_BOUND = 200000000;
__attribute__((noinline))
static int add(const int& x, const int& y) {
return x + y;
}
__attribute__((noinline))
static int work(int xval, int yval) {
int sum(0);
for (int i=0; i<LOOP_BOUND; ++i) {
int x(xval+sum);
int y(yval+sum);
int z = add(x, y);
sum += z;
}
return sum;
}
int main(int , char* argv[]) {
int result = work(*argv[1], *argv[2]);
return result;
}Wenn ich es mit kompiliere -Os, dauert es 0,38 s, um dieses Programm auszuführen, und 0,44 s, wenn es mit -O2oder kompiliert wird -O3. Diese Zeiten werden konsistent und praktisch rauschfrei erhalten (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).
(Update: Ich habe den gesamten Assemblycode auf GitHub verschoben : Sie haben den Beitrag aufgebläht und den Fragen anscheinend nur einen sehr geringen Wert verliehen, da die fno-align-*Flags den gleichen Effekt haben.)
Hier ist die generierte Baugruppe mit -Osund -O2.
Leider ist mein Verständnis der Baugruppe sehr begrenzt, so dass ich keine Ahnung habe, ob das, was ich als Nächstes getan habe, richtig war: Ich habe die Baugruppe für -O2alle Baugruppen mit -Os Ausnahme der .p2alignLinien in die Baugruppe eingefügt . Dieser Code läuft immer noch in 0,38 Sekunden und der einzige Unterschied ist das .p2align Zeug.
Wenn ich richtig denke, sind dies Auffüllungen für die Stapelausrichtung. Laut Warum funktioniert das GCC-Pad mit NOPs? Es wird in der Hoffnung gemacht, dass der Code schneller ausgeführt wird, aber anscheinend schlug diese Optimierung in meinem Fall fehl.
Ist es die Polsterung, die in diesem Fall die Schuld trägt? Warum und wie?
Das Rauschen, das es macht, macht zeitliche Mikrooptimierungen unmöglich.
Wie kann ich sicherstellen, dass solche versehentlichen glücklichen / unglücklichen Ausrichtungen nicht stören, wenn ich Mikrooptimierungen (unabhängig von der Stapelausrichtung) für C- oder C ++ - Quellcode durchführe?
AKTUALISIEREN:
Nach der Antwort von Pascal Cuoq bastelte ich ein wenig an den Ausrichtungen. Durch die Übergabe -O2 -fno-align-functions -fno-align-loopsan gcc werden alle .p2alignaus der Assembly entfernt und die generierte ausführbare Datei wird in 0,38 Sekunden ausgeführt. Laut gcc-Dokumentation :
-Os aktiviert alle -O2-Optimierungen [aber] -Os deaktiviert die folgenden Optimierungsflags:
-falign-functions -falign-jumps -falign-loops -falign-labels -freorder-blocks -freorder-blocks-and-partition -fprefetch-loop-arrays
Es scheint also so ziemlich ein (falsches) Ausrichtungsproblem zu sein.
Ich bin immer noch skeptisch, -march=nativewie in Marat Dukhans Antwort vorgeschlagen . Ich bin nicht davon überzeugt, dass es nicht nur dieses (falsche) Ausrichtungsproblem stört. es hat absolut keine Auswirkung auf meine Maschine. (Trotzdem habe ich seine Antwort positiv bewertet.)
UPDATE 2:
Wir können -Osaus dem Bild herausnehmen. Die folgenden Zeiten werden durch Kompilieren mit erhalten
-O2 -fno-omit-frame-pointer0,37 s-O2 -fno-align-functions -fno-align-loops0,37 s-S -O2dann manuelles Verschieben der Baugruppeadd()nachwork()0,37 s-O20,44 s
Mir scheint, dass die Entfernung add()von der Anrufstelle sehr wichtig ist. Ich habe es versucht perf, aber die Ausgabe von perf statund perf reportmacht für mich sehr wenig Sinn. Ich konnte jedoch nur ein konsistentes Ergebnis erzielen:
-O2::
602,312,864 stalled-cycles-frontend # 0.00% frontend cycles idle
3,318 cache-misses
0.432703993 seconds time elapsed
[...]
81.23% a.out a.out [.] work(int, int)
18.50% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
100.00 ¦ lea (%rdi,%rsi,1),%eax
¦ }
¦ ? retq
[...]
¦ int z = add(x, y);
1.93 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
79.79 ¦ add %eax,%ebxFür fno-align-*:
604,072,552 stalled-cycles-frontend # 0.00% frontend cycles idle
9,508 cache-misses
0.375681928 seconds time elapsed
[...]
82.58% a.out a.out [.] work(int, int)
16.83% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
51.59 ¦ lea (%rdi,%rsi,1),%eax
¦ }
[...]
¦ __attribute__((noinline))
¦ static int work(int xval, int yval) {
¦ int sum(0);
¦ for (int i=0; i<LOOP_BOUND; ++i) {
¦ int x(xval+sum);
8.20 ¦ lea 0x0(%r13,%rbx,1),%edi
¦ int y(yval+sum);
¦ int z = add(x, y);
35.34 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
39.48 ¦ add %eax,%ebx
¦ }Für -fno-omit-frame-pointer:
404,625,639 stalled-cycles-frontend # 0.00% frontend cycles idle
10,514 cache-misses
0.375445137 seconds time elapsed
[...]
75.35% a.out a.out [.] add(int const&, int const&) [clone .isra.0] ¦
24.46% a.out a.out [.] work(int, int)
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
18.67 ¦ push %rbp
¦ return x + y;
18.49 ¦ lea (%rdi,%rsi,1),%eax
¦ const int LOOP_BOUND = 200000000;
¦
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ mov %rsp,%rbp
¦ return x + y;
¦ }
12.71 ¦ pop %rbp
¦ ? retq
[...]
¦ int z = add(x, y);
¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
29.83 ¦ add %eax,%ebxEs sieht so aus, als würden wir add()im langsamen Fall auf dem Anruf stehen bleiben .
Ich habe untersucht alles , die perf -eauf meiner Maschine ausspucken kann; nicht nur die Statistiken, die oben angegeben sind.
Für dieselbe ausführbare Datei stalled-cycles-frontendzeigt die lineare Korrelation mit der Ausführungszeit; Ich habe nichts anderes bemerkt, was so klar korrelieren würde. (Das Vergleichen stalled-cycles-frontendverschiedener ausführbarer Dateien macht für mich keinen Sinn.)
Ich habe die Cache-Fehler als ersten Kommentar eingefügt. Ich habe alle Cache-Fehler untersucht, die auf meinem Computer gemessen werden können perf, nicht nur die oben angegebenen. Die Cache-Fehler sind sehr, sehr verrauscht und zeigen wenig bis gar keine Korrelation mit den Ausführungszeiten.
Antworten:
Standardmäßig optimieren Compiler für "durchschnittliche" Prozessoren. Da verschiedene Prozessoren unterschiedliche Befehlssequenzen bevorzugen, können Compiler-Optimierungen, die durch aktiviert werden
-O2, dem durchschnittlichen Prozessor zugute kommen, aber die Leistung Ihres speziellen Prozessors verringern (und das gilt auch für-Os). Wenn Sie dasselbe Beispiel auf verschiedenen Prozessoren ausprobieren, werden Sie feststellen, dass einige davon profitieren,-O2während andere für-OsOptimierungen günstiger sind .Hier sind die Ergebnisse für
time ./test 0 0mehrere Prozessoren (Benutzerzeit angegeben):In einigen Fällen können Sie die Auswirkungen nachteiliger Optimierungen verringern, indem Sie
gccnach einer Optimierung für Ihren bestimmten Prozessor fragen (mithilfe von Optionen-mtune=nativeoder-march=native):Update: auf Ivy - Bridge-Core i3 drei Versionen
gcc(4.6.4,4.7.3, und4.8.1) produzieren Binärdateien mit signifikant unterschiedlicher Leistung, aber der Assembler - Code hat nur subtile Variationen. Bisher habe ich keine Erklärung für diese Tatsache.Zusammenbau von
gcc-4.6.4 -Os(wird in 0,709 Sekunden ausgeführt):Zusammenbau von
gcc-4.7.3 -Os(wird in 0,822 Sekunden ausgeführt):Zusammenbau von
gcc-4.8.1 -Os(wird in 0,994 Sekunden ausgeführt):quelle
-O2 -fno-align-functions -fno-align-loopsZeit auf0.340s, sodass dies durch Ausrichtung erklärt werden kann. Die optimale Ausrichtung hängt jedoch vom Prozessor ab: Einige Prozessoren bevorzugen ausgerichtete Schleifen und Funktionen.Mein Kollege hat mir geholfen, eine plausible Antwort auf meine Frage zu finden. Er bemerkte die Bedeutung der 256-Byte-Grenze. Er ist hier nicht registriert und hat mich ermutigt, die Antwort selbst zu posten (und den ganzen Ruhm zu nehmen).
Kurze Antwort:
Alles läuft auf die Ausrichtung hinaus. Ausrichtungen können einen erheblichen Einfluss auf die Leistung haben. Deshalb haben wir
-falign-*in erster Linie die Flags.Ich habe den gcc-Entwicklern einen (falschen?) Fehlerbericht übermittelt . Es stellt sich heraus, dass das Standardverhalten lautet: "Wir richten Schleifen standardmäßig auf 8 Byte aus, versuchen jedoch, sie auf 16 Byte auszurichten, wenn wir nicht mehr als 10 Byte ausfüllen müssen." Anscheinend ist diese Standardeinstellung in diesem speziellen Fall und auf meinem Computer nicht die beste Wahl. Clang 3.4 (Trunk) mit
-O3führt die entsprechende Ausrichtung durch und der generierte Code zeigt dieses seltsame Verhalten nicht.Wenn eine unangemessene Ausrichtung vorgenommen wird, wird dies natürlich noch schlimmer. Eine unnötige / schlechte Ausrichtung verbraucht nur ohne Grund Bytes und erhöht möglicherweise die Cache-Fehler usw.
Einfach indem Sie gcc anweisen, die richtige Ausrichtung vorzunehmen:
g++ -O2 -falign-functions=16 -falign-loops=16Lange Antwort:
Der Code wird langsamer ausgeführt, wenn:
Eine
XXByte-Grenze schneidetadd()in der Mitte (XXmaschinenabhängig).wenn der Aufruf von
add()über eineXXBytegrenze springen muss und das Ziel nicht ausgerichtet ist.wenn
add()nicht ausgerichtet ist.wenn die Schleife nicht ausgerichtet ist.
Die ersten beiden sind auf den Codes und Ergebnissen, die Marat Dukhan freundlicherweise veröffentlicht hat, gut sichtbar . In diesem Fall
gcc-4.8.1 -Os(wird in 0,994 Sekunden ausgeführt):Eine 256-Byte-Grenze schneidet
add()genau in der Mitte und wederadd()die Schleife noch die Schleife sind ausgerichtet. Überraschung, Überraschung, das ist der langsamste Fall!In dem Fall
gcc-4.7.3 -Os(wird in 0,822 Sekunden ausgeführt) schneidet die 256-Byte-Grenze nur in einen kalten Abschnitt (aber weder die Schleife nochadd()wird sie geschnitten):Nichts ist ausgerichtet, und der Aufruf von
add()muss über die 256-Byte-Grenze springen. Dieser Code ist der zweitlangsamste.Falls
gcc-4.6.4 -Os(wird in 0,709 Sekunden ausgeführt), obwohl nichts ausgerichtet ist, muss der Aufruf vonadd()nicht über die 256-Byte-Grenze springen und das Ziel ist genau 32 Byte entfernt:Dies ist der schnellste von allen dreien. Warum die 256-Byte-Grenze auf seinem Computer besonders wichtig ist, überlasse ich ihm, um es herauszufinden. Ich habe keinen solchen Prozessor.
Jetzt bekomme ich auf meinem Computer diesen 256-Byte-Randeffekt nicht. Nur die Funktion und die Schleifenausrichtung werden auf meinem Computer aktiviert. Wenn ich passiere,
g++ -O2 -falign-functions=16 -falign-loops=16ist alles wieder normal: Ich bekomme immer den schnellsten Fall und die Zeit reagiert nicht-fno-omit-frame-pointermehr auf die Flagge. Ich kanng++ -O2 -falign-functions=32 -falign-loops=32oder ein Vielfaches von 16 bestehen, der Code ist auch dafür nicht empfindlich.Eine wahrscheinliche Erklärung ist, dass ich Hotspots hatte, die für die Ausrichtung empfindlich waren, genau wie in diesem Beispiel. Durch das Durcheinander mit den Flaggen (vorbei
-Osstatt-O2) wurden diese Hotspots aus Versehen auf glückliche Weise ausgerichtet und der Code wurde schneller. Es hatte nichts mit Größenoptimierung zu tun: Es war ein Zufall, dass die Hotspots besser ausgerichtet wurden. Von nun an werde ich die Auswirkungen der Ausrichtung auf meine Projekte überprüfen.Oh, und noch etwas. Wie können solche Hotspots entstehen, wie im Beispiel gezeigt? Wie kann das Inlining einer so winzigen Funktion wie
add()fehlschlagen?Bedenken Sie:
und in einer separaten Datei:
und zusammengestellt als :
g++ -O2 add.cpp main.cpp.gcc wird nicht inline
add()!Das ist alles, es ist so einfach, unbeabsichtigt Hotspots wie den im OP zu erstellen. Natürlich ist es teilweise meine Schuld: gcc ist ein ausgezeichneter Compiler. Wenn die Kompilierung des oben als:
g++ -O2 -flto add.cpp main.cpp, das heißt, wenn ich Link Zeitoptimierung durchführen, um den Code läuft in 0.19s!(Inlining ist im OP künstlich deaktiviert, daher war der Code im OP 2x langsamer).
quelle
inline+ Funktionsdefinition im Header verwenden. Ich bin mir nicht sicher, wie ausgereift lto in gcc ist. Meine Erfahrung damit zumindest in Mingw ist ein Hit oder Miss.-flto. Es ist ziemlich revolutionär, wenn Sie es noch nie benutzt haben, aus Erfahrung :)Ich füge diese Nachannahme hinzu, um darauf hinzuweisen, dass die Auswirkungen der Ausrichtung auf die Gesamtleistung von Programmen - einschließlich großer Programme - untersucht wurden. Zum Beispiel zeigt dieser Artikel (und ich glaube, eine Version davon ist auch in CACM erschienen), wie Änderungen der Verbindungsreihenfolge und der Größe der Betriebssystemumgebung allein ausreichten, um die Leistung signifikant zu verändern. Sie führen dies auf die Ausrichtung von "Hot Loops" zurück.
Dieses Papier mit dem Titel "Falsche Daten produzieren, ohne etwas offensichtlich Falsches zu tun!" sagt, dass eine versehentliche experimentelle Verzerrung aufgrund nahezu unkontrollierbarer Unterschiede in den Programmlaufumgebungen wahrscheinlich viele Benchmark-Ergebnisse bedeutungslos macht.
Ich denke, Sie stoßen bei derselben Beobachtung auf einen anderen Blickwinkel.
Für leistungskritischen Code ist dies ein ziemlich gutes Argument für Systeme, die die Umgebung bei der Installation oder Laufzeit bewerten und unter den unterschiedlich optimierten Versionen der wichtigsten Routinen die lokal beste auswählen.
quelle
Ich denke, dass Sie das gleiche Ergebnis erzielen können wie Sie:
… Mit
-O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1. Ich habe-O215 Jahre lang alles mit diesen Optionen zusammengestellt, die jedes Mal, wenn ich mich bemühte zu messen, schneller als normal waren.Auch für einen völlig anderen Kontext (einschließlich eines anderen Compilers) habe ich festgestellt, dass die Situation ähnlich ist : Die Option, die "Codegröße statt Geschwindigkeit optimieren" soll, optimiert die Codegröße und -geschwindigkeit.
Nein, dies hat nichts mit dem Stapel zu tun. Die standardmäßig generierten NOPs und die Optionen -falign - * = 1 verhindern die Code-Ausrichtung.
Es ist sehr wahrscheinlich, dass die Polsterung der Schuldige ist. Der Grund, warum das Auffüllen als notwendig erachtet wird und in einigen Fällen nützlich ist, besteht darin, dass Code normalerweise in Zeilen von 16 Byte abgerufen wird ( Einzelheiten zu den Optimierungsressourcen von Agner Fog , die je nach Prozessormodell variieren). Das Ausrichten einer Funktion, Schleife oder Beschriftung an einer 16-Byte-Grenze bedeutet, dass die Wahrscheinlichkeit statistisch erhöht ist, dass eine Zeile weniger erforderlich ist, um die Funktion oder Schleife zu enthalten. Offensichtlich schlägt es fehl, weil diese NOPs die Codedichte und damit die Cache-Effizienz verringern. Im Fall von Schleifen und Beschriftungen müssen die NOPs möglicherweise sogar einmal ausgeführt werden (wenn die Ausführung normal zur Schleife / Beschriftung gelangt, im Gegensatz zu einem Sprung).
quelle
-O2 -fno-omit-frame-pointerist genauso gut wie-Os. Bitte überprüfen Sie die aktualisierte Frage.Wenn Ihr Programm durch den CODE L1-Cache begrenzt ist, zahlt sich die Größenoptimierung plötzlich aus.
Als ich das letzte Mal nachgesehen habe, ist der Compiler nicht klug genug, um dies in allen Fällen herauszufinden.
In Ihrem Fall generiert -O3 wahrscheinlich genug Code für zwei Cache-Zeilen, aber -Os passt in eine Cache-Zeile.
quelle
-falign-*=16Flaggen ist alles wieder normal, alles verhält sich konsequent. Für mich ist diese Frage gelöst.Ich bin kein Experte auf diesem Gebiet, aber ich scheine mich daran zu erinnern, dass moderne Prozessoren sehr empfindlich sind, wenn es um die Vorhersage von Zweigen geht . Die Algorithmen zur Vorhersage der Verzweigungen basieren (oder waren zumindest in den Tagen, als ich Assembler-Code schrieb) auf mehreren Eigenschaften des Codes, einschließlich der Entfernung eines Ziels und der Richtung.
Das Szenario, das mir in den Sinn kommt, sind kleine Schleifen. Wenn der Zweig rückwärts ging und die Entfernung nicht zu weit war, wurde die Verzweigungsvorhersage für diesen Fall optimiert, da alle kleinen Schleifen auf diese Weise ausgeführt werden. Die gleichen Regeln können zum Tragen kommen, wenn Sie die Position von
addundworkim generierten Code tauschen oder wenn sich die Position von beiden geringfügig ändert.Trotzdem habe ich keine Ahnung, wie ich das überprüfen soll, und ich wollte Sie nur wissen lassen, dass dies etwas sein könnte, das Sie untersuchen möchten.
quelle
add()undwork()wenn-O2bestanden wird. In allen anderen Fällen wird der Code durch Tauschen erheblich langsamer. Während des Wochenendes analysierte ich auch Statistiken zur Verzweigungsvorhersage / Fehlvorhersage mitperfund bemerkte nichts, was dieses seltsame Verhalten erklären könnte. Das einzige konsistente Ergebnis ist, dass im langsamen Fallperf100,0 Zolladd()und ein großer Wert in der Zeile direkt nach dem Aufruf vonadd()in der Schleife gemeldet werden. Es sieht so aus, als ob wir aus irgendeinem Grundadd()im langsamen Fall stehen bleiben, aber nicht in den schnellen Läufen.perfunterstützt nur eine begrenzte Anzahl von Dingen, vielleicht ist Intels Zeug auf dem eigenen Prozessor etwas praktischer.