Welche Techniken zur Vermeidung bedingter Verzweigungen kennen Sie?

Manchmal hat eine Schleife, in der die CPU die meiste Zeit verbringt, sehr oft einen Verzweigungsvorhersagefehler (Fehlvorhersage). Ich habe ein paar Techniken zu sehr isolierten Threads gesehen, aber nie eine Liste. Die, die ich kenne, beheben bereits Situationen, in denen die Bedingung in einen Bool umgewandelt werden kann und dass 0/1 in irgendeiner Weise zum Ändern verwendet wird. Gibt es andere bedingte Verzweigungen, die vermieden werden können?

zB (Pseudocode)

loop () {
  if (in[i] < C )
    out[o++] = in[i++]
  ...
}

Kann umgeschrieben werden, wobei wohl etwas an Lesbarkeit verloren geht, mit so etwas:

loop() {
  out[o] = in[i]  // copy anyway, just don't increment
  inc = in[i] < C  // increment counters? (0 or 1)
  o += inc
  i += inc
}

Auch habe ich gesehen, wie sich Techniken in freier Wildbahn veränderten && zu & im Konditional in bestimmten Kontexten, die mir gerade entgehen. Ich bin ein Anfänger auf diesem Optimierungsniveau, aber es fühlt sich sicher so an, als müsste es mehr geben.

Am Beispiel von Matt Joiner:

if (b > a) b = a;

Sie können auch Folgendes tun, ohne sich mit Assemblercode befassen zu müssen:

bool if_else = b > a;
b = a * if_else + b * !if_else;

Ich glaube, der häufigste Weg, Verzweigungen zu vermeiden, besteht darin, die Bitparallelität zu nutzen, um die Gesamtsprünge in Ihrem Code zu reduzieren. Je länger die Basisblöcke sind, desto seltener wird die Pipeline gespült.

Wie jemand anderes bereits erwähnt hat, wenn Sie mehr tun möchten, als Schleifen aufzurollen und Verzweigungshinweise bereitzustellen, sollten Sie in die Assemblierung einsteigen. Dies sollte natürlich mit äußerster Vorsicht erfolgen: Ihr typischer Compiler kann in den meisten Fällen eine bessere Assemblierung schreiben als ein Mensch. Ihre beste Hoffnung ist es, Ecken und Kanten abzuschleifen und Annahmen zu treffen, die der Compiler nicht ableiten kann.

Hier ist ein Beispiel für den folgenden C-Code:

if (b > a) b = a;

In Assembler ohne Sprünge, durch Bit-Manipulation (und extremes Kommentieren):

sub eax, ebx ; = a - b
sbb edx, edx ; = (b > a) ? 0xFFFFFFFF : 0
and edx, eax ; = (b > a) ? a - b : 0
add ebx, edx ; b = (b > a) ? b + (a - b) : b + 0

Beachten Sie, dass bedingte Züge zwar sofort von Assembler-Enthusiasten angesprungen werden, dies aber nur, weil sie leicht verständlich sind und ein höheres Sprachkonzept in einer praktischen Einzelanweisung bieten. Sie sind nicht unbedingt schneller, auf älteren Prozessoren nicht verfügbar, und indem Sie Ihren C-Code in entsprechende bedingte Bewegungsanweisungen abbilden, erledigen Sie nur die Arbeit des Compilers.

Die Verallgemeinerung des von Ihnen gegebenen Beispiels lautet “Bedingte Bewertung durch Mathematik ersetzen”; Die Vermeidung bedingter Verzweigungen läuft weitgehend darauf hinaus.

Was ist los mit dem Austausch && mit & ist das, da && Kurzschluss ist, stellt er an und für sich eine bedingte Bewertung dar. & erhalten Sie die gleichen logischen Ergebnisse, wenn beide Seiten entweder 0 oder 1 sind, und kein Kurzschluss ist. Gleiches gilt für || und | außer Sie müssen nicht sicherstellen, dass die Seiten auf 0 oder 1 beschränkt sind (wiederum nur für logische Zwecke, dh Sie verwenden das Ergebnis nur boolesch).

Auf dieser Ebene sind die Dinge sehr Hardware- und Compiler-abhängig. Ist der von Ihnen verwendete Compiler intelligent genug, um < ohne Kontrollfluss zu kompilieren? gcc auf x86 ist schlau genug; lcc ist nicht. Bei älteren oder eingebetteten Befehlssätzen ist es möglicherweise nicht möglich, < ohne Kontrollfluss zu berechnen.

Über diese Cassandra-artige Warnung hinaus ist es schwierig, hilfreiche allgemeine Aussagen zu machen. Hier sind einige allgemeine Aussagen, die möglicherweise nicht hilfreich sind:

• Moderne Branchenvorhersage-Hardware ist erschreckend gut. Wenn Sie ein echtes Programm finden könnten, bei dem die Vorhersage schlechter Verzweigungen mehr als 1 % bis 2 % Verlangsamung kostet, wäre ich sehr überrascht.

• Leistungszähler oder andere Tools, die Ihnen sagen, wo Sie falsche Vorhersagen für Zweige finden, sind unverzichtbar.

• Wenn Sie solchen Code tatsächlich verbessern müssen, würde ich mich mit der Trace-Planung und dem Abrollen von Schleifen befassen:

  • Das Abrollen von Schleifen repliziert Schleifenkörper und gibt Ihrem Optimierer mehr Kontrollfluss, mit dem er arbeiten kann.

  • Die Trace-Planung identifiziert, welche Pfade am wahrscheinlichsten genommen werden, und kann unter anderem die Verzweigungsrichtungen optimieren, sodass die Verzweigungsvorhersage-Hardware auf den häufigsten Pfaden besser funktioniert. Bei ausgerollten Schleifen gibt es mehr und längere Pfade, sodass der Trace-Scheduler mehr zu verarbeiten hat

• Ich wäre misstrauisch, wenn ich versuchen würde, dies selbst in Assembler zu codieren. Wenn der nächste Chip mit neuer Verzweigungsvorhersage-Hardware herauskommt, stehen die Chancen gut, dass all Ihre harte Arbeit den Bach runtergeht. Stattdessen würde ich nach einem suchen Feedback-gesteuerter optimierender Compiler.

Eine Erweiterung der in der ursprünglichen Frage demonstrierten Technik gilt, wenn Sie mehrere verschachtelte Tests durchführen müssen, um eine Antwort zu erhalten. Sie können aus den Ergebnissen aller Tests eine kleine Bitmaske erstellen und die Antwort in einer Tabelle “nachschlagen”.

if (a) {
  if (b) {
    result = q;
  } else {
    result = r;
  }
} else {
  if (b) {
    result = s;
  } else {
    result = t;
  }
}

Wenn a und b nahezu zufällig sind (z. B. aus willkürlichen Daten) und dies in einer engen Schleife ist, dann können Verzweigungsvorhersagefehler dies wirklich verlangsamen. Kann geschrieben werden als:

// assuming a and b are bools and thus exactly 0 or 1 ...
static const table[] = { t, s, r, q };
unsigned index = (a << 1) | b;
result = table[index];

Sie können dies auf mehrere Bedingungen verallgemeinern. Ich habe es für 4 gesehen. Wenn die Verschachtelung so tief wird, möchten Sie jedoch sicherstellen, dass das Testen aller von ihnen wirklich schneller ist, als nur die minimalen Tests durchzuführen, die von der Kurzschlussbewertung vorgeschlagen werden.

GCC ist bereits intelligent genug, um Bedingungen durch einfachere Anweisungen zu ersetzen. Das bieten zum Beispiel neuere Intel-Prozessoren cmov (bedingter Zug). Wenn Sie es verwenden können, bietet SSE2 einige Anweisungen dazu Vergleiche 4 ganze Zahlen (oder 8 Kurzschlüsse oder 16 Zeichen) gleichzeitig.

Zusätzlich zum Berechnen des Minimums können Sie verwenden (siehe diese Zaubertricks):

min(x, y) = x+(((y-x)>>(WORDBITS-1))&(y-x))

Achten Sie jedoch auf Dinge wie:

c[i][j] = min(c[i][j], c[i][k] + c[j][k]);   // from Floyd-Warshal algorithm

auch wenn keine Sprünge impliziert sind, ist viel langsamer als

int tmp = c[i][k] + c[j][k];
if (tmp < c[i][j])
    c[i][j] = tmp;

Meine beste Vermutung ist, dass Sie im ersten Snippet den Cache häufiger verschmutzen, während Sie dies im zweiten nicht tun.

Wenn Sie dieses Optimierungsniveau erreichen, ist es meiner Meinung nach wahrscheinlich an der Zeit, direkt in die Assemblersprache einzusteigen.

Im Wesentlichen verlassen Sie sich darauf, dass der Compiler ein bestimmtes Assemblermuster generiert, um diese Optimierung in C ohnehin zu nutzen. Es ist schwierig, genau zu erraten, welchen Code ein Compiler generieren wird, also müssten Sie ihn sich jedes Mal ansehen, wenn eine kleine Änderung vorgenommen wird – warum nicht einfach in Assembler und fertig?