Welcher Code ist besser für die Optimierung der Verzweigungsvorhersage?

10

Welcher Code bietet angesichts der Verzweigungsvorhersage und der Auswirkungen von Compileroptimierungen tendenziell eine überlegene Leistung?

Beachten Sie, dass bRareExceptionPresent eine ungewöhnliche Bedingung darstellt. Es ist nicht der normale Weg der Logik.

/* MOST COMMON path must branch around IF clause */

bool SomeFunction(bool bRareExceptionPresent)
{
  // abort before function
  if(bRareExceptionPresent)
  {
     return false;
  }    
  .. function primary body ..    
  return true;
}

/* MOST COMMON path does NOT branch */

bool SomeFunction(bool bRareExceptionPresent)
{
  if(!bRareExceptionPresent)
  {
    .. function primary body ..
  }
  else
  {
    return false;
  }
  return true;
}
Dyasta
quelle
9
Ich werde hier auf die Beine gehen und sagen, dass es überhaupt keinen Unterschied gibt.
Robert Harvey
7
Dies hängt wahrscheinlich von der spezifischen CPU ab, für die Sie kompilieren, da sie unterschiedliche Pipelining-Architekturen haben (Verzögerungssteckplätze vs. kein Verzögerungssteckplatz). Die Zeit, die Sie damit verbracht haben, darüber nachzudenken, ist wahrscheinlich viel länger als die Zeit, die beim Ausführen gespart wurde - zuerst Profil erstellen, dann optimieren.
2
Es ist mit ziemlicher Sicherheit eine vorzeitige Mikrooptimierung.
Robert Harvey
2
@MichaelT Ja, Profiling ist in der Tat die einzige zuverlässige Methode, um zu wissen, was mit der Leistung des Codes auf dem Ziel, der Plattform, in seinem Kontext wirklich los ist. Ich war jedoch neugierig, ob man allgemein bevorzugt wurde.
Dyasta
1
@RobertHarvey: Es handelt sich um eine vorzeitige Mikrooptimierung, außer in Fällen , in denen beide Bedingungen erfüllt sind: (1) Die Schleife wird milliardenfach (nicht millionenfach) genannt. und (2) ironischerweise, wenn der Schleifenkörper in Bezug auf den Maschinencode winzig ist. Bedingung 2 bedeutet, dass der Anteil der Zeit, die für Gemeinkosten aufgewendet wird , im Vergleich zu der Zeit, die für nützliche Arbeit aufgewendet wird, nicht unerheblich ist. Die gute Nachricht ist, dass in solchen Situationen, in denen beide Bedingungen erfüllt sind, SIMD (Vektorisierung), die von Natur aus verzweigungslos ist, normalerweise alle Leistungsprobleme löst.
Rwong

Antworten:

10

In der heutigen Welt spielt es keine Rolle, wenn überhaupt.

Dynamische Verzweigungsvorhersagen (über die seit Jahrzehnten nachgedacht wird (siehe Eine 1996 veröffentlichte Analyse der Schemata für dynamische Verzweigungsvorhersagen )) sind weit verbreitet.

Ein Beispiel hierfür finden Sie im ARM-Prozessor. Aus dem Arm Info Center zur Zweigvorhersage

Um die Genauigkeit der Verzweigungsvorhersage zu verbessern, wird eine Kombination aus statischen und dynamischen Techniken verwendet.

Die Frage ist dann: "Was ist dynamische Verzweigungsvorhersage im Armprozessor?" Das fortgesetzte Lesen der dynamischen Verzweigungsvorhersage zeigt, dass ein 2-Bit-Vorhersageschema (in der Veröffentlichung beschrieben) Informationen darüber erstellt, ob die Verzweigung stark oder schwach genommen wird oder nicht.

Mit der Zeit (und mit der Zeit meine ich ein paar Durchgänge durch diesen Block) werden Informationen darüber aufgebaut, in welche Richtung der Code gehen wird.

Bei der statischen Vorhersage wird untersucht , wie der Code selbst aussieht und wie die Verzweigung beim Test erfolgt - zu einer vorherigen Anweisung oder einer weiteren im Code:

Das im ARM1136JF-S-Prozessor verwendete Schema sagt voraus, dass nicht alle bedingten Vorwärtszweige und alle Rückwärtszweige genommen werden. Rund 65% aller Zweige gehen genügend Nicht-Verzweigungszyklen voraus, um vollständig vorhergesagt zu werden.

Wie von Sparky erwähnt, basiert dies auf dem Verständnis, dass Schleifen häufig Schleifen sind. Die Schleife verzweigt sich rückwärts (am Ende der Schleife befindet sich eine Verzweigung, um sie oben neu zu starten) - dies geschieht normalerweise.

Die Gefahr, den Compiler zu erraten, besteht darin, dass Sie nicht wissen, wie dieser Code tatsächlich kompiliert (und optimiert) wird. Und zum größten Teil spielt es keine Rolle. Bei der dynamischen Vorhersage wird zweimal durch die Funktion ein Überspringen der Schutzanweisung für eine vorzeitige Rückkehr vorhergesagt. Wenn die Leistung von zwei gespülten Rohrleitungen von kritischer Leistung ist, gibt es andere Dinge, über die Sie sich Sorgen machen müssen.

Die Zeit, die benötigt wird, um einen Stil über den anderen zu lesen, ist wahrscheinlich von größerer Bedeutung - Code sauber zu machen, damit ein Mensch ihn lesen kann, da der Compiler gut funktioniert, egal wie chaotisch oder idealisiert Sie den Code schreiben.


quelle
7
Eine berühmte Stackoverflow-Frage zeigte, dass die Verzweigungsvorhersage auch heute noch eine Rolle spielt.
Florian Margaine
3
@FlorianMargaine Während es wichtig ist, scheint es in einer Situation, in der es wirklich wichtig ist, das Verständnis dafür zu erfordern, was Sie kompilieren und wie es funktioniert (arm vs x86 vs mips ...). Das Schreiben von Code, der zu Beginn versucht, diese Mikrooptimierung durchzuführen, funktioniert wahrscheinlich unter falschen Voraussetzungen und erzielt nicht den gewünschten Effekt.
Lassen Sie uns natürlich nicht DK zitieren. Aber ich denke, diese Frage war eindeutig im Sinne einer Optimierung, als Sie die Profilierungsphase bereits hinter sich gelassen haben. :-)
Florian Margaine
2
@ MichaelT Schöne Antwort, und ich stimme Ihrer Schlussfolgerung sehr zu. Diese Art der Vorprofilierung / abstrakten Optimierung kann definitiv kontraproduktiv sein. Es ist ein Ratespiel, bei dem man aus irrationalen Gründen Designentscheidungen trifft. Trotzdem war ich neugierig, o
dyasta
5
@ 90h stackoverflow.com/questions/11227809/…
Florian Margaine
9

Nach meinem Verständnis wird die CPU beim ersten Auftreffen auf einen Zweig vorhersagen (sofern unterstützt), dass keine Vorwärtszweige und Rückwärtszweige verwendet werden. Der Grund dafür ist, dass angenommen wird, dass Schleifen (die typischerweise rückwärts verzweigen) angenommen werden.

Auf einigen Prozessoren können Sie in der Assembly-Anweisung einen Hinweis geben, welcher Pfad am wahrscheinlichsten ist. Details dazu entgehen mir im Moment.

Darüber hinaus unterstützen einige C-Compiler auch die statische Verzweigungsvorhersage, sodass Sie dem Compiler mitteilen können, welche Verzweigung wahrscheinlicher ist. Im Gegenzug kann es den generierten Code neu organisieren oder geänderte Anweisungen verwenden, um diese Informationen zu nutzen (oder sie einfach nur ignorieren).

__builtin_expect((long)!!(x), 1L)  /* GNU C to indicate that <x> will likely be TRUE */
__builtin_expect((long)!!(x), 0L)  /* GNU C to indicate that <x> will likely be FALSE */

Hoffe das hilft.

Sparky
quelle
3
"Ich verstehe, dass die CPU beim ersten Auftreffen auf eine Verzweigung (sofern unterstützt) vorhersagt, dass keine Vorwärtsverzweigungen und keine Rückwärtsverzweigungen verwendet werden." Dies ist ein sehr interessanter Gedanke. Haben Sie Beweise dafür, dass dies tatsächlich in gängigen Architekturen implementiert ist?
Blubb
5
Direkt aus dem Maul des Pferdes: Ein vorderer Ast wird standardmäßig nicht genommen. Standardmäßig wird ein Rückwärtszweig verwendet . Und von derselben Seite: "Präfix 0x3E - statisch einen Zweig als genommen vorhersagen".
MSalters
Gibt es ein plattformunabhängiges Pragma, das gleichwertig ist __builtin_expect?
MarcusJ