wie gcc-Compiler wahrscheinliches Zweig

Question

Beispiel vorzuschlagen. Die Bedingungsberechnung dauert ~ 60 Zyklen, die überprüft werden müssen, und sie kann nicht zur Kompilierzeit vom Compiler selbst berechnet werden.

(gcc 4.3)

Answer 1

Wenn Sie GCC vorschlagen wollen, dass eine Bedingung einen bestimmten Wert als Hinweis haben, für die Anordnung Code Fluss wahrscheinlich ist, sollten Sie __builtin_expect() verwenden:

if (__builtin_expect(almost_always_false_condition,0)) { 
    // do something 
} 

jedoch Es klingt, als ob du einen Weg finden willst, den Zustand nicht zu bewerten, was __builtin_expect() nicht tut. Gibt es eine Möglichkeit, dass Sie schnell den Zustand annähern kann, und nur die vollständige Kontrolle tun, wenn die Annäherung wahr ist:

if (__builtin_expect(fastCheckThatIsTrueIfFullConditionIsTrue,0)) { 
    // most of the time, we don't even get to here, so you don't need 
    // to evaluate the condition 
    if (almostAlwaysFalseCondition) { 
     // do something 
    } 
} 

Können Sie uns mehr über das, was die Bedingung ist?

Answer 2

Die Dokumentation schlägt vor, dass gcc tut (oder kann) Wählen Sie aus gesteuerte Optimierung. Es ist nicht etwas, was ich jemals mit gcc versucht habe, also kann ich keinen weiteren Rat geben, es könnte sich lohnen, Google zu schlagen.

Answer 3

Wenn das Ergebnis während eines einzelnen Laufs variieren kann, können Sie möglicherweise eine langsame Auswertung boolescher Operatoren verwenden, um Ihre Bedingung in einen billigen Teil und einen teuren Teil aufzuteilen und den billigen Teil zuerst auszuführen.

if (a == 5 && somethingexpensive()) 
{ 
    ... 
} 

Da a == 5 Berechnung ist billiger als somethingexpensive(), und wenn es fast immer false ist, sollten Sie es zuerst ausgeführt, die die somethingexpensive Klausel verhindert auswertet.

Wenn auf der anderen Seite das Ergebnis für einen Lauf des Programms konstant ist, können Sie es optimieren, indem das Ergebnis der Berechnung in einer statischen oder globalen Variablen zu speichern.

static int result = doevalfunctiononlyonce(); 

if (result) 
{ 
    ....  
} 

Auf diese Weise können die Kosten für die if auf einen einfachen Speicher-Lookup reduziert haben.

Wenn die Bedingung nur in Reaktion auf eine Aktion in einem anderen Verfahren ändert, können Sie die globale von diesem Verfahren aktualisieren:

int condition; 

void appendToList(int a) 
{ 
    list.append(a); 
    if (list.somethingexpensive()) 
    { 
    condition = true; 
    } else 
    { 
    condition = false; 
    } 
} 

void someotherfunction() 
{ 
    // if (list.somethingexpensive()) 
    if (condition) 
    { 
    ... 
    } 
} 

Dies ist nützlich, wenn someotherfunction viel häufiger als die appendtolist Funktion aufgerufen wird.

Answer 4

Zunächst einmal, wie viele Zyklen sind in der else Klausel ausgegeben oder an anderer Stelle im Programm? Wenn Sie profilieren oder stackshots einnehmen, verbringen Sie mindestens 10% Ihrer Zeit in diesem Test? Wenn nicht, gibt es wahrscheinlich größere Probleme, die Sie zuerst betrachten sollten.

Zweitens, wenn Sie verbringen> 10% der Zeit in diesem Test sollten Sie, wenn der Algorithmus, um zu sehen eingestellt werden kann Entscheidungspunkte näher an 50-50 Wahrscheinlichkeit zu haben. Ein 50-50 Entscheidungspunkt ergibt 1 Bit an Information, wenn es ausgeführt wird, während ein 99-1 Entscheidungspunkt nur etwa 0,07 Bits ergibt. * (Dh es ist nicht viel zu sagen, so ist es eine ineffiziente Nutzung von CPU-Zyklen ist.) Ein Beispiel für dieses Phänomen ist, wenn Sie die lineare Suche mit der binären Suche vergleichen.

* Wenn Sie einen binären Entscheidungspunkt und die Wahrscheinlichkeiten der Ergebnisse haben, sind a und b, ist die Informationsausbeute (Entropie) in Bits -(a*log(a) + b*log(b))/log(2).

Answer 5

Meiner Meinung nach ist der beste Weg, um diese Art der Optimierung durchzuführen, die -fprofile-generate und -fprofile-use Optionen zu verwenden. Dies erfordert eine Basis von repräsentativen Anwendungsfällen, um Informationen darüber zu sammeln, was wahrscheinlich ist und was nicht, aber die Tests können für diesen Zweck verwendet werden. Auf der anderen Seite ist der Code nicht mit hässlichen, nicht portablen Anweisungen versehen. Weitere Informationen zu diesen beiden Optionen finden Sie unter https://gcc.gnu.org/onlinedocs/gcc-4.3.6/gcc/Optimize-Options.html#Optimize-Options.