Ist es möglich, dem Zweigprädiktor mitzuteilen, wie wahrscheinlich es ist, dem Zweig zu folgen?

Um es klar zu machen, ich werde hier keine Portabilität anstreben, daher sind alle Lösungen, die mich an eine bestimmte Box binden, in Ordnung.

Grundsätzlich habe ich eine if-Anweisung, die in 99% der Fälle als wahr ausgewertet wird, und versuche, jede letzte Uhr der Leistung herauszuholen. Kann ich eine Art Compiler-Befehl ausgeben (unter Verwendung von GCC 4.1.2 und x86 ISA, wenn es ist wichtig) dem Zweigprädiktor mitzuteilen, dass er für diesen Zweig zwischenspeichern soll?

Ja. http://kerneltrap.org/node/4705

Das __builtin_expectist ein Verfahren , dass gcc (Versionen> = 2.96) Angebot für Programmierer Verzweigungsvorhersageinformationen an den Compiler , um anzuzeigen. Der Rückgabewert von __builtin_expectist das erste Argument (das nur eine Ganzzahl sein kann), das an ihn übergeben wird.

if (__builtin_expect (x, 0))
                foo ();

     [This] would indicate that we do not expect to call `foo', since we
     expect `x' to be zero. 

Ja, aber es wird keine Wirkung haben. Ausnahmen sind ältere (veraltete) Architekturen vor Netburst, und selbst dann macht es nichts Messbares.

Es gibt einen "Verzweigungshinweis" -Opcode, den Intel mit der Netburst-Architektur eingeführt hat, und eine standardmäßige statische Verzweigungsvorhersage für Kaltsprünge (rückwärts vorhergesagt genommen, vorwärts vorhergesagt nicht genommen) auf einigen älteren Architekturen. GCC implementiert dies mit dem __builtin_expect (x, prediction), wobei die Vorhersage normalerweise 0 oder 1 ist. Der vom Compiler ausgegebene Opcode wird auf allen neueren Prozessorarchitekturen ignoriert (> = Core 2). Der kleine Eckfall, in dem dies tatsächlich etwas bewirkt, ist der Fall eines Kaltsprungs auf die alte Netburst-Architektur. Intel empfiehlt jetzt, die statischen Verzweigungshinweise nicht zu verwenden, wahrscheinlich weil sie die Erhöhung der Codegröße als schädlicher als die mögliche marginale Beschleunigung betrachten.

Neben dem nutzlosen Verzweigungshinweis für den Prädiktor kann __builtin_expectder Compiler den Code neu anordnen, um die Cache-Nutzung zu verbessern oder Speicherplatz zu sparen.

Es gibt mehrere Gründe, warum es nicht wie erwartet funktioniert.

• Der Prozessor kann kleine Schleifen (n <64) perfekt vorhersagen.
• Der Prozessor kann kleine Wiederholungsmuster (n ~ 7) perfekt vorhersagen.
• Der Prozessor selbst kann die Wahrscheinlichkeit einer Verzweigung zur Laufzeit besser schätzen als der Compiler / Programmierer zur Kompilierungszeit.
• Die Vorhersagbarkeit (= Wahrscheinlichkeit, dass ein Zweig korrekt vorhergesagt wird) eines Zweigs ist weitaus wichtiger als die Wahrscheinlichkeit, dass der Zweig genommen wird. Leider ist dies stark von der Architektur abhängig, und die Vorhersage der Vorhersagbarkeit von Zweigen ist notorisch schwierig.

Weitere Informationen zu den inneren Arbeiten der Zweigvorhersage finden Sie in den Agner Fogs- Handbüchern . Siehe auch die gcc Mailingliste .

Pentium 4 (auch bekannt als Netburst-Mikroarchitektur) hatte Verzweigungsvorhersagen als Präfixe für die jcc-Anweisungen, aber nur P4 hat jemals etwas damit gemacht. Siehe http://ref.x86asm.net/geek32.html . Und Abschnitt 3.5 von Agner Fogs ausgezeichnetem asm opt-Leitfaden von http://www.agner.org/optimize/ . Er hat auch eine Anleitung zur Optimierung in C ++.

Frühere und spätere x86-CPUs ignorieren diese Präfixbytes stillschweigend. Gibt es Leistungstestergebnisse für die Verwendung wahrscheinlicher / unwahrscheinlicher Hinweise? erwähnt, dass PowerPC einige Sprunganweisungen hat, die einen Verzweigungsvorhersagehinweis als Teil der Codierung enthalten. Es ist ein ziemlich seltenes architektonisches Merkmal. Die statische Vorhersage von Zweigen zur Kompilierungszeit ist sehr schwierig, daher ist es normalerweise besser, sie der Hardware zu überlassen, um dies herauszufinden.

Es wird offiziell nicht viel darüber veröffentlicht, wie sich die Verzweigungsprädiktoren und Verzweigungszielpuffer in den neuesten Intel- und AMD-CPUs genau verhalten. Die Optimierungshandbücher (leicht zu finden auf den Websites von AMD und Intel) geben einige Ratschläge, dokumentieren jedoch kein spezifisches Verhalten. Einige Leute haben Tests durchgeführt, um zu versuchen, die Implementierung zu erraten, z. B. wie viele BTB-Einträge Core2 hat ... Wie auch immer, die Idee, den Prädiktor explizit anzudeuten, wurde (vorerst) aufgegeben.

Es ist beispielsweise dokumentiert, dass Core2 über einen Zweigverlaufspuffer verfügt, der eine Fehlvorhersage des Schleifenausgangs vermeiden kann, wenn die Schleife immer eine konstant kurze Anzahl von Iterationen <8 oder 16 IIRC ausführt. Aber seien Sie nicht zu schnell zum Abrollen, da eine Schleife, die in 64 Byte (oder 19 Ups auf Penryn) passt, keine Engpässe beim Abrufen von Anweisungen aufweist, da sie aus einem Puffer wiedergegeben wird. Lesen Sie die PDFs von Agner Fog. Sie sind ausgezeichnet .

Siehe auch Warum hat Intel in diesen Jahren den Mechanismus zur Vorhersage statischer Zweige geändert? : Intel verwendet seit Sandybridge überhaupt keine statische Vorhersage, soweit wir aus Leistungsexperimenten ersehen können, die versuchen, die Funktionsweise von CPUs rückzuentwickeln. (Viele ältere CPUs haben eine statische Vorhersage als Fallback, wenn die dynamische Vorhersage fehlschlägt. Die normale statische Vorhersage besteht darin, dass Vorwärtsverzweigungen nicht und Rückwärtsverzweigungen verwendet werden (da Rückwärtsverzweigungen häufig Schleifenverzweigungen sind).)

Die Wirkung von likely()/ unlikely()Makros unter Verwendung von GNU __builtin_expectCs (wie in Drakoshas Antwort erwähnt) fügt BP-Hinweise nicht direkt in den Asm ein . (Möglicherweise mit gcc -march=pentium4, aber nicht beim Kompilieren für etwas anderes).

Der eigentliche Effekt besteht darin, den Code so auszulegen, dass auf dem schnellen Pfad weniger Verzweigungen und möglicherweise insgesamt weniger Anweisungen vorhanden sind. Dies hilft bei der Verzweigungsvorhersage in Fällen, in denen die statische Vorhersage ins Spiel kommt (z. B. sind dynamische Prädiktoren kalt, auf CPUs, die auf die statische Vorhersage zurückgreifen, anstatt nur Verzweigungen in den Prädiktor-Caches miteinander aliasen zu lassen).

Siehe Was ist der Vorteil von GCCs __builtin_expect in if else-Anweisungen? für ein bestimmtes Beispiel von Code-Gen.

Entnommene Zweige kosten etwas mehr als nicht genommene Zweige, selbst wenn sie perfekt vorhergesagt werden. Wenn die CPU Code in Blöcken von 16 Bytes abruft, um ihn parallel zu decodieren, bedeutet eine genommene Verzweigung, dass spätere Befehle in diesem Abrufblock nicht Teil des auszuführenden Befehlsstroms sind. Es entstehen Blasen im Front-End, die zu einem Engpass im Code mit hohem Durchsatz werden können (der bei Cache-Fehlern nicht im Back-End blockiert und eine hohe Parallelität auf Befehlsebene aufweist).

Das Herumspringen zwischen verschiedenen Blöcken berührt möglicherweise auch mehr Cache-Codezeilen , erhöht den L1i-Cache-Footprint und verursacht möglicherweise mehr Befehls-Cache-Fehler, wenn es kalt ist. (Und möglicherweise UOP-Cache-Footprint). Das ist ein weiterer Vorteil, wenn der schnelle Weg kurz und linear ist.

Die profilgesteuerte Optimierung von GCC macht normalerweise wahrscheinliche / unwahrscheinliche Makros unnötig. Der Compiler sammelt Laufzeitdaten darüber, wie jeder Zweig Code-Layout-Entscheidungen getroffen und heiße oder kalte Blöcke / Funktionen identifiziert hat. (z. B. werden Schleifen in heißen Funktionen, aber nicht in kalten Funktionen abgewickelt.) Siehe -fprofile-generateund -fprofile-use im GCC-Handbuch . Wie verwende ich profilgesteuerte Optimierungen in g ++?

Andernfalls muss GCC verschiedene Heuristiken erraten, wenn Sie keine wahrscheinlichen / unwahrscheinlichen Makros und kein PGO verwendet haben. -fguess-branch-probabilityist standardmäßig bei -O1und höher aktiviert .

https://www.phoronix.com/scan.php?page=article&item=gcc-82-pgo&num=1 bietet Benchmark-Ergebnisse für PGO im Vergleich zu regulären mit gcc8.2 auf einer Xeon Scalable Server-CPU. (Skylake-AVX512). Jeder Benchmark wurde mindestens geringfügig beschleunigt, und einige profitierten von ~ 10%. (Das meiste davon ist wahrscheinlich auf das Abrollen von Schleifen in Hot-Loops zurückzuführen, aber ein Teil davon ist vermutlich auf ein besseres Zweiglayout und andere Effekte zurückzuführen.)

Ich schlage vor, mich nicht um die Verzweigungsvorhersage zu kümmern, den Code zu profilieren und den Code zu optimieren, um die Anzahl der Verzweigungen zu verringern. Ein Beispiel ist das Abrollen von Schleifen und ein anderes mit booleschen Programmiertechniken anstelle von ifAnweisungen.

Die meisten Prozessoren lieben es, Anweisungen vorab abzurufen. Im Allgemeinen generiert eine Verzweigungsanweisung a Fehler im Prozessor, der dazu führt, dass die Prefetch-Warteschlange geleert wird. Hier ist die größte Strafe. Um diese Zeit zu verkürzen, schreiben Sie den Code neu (und entwerfen Sie ihn), sodass weniger Zweige verfügbar sind. Einige Prozessoren können Anweisungen auch bedingt ausführen, ohne verzweigen zu müssen.

Ich habe ein Programm von 1 Stunde Ausführungszeit auf 2 Minuten optimiert, indem ich das Abrollen von Schleifen und große E / A-Puffer verwendet habe. Die Branchenvorhersage hätte in diesem Fall nicht viel Zeit gespart.

In SUN C Studio sind einige Pragmas für diesen Fall definiert.

#pragma rar_called ()

Dies funktioniert, wenn ein Teil eines bedingten Ausdrucks ein Funktionsaufruf ist oder mit einem Funktionsaufruf beginnt.

Es gibt jedoch keine Möglichkeit, eine generische if / while-Anweisung zu kennzeichnen

Nein, da es keinen Assembly-Befehl gibt, der den Verzweigungsprädiktor informiert. Mach dir keine Sorgen, der Branch Predictor ist ziemlich schlau.

Auch obligatorischer Kommentar zur vorzeitigen Optimierung und wie es böse ist.

EDIT: Drakosha erwähnte einige Makros für GCC. Ich glaube jedoch, dass dies eine Codeoptimierung ist und eigentlich nichts mit Verzweigungsvorhersage zu tun hat.

Das klingt für mich nach Overkill - diese Art der Optimierung spart nur wenig Zeit. Die Verwendung einer moderneren Version von gcc hat beispielsweise einen viel größeren Einfluss auf die Optimierung. Versuchen Sie außerdem, alle verschiedenen Optimierungsflags zu aktivieren und zu deaktivieren. Sie verbessern nicht alle die Leistung.

Grundsätzlich scheint es sehr unwahrscheinlich, dass dies im Vergleich zu vielen anderen fruchtbaren Pfaden einen signifikanten Unterschied macht.

EDIT: danke für die Kommentare. Ich habe dieses Community-Wiki erstellt, es aber belassen, damit andere die Kommentare sehen können.