CPU-Branch-Prediction: Der versteckte Flaschenhals im Code

Es gibt eine berühmte Stack-Overflow-Antwort, die über 3 Millionen Mal aufgerufen wurde. Die Frage: Warum ist die Verarbeitung eines sortierten Arrays schneller als die eines unsortierten? Der Code ist identisch — eine Schleife mit einer if-Anweisung. Der einzige Unterschied ist, ob das Eingabe-Array sortiert ist. Die sortierte Version läuft 6x schneller. Die Erklärung — CPU Branch Prediction — zeigt einen der wichtigsten Performance-Faktoren in moderner Informatik.

Jede if-Anweisung, jede Schleifenbedingung, jeder switch-Case — das sind Verzweigungen in deinem Code. Deine CPU trifft Milliarden davon pro Sekunde und muss das Ergebnis jeder einzelnen vorhersagen, bevor sie die tatsächliche Antwort kennt. Liegt sie richtig, läuft die Ausführung mit voller Geschwindigkeit weiter. Liegt sie falsch, verwirft die CPU 10–20 Takte Arbeit und fängt von vorne an. Wer diesen Mechanismus versteht, betrachtet performancekritischen Code mit ganz anderen Augen.

Warum CPUs vorhersagen müssen

Moderne CPUs arbeiten mit Pipelines: Sie warten nicht, bis ein Befehl fertig ist, bevor sie den nächsten starten. Eine typische CPU-Pipeline hat 12–20 Stufen. Während ein Befehl ausgeführt wird, werden bereits die nächsten rund 15 Befehle geholt, dekodiert und vorbereitet. Genau dieses Pipelining ermöglicht es, dass CPUs trotz mehrtaktiger Befehle etwa einen Befehl pro Takt abarbeiten.

Trifft die CPU aber auf eine Verzweigung (if x > 0), gibt es ein Problem. Der nächste Befehl hängt davon ab, ob der Sprung genommen wird oder nicht. Die CPU kennt das Ergebnis erst nach mehreren Takten, denn das Vergleichsergebnis muss erst durch die Pipeline wandern. Sie hat zwei Möglichkeiten: die Pipeline anhalten und warten (und dabei 15+ Takte nichts tun) oder die Richtung raten und weiterarbeiten.

CPUs raten immer. Der Branch Predictor trifft eine Vorhersage, und die CPU holt und führt Befehle entlang des vorhergesagten Pfads aus. War die Vorhersage richtig, geht nichts verloren. War sie falsch, muss die CPU die falsch ausgeführten Befehle verwerfen, ihre Ergebnisse wegwerfen und auf dem richtigen Pfad neu starten. Dieser sogenannte Pipeline-Flush kostet auf modernen x86-CPUs etwa 15–20 Takte — also so viel wie 15–20 verlorene Befehle.

So arbeiten Branch Predictors

Moderne Branch Predictors sind erstaunlich ausgefeilt. Im Kern sind es Mustererkennungs-Hardware, die aus der Historie jedes Verzweigungsbefehls lernt.

Der einfache Fall: verzerrte Verzweigungen

Viele Verzweigungen sind stark verzerrt — sie gehen fast immer in dieselbe Richtung. Eine Fehlerprüfung, die in 99,9 % der Fälle erfolgreich ist, oder eine Schleifenbedingung, die 999-mal wahr und dann einmal falsch ist. Der Branch Predictor lernt solche Muster schnell und erreicht nahezu perfekte Trefferquoten. Eine Verzweigung, die in 99 % der Fälle gleich verläuft, hat höchstens eine Fehlvorhersagerate von 1 %.

Mustererkennung

Moderne Predictors gehen über einfaches Bias-Tracking hinaus. Sie erkennen wiederkehrende Muster. Folgt eine Verzweigung dem Muster genommen-genommen-nicht genommen-genommen-genommen-nicht genommen... (Periode 3), lernt der Predictor dieses Muster und sagt es korrekt voraus. Der in modernen Intel- und AMD-CPUs eingesetzte TAGE-Predictor (TAgged GEometric history length) pflegt mehrere History-Tabellen mit unterschiedlichen Historienlängen und erkennt so Muster mit Perioden von 2 bis zu einigen hundert.

Korrelierte Verzweigungen

Die fortschrittlichsten Predictors lernen zudem Zusammenhänge zwischen Verzweigungen. Wenn das Genommenwerden von Verzweigung A immer bedeutet, dass Verzweigung B (weiter hinten im Code) nicht genommen wird, kann der Predictor diese Beziehung erlernen. Man spricht von „zweistufiger adaptiver Vorhersage“, und sie behandelt Codemuster wie:

// These branches are correlated
if (x > 0) {      // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) {     // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracy

Das Rätsel um das sortierte Array aufgelöst

Zurück zur berühmten Stack-Overflow-Frage. Der Code sieht so aus:

int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128)    // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cycles

Bei sortierten Daten ist die Verzweigung perfekt vorhersagbar: Sie wird in der ersten Hälfte des Arrays nicht genommen und in der zweiten Hälfte genommen. Der Predictor lernt jede Phase schnell und liegt nur an der einen Übergangsstelle daneben. Bei zufälligen Daten ist die Verzweigung praktisch ein Münzwurf — der Predictor kommt nicht über etwa 50 % Trefferquote hinaus, und die Hälfte der Iterationen verschwendet 15 Takte durch Pipeline-Flushes.

Bei 100.000 Iterationen und einer Fehlvorhersagerate von etwa 50 % sind das 50.000 Fehlvorhersagen × 15 Takte = 750.000 verschwendete Takte. Auf einer 3-GHz-CPU entspricht das etwa einer viertel Millisekunde — ein beachtlicher Anteil der Gesamtlaufzeit für diese einfache Schleife.

Wie viele Verzweigungen kann deine CPU verarbeiten?

Der Branch Predictor hat begrenzten Speicher. Er verfolgt die Historie für eine endliche Anzahl von Verzweigungsstellen über eine Struktur namens Branch Target Buffer (BTB) und die zugehörigen History-Tabellen. Moderne CPUs können zehntausende Verzweigungsstellen verfolgen, große Codebasen können diese Grenze aber überschreiten.

Wenn zwei verschiedene Verzweigungsbefehle auf denselben Predictor-Eintrag abgebildet werden (weil der BTB über einen Hash der Befehlsadresse indiziert wird), beeinflussen sie sich gegenseitig in ihren Vorhersagen. Im normalen Code ist das selten, wird aber bei sehr großen Funktionen oder vielen kleinen Funktionen mit jeweils eigenen Verzweigungen relevant.

Daniel Lemire hat exzellente Untersuchungen veröffentlicht, die die Kapazität von Branch Predictors auf verschiedenen CPUs messen. Die Ergebnisse zeigen, dass moderne Intel-CPUs (Alder Lake und neuer) Verzweigungen mit Historien von bis zu etwa 200 Verzweigungen effektiv vorhersagen können — der Predictor berücksichtigt also die Ergebnisse der letzten ~200 Verzweigungen bei der Vorhersage der aktuellen. AMD-CPUs haben eine ähnliche Kapazität. ARM-Chips variieren stärker; die M-Serie von Apple hat besonders starke Branch Predictors.

Branch-Prediction-freundlichen Code schreiben

In den meisten Codes spielt Branch Prediction keine Rolle. Der Predictor ist gut genug, und die Verzweigungen liegen nicht in heißen Schleifen. Wenn du aber performancekritische Pfade optimierst — innere Schleifen, Datenverarbeitungs-Pipelines, Parser, Codecs — kann das Verzweigungsverhalten die Laufzeit dominieren.

Verzweigungen durch Arithmetik ersetzen

Der schnellste Branch ist der, den es nicht gibt. Viele bedingte Konstrukte lassen sich durch verzweigungsfreie Arithmetik ersetzen.

// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo;  // CMOV
return t < hi ? t : hi;   // CMOV
}

Moderne Compiler wandeln einfache Bedingungen meist gut in CMOV-Befehle (Conditional Move) um, die Verzweigungen komplett vermeiden. Sie schaffen das aber nicht immer — besonders dann nicht, wenn die Zweige Seiteneffekte haben oder der „then“-Pfad teuer ist. Explizit verzweigungsfreie Muster helfen in heißen Schleifen, wenn der Compiler keinen optimalen Code erzeugt.

Vor der Verarbeitung sortieren

Wenn du Daten mit einer Verzweigung filterst, macht Sortieren vorab die Verzweigung perfekt vorhersagbar. Das klingt widersprüchlich — Sortieren kostet O(n log n) — aber bei großen Datenmengen, bei denen die Schleife oft läuft oder die Kosten der Fehlvorhersagen hoch sind, zahlt sich das Sortieren aus.

Lookup-Tabellen verwenden

Komplexe bedingte Logik (switch-Anweisungen mit vielen Fällen) lässt sich durch Tabellenzugriffe ersetzen. Statt einer Kette von Vergleichen indizierst du direkt in ein Array. Der Array-Zugriff kann einen Cache-Miss verursachen, ist aber meist günstiger als eine Kaskade falsch vorhergesagter Verzweigungen.

// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}

Dem Compiler Hinweise geben

GCC und Clang unterstützen __builtin_expect, um dem Compiler mitzuteilen, welche Verzweigungsrichtung wahrscheinlich ist. Das steuert nicht direkt den Branch Predictor der CPU (der zur Laufzeit lernt), beeinflusst aber das Code-Layout: Der wahrscheinliche Pfad wird geradlinig ohne Sprünge angeordnet, was wegen der Effekte im Befehls-Cache schneller ist.

// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}

Verzweigungsverhalten messen

Die Leistung von Branch Prediction lässt sich direkt mit Hardware-Performance-Countern messen. Unter Linux liefert perf stat dir die Fehlvorhersageraten für jedes beliebige Programm.

# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256  branches          # 892.7M/sec
3,271,842  branch-misses     # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.

Für Mikrobenchmarks können Tools wie Google Benchmark die branch-misses pro Iteration erfassen. So bekommst du präzises Feedback, ob eine Codeänderung das Verzweigungsverhalten verbessert hat. Das ist aussagekräftiger als die Wanduhrzeit, die Rauschen durch andere Systemaktivitäten enthält.

Wann es sich lohnt (und wann nicht)

Die Optimierung von Branch Prediction ist in einer schmalen, aber wichtigen Kategorie von Code relevant: enge innere Schleifen, die große Datenmengen verarbeiten. Parser, Kompressoren, Bildverarbeitung, numerische Berechnungen, Auswertung von Datenbankabfragen — hier dominiert das Verzweigungsverhalten.

Für alles andere — Business-Logik, API-Handler, CRUD-Operationen — ist Branch Prediction irrelevant. Die Verzweigungen im Request-Router deines Webservers sind nicht dein Engpass. Schreib lesbare if/else-Ketten nicht in unlesbare verzweigungsfreie Arithmetik um, wenn der Code nur einmal pro HTTP-Request läuft. Optimiere dort, wo der Profiler es dir sagt, nicht dort, wo die Theorie ein mögliches Problem vermutet.

Der eigentliche Nutzen, Branch Prediction zu verstehen, liegt nicht in manueller Optimierung, sondern darin, zu begreifen, warum dein Code so performt, wie er performt. Wenn ein Profiler zeigt, dass eine simple Schleife mit einer if-Anweisung langsamer ist als erwartet, ist oft eine Fehlvorhersage die Erklärung. Und wenn das Sortieren der Eingabedaten die Verarbeitung auf einmal beschleunigt, steckt ebenfalls Branch Prediction dahinter. Dieses mentale Modell hilft dir, Performance-Probleme zu diagnostizieren, die sonst rätselhaft bleiben würden.