Welche Techniken zu vermeiden, die bedingte Verzweigung, weißt du?

Manchmal ist eine Schleife, wo die CPU verbringt die meiste Zeit hat Sie einige branch prediction miss (misprediction) sehr oft (in der Nähe .5 Wahrscheinlichkeit.) Ich habe gesehen, ein paar Techniken, die auf sehr vereinzelte threads, aber nie eine Liste. Die meisten die ich kenne bereits fix Situationen, in denen der Zustand kann sich zu einem bool und 0/1 verwendet wird, in irgendeiner Weise zu ändern. Gibt es andere, bedingten Verzweigungen, die vermieden werden können?

z.B. (pseudocode)

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

Umgeschrieben werden kann, wohl verlieren einige Lesbarkeit, mit so etwas wie dies:

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

Zudem habe ich gesehen, Techniken in der wildnis ändern && zu & in den Bedingungen, in bestimmten Kontexten entkommen meinem Kopf jetzt. Ich bin ein Neuling auf dieser Ebene der Optimierung, aber es sicher fühlt sich an wie es muss mehr sein.

Schlechtes Beispiel. Auch wenn die astfreie code gesehen werden kann, als gleichwertig mit dem original, das auch nur, wenn der ursprüngliche code hat keinen Sinn, in den ersten Platz.
warum so viele Menschen reagieren mit einer Antwort, die nicht wirklich die Beantwortung der Frage, ist mir schleierhaft

InformationsquelleAutor alecco | 2009-10-24

assembly c optimization

11

Ich glaube, der häufigste Weg, dies zu vermeiden ist die Verzweigung zu nutzen, bit-Parallelität, bei der Verringerung der Gesamt-Sprünge in Ihrem code. Je länger die grundlegenden Blöcke, desto weniger oft wird die pipeline geleert wird.

Als jemand anderes erwähnt hat, wenn Sie mehr tun wollen, als unrolling loops, und bietet branch Tipps, die Sie gehen zu wollen, um die drop-in-Montage. Natürlich sollte dies mit größter Vorsicht: die typische compiler schreiben kann, besser Montage in den meisten Fällen als ein Mensch. Ihre beste Hoffnung ist, abrasieren Ecken und Kanten, und die Annahmen, die der compiler nicht ableiten.

Hier ist ein Beispiel der folgenden C-code:
```
if (b > a) b = a;
```
In der Montage-ohne Sprünge, indem Sie mit bit-manipulation (und extreme Kommentare):
```
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 während der bedingte Bewegungen sprang sofort auf, indem Sie Montage-Enthusiasten, das ist nur, weil Sie sind leicht zu verstehen und bieten eine höhere Sprache Konzept in einem komfortablen Einzel Unterricht. Sie sind nicht unbedingt schneller, nicht verfügbar auf älteren Prozessoren, und durch die Zuordnung des C-code in die entsprechenden bedingten move-Anweisungen, die Sie tun, die Arbeit des Compilers.
- Hm, nicht Ihren assembler-code übernehmen keine überlauf auf sub eax, exb?
InformationsquelleAutor Matt Joiner
13

Mit Matt Tischler Beispiel:
```
if (b > a) b = a;
```
Könnten Sie auch Folgendes tun, ohne zu Graben in Assembler-code:
```
bool if_else = b > a;
b = a * if_else + b * !if_else;
```
InformationsquelleAutor roennowmads
8

Die Verallgemeinerung von Beispiel Sie geben, ist "ersetzen bedingte Auswertung mit Mathematik"; conditional branch Vermeidung weitgehend darauf hinauslaufen, dass.

Was ist Los mit einbauen && mit & ist, dass, da && ist der Kurzschluss, es stellt die bedingte Bewertung an und für sich. & bekommt man die gleichen logischen Ergebnis, wenn beide Seiten entweder 0 oder 1, und ist nicht kurzschlussfest. Dasselbe gilt für || und | außer Sie nicht brauchen, um sicherzustellen, dass die Seiten gezwungen sind, zu 0 oder 1 (wieder, für die Logik Zwecken, d.h. Sie sind mit dem Ergebnis nur Booleanly).

InformationsquelleAutor chaos
5

Auf dieser Ebene Dinge sind sehr abhängig von der verwendeten hardware-und compiler-abhängig. Ist der compiler Sie verwenden intelligent genug, um zu kompilieren < ohne Ablaufsteuerung? gcc auf x86 ist schlau genug; lcc nicht. Auf älteren oder embedded-Befehl setzt, kann es nicht möglich sein, berechnen < ohne Ablaufsteuerung.

Jenseits dieser Cassandra-wie Warnung, es ist schwer, um jede hilfreiche Allgemeine Aussagen. So, hier sind einige Allgemeine Aussagen, die möglicherweise nicht hilfreich:
- Moderne branch-prediction-hardware ist erschreckend gut. Wenn Sie finden konnte, ein richtiges Programm, wo schlechte branch prediction Kosten von mehr als 1%-2% Verlangsamung, wäre ich sehr überrascht.
- Leistungsindikatoren oder andere tools, die Ihnen sagen, wo Sie zu finden, Zweig mispredictions unverzichtbar sind.
- Wenn Sie wirklich brauchen, um eine Verbesserung dieser code würde ich schauen in das trace-scheduling und loop-unrolling:
  - Loop unrolling repliziert loop-Körper und gibt Ihre Optimierer mehr Steuern fließen, mit zu arbeiten.
  - Trace scheduling identifiziert, welche Pfade Sie am wahrscheinlichsten genommen werden, und unter anderen tricks, Sie können zwicken die Filiale Richtungen, so dass die branch-prediction-hardware funktioniert besser auf die häufigsten Pfade. Mit ent-Schleifen, es gibt mehr und längere Wege, so dass die trace-scheduler hat mehr Arbeit mit
- Ich würde misstrauisch zu versuchen, die Codes selbst in der Montage. Wenn der nächste chip kommt mit neue branch-prediction-hardware, stehen die Chancen ausgezeichnet, dass alle Ihre harte Arbeit den Bach runtergeht. Sondern ich würde schauen für ein feedback-directed compiler-Optimierung.
- Cool, danke! Ich mache SIMD-Kompression, Sortierung und Suche in großen Datenmengen. Es macht einen Unterschied, wenn die Wahrscheinlichkeit über .5 (das ist der Grund, warum das in der Frage am Anfang.) Naja, sparen Itanium oder Architekturen wie, aber das ist nicht mein Fall. Die Art der Daten unterscheidet sich erheblich, da es nicht speziell für eine Art von dataset (es könnte sein, zufälliges, inkrementelle, etc.) So feedback wird helfen, aber bis zu einem gewissen Punkt. Und es gibt viele Fälle, wie das Beispiel in der Frage, die einfach gelöst werden können, ohne selbst Tauchen in der Montage. Das ist meine quest 🙂
InformationsquelleAutor Norman Ramsey
4

GCC ist schon schlau genug, zu ersetzen, die Bedingungen mit den einfachen Anweisungen. Zum Beispiel neuere Intel-Prozessoren bieten cmov (conditional move). Wenn Sie es verwenden können, SSE2 bietet einige Anweisungen, um vergleichen Sie 4 ganze zahlen (oder 8 shorts oder 16 chars) zu einem Zeitpunkt.

Zusätzlich zu berechnen, die Sie verwenden können (siehe diese magic tricks):
```
min(x, y) = x+(((y-x)>>(WORDBITS-1))&(y-x))
```
Aber achten Sie auf Dinge wie:
```
c[i][j] = min(c[i][j], c[i][k] + c[j][k]);   //from Floyd-Warshal algorithm
```
selbst keine Sprünge impliziert sind 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 in der ersten snippet, das Sie verschmutzen den cache öfter, während in der zweiten nicht.
- Beachten Sie, dass cmov hat den Nachteil, dass Sie als abhängig von Ihrer Quell-Operanden aus der Sicht der Instruktion, die Neuordnung und die parallele Ausführung. Für einen Zustand, der oft falsch, eine gut vorhergesagt bedingte Sprung kann schneller sein als ein Abwürgen cmov.
InformationsquelleAutor Alexandru
2

Meiner Meinung nach, wenn Sie bis hinunter auf das Niveau der Optimierung, ist es wahrscheinlich Zeit, um die drop direkt in Assembler.

Im wesentlichen Sie zählen auf den compiler generieren ein spezifisches Muster von Montage-nutzen-Optimierung in C sowieso. Es ist schwer zu erraten, genau das, was code, den ein compiler wird zu generieren, so würden Sie haben, um es zu betrachten und jederzeit eine kleine änderung gemacht ist - warum nicht tun Sie es einfach in der Montage und mit ihm getan werden?
- Wahr. Das ist, warum die assembly-tag. Wenn Sie Techniken, die in der assembly für diese Art der Optimierung wäre es sehr geschätzt, wenn Sie teilen können (links zu!)
- Ich bin mir nicht sicher, es gibt viel, was ich teilen kann - meine Montage ist meist auf der Seite Lesen (beim Debuggen) oder hardware-level " - Sachen, die nicht getan werden kann, die in C (nicht Optimierung) für eingebettete Systeme. Eine Sache, die pops in meinem Kopf ist ARM spezifisch ist,und nicht viel von einem trick. ARM-Anweisungen, die ein Feld besitzen, die es Ihnen erlauben, die bedingt ausgeführt werden, also anstatt zu springen, um Sie wirksam werden in NOPs für die keine Wirkung auf die instruction-pipeline.
InformationsquelleAutor Michael Burr
2

Meisten Prozessoren bieten branch prediction, die besser ist als 50%. In der Tat, wenn Sie eine 1% Verbesserung in der branch prediction, dann können Sie wahrscheinlich veröffentlichen ein Papier. Es gibt einen Berg von Papieren zu diesem Thema, wenn Sie interessiert sind.

Du bist besser dran, sich Gedanken über die cache-hits und-misses.
- Ich habe festgestellt, dass-zumindest in einigen Fällen-die Lösung für branch prediction findet, ist oft auch besser für die cache-Leistung. Es kann eine win-win-Situation.
InformationsquelleAutor BobbyShaftoe
2

Eine Erweiterung der Technik gezeigt, in der ursprünglichen Frage gilt, wenn Sie mehrere verschachtelte tests, um eine Antwort zu bekommen. Können Sie bauen einen kleinen Bitmaske aus den Ergebnissen aller tests, und das "look up", die Antwort in eine Tabelle.
```
if (a) {
  if (b) {
    result = q;
  } else {
    result = r;
  }
} else {
  if (b) {
    result = s;
  } else {
    result = t;
  }
}
```
Wenn a und b sind fast zufällig (z.B. aus beliebigen Daten), und dies ist in einer engen Schleife, dann die branch prediction Ausfälle können wirklich diese langsam nach unten. 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];
```
Kann man verallgemeinern, um mehrere Bedingungen. Ich habe es getan für 4. Wenn die Verschachtelung wird, dass Tiefe, obwohl, werden Sie wollen, stellen Sie sicher, dass diese alle zu testen, ist wirklich schneller als nur die minimal-tests vorgeschlagen, die von short-circuit-evaluation.

InformationsquelleAutor Adrian McCarthy
1

Diese Stufe der Optimierung ist unwahrscheinlich, um eine lohnende Differenz in alle, aber die heißesten hotspots. Angenommen, es ist (ohne es zu beweisen in einem bestimmten Fall) ist eine form der raten, und die erste Regel der Optimierung ist Verhalten sich nicht auf Vermutungen.
- Ich denke, dass das Beispiel in der Frage ist ganz real und weit entfernt von raten. In der Tat ist es richtig, es in diesem code. Dies ist natürlich für die innersten Komponenten der tight loops für die Komprimierung/Sortierung/Suche, also es ist definitiv ein hotspot. Es ist nicht die Optimierung von Hallo-Welt-nur für kicks. Danke.
- Hier ist, was ich meine. Pick ein echtes Programm, nicht eine, die erstellt wird, nur eine Frage zu stellen. Einige performance-tuning drauf, um wirklich wringen Sie es aus. Themen wie branch-prediction nicht kommen, bis alles andere ausgereizt ist, also beginnend mit der Annahme, dass Sie wirklich nicht egal, basierend auf wissen, was die Probleme eigentlich sind. stackoverflow.com/questions/926266/...
- ... zur gleichen Zeit, wenn Sie runter, um hotspots wie, dass, Sie haben Recht, Sie können einen Unterschied machen. (Tut mir Leid. Für mich ist es ein hot-button Problem, dass viele Leute scheinen zu denken, dass die Optimierung beginnt und endet auf dem niedrigen Niveau, wenn das ist nur die Spitze des Eisbergs.)
- Ja, in der Tat. Auch gibt es mehr obskure performance-Sanktionen wie diese Seite-teilt-oder cache-line-teilt. Aber ich weiß, wie man mit diesen bereits (und vorbeugende Maßnahmen sind bereits in der Planung.) Cheers.
InformationsquelleAutor Mike Dunlavey

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.