Begriff
Branch Prediction
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Eine CPU ist wie ein Fließband (Pipeline). Sie arbeitet an 20 Befehlen gleichzeitig. Problem: Eine Kreuzung ("IF x > 0 THEN"). Die CPU weiß noch nicht, ob x > 0 ist (das wird noch berechnet). Soll sie warten? Nein, das würde das Fließband stoppen (Stall). Stattdessen rät sie: "Ich glaube, es geht links lang." Sie arbeitet auf Verdacht weiter (Speculative Execution). Wenn sie richtig lag: Super, keine Zeit verloren! Wenn sie falsch lag: Alles wegwerfen und den anderen Weg nehmen (Flush). Moderne CPUs raten mit >95% Genauigkeit richtig (dank KI-ähnlichen Perceptrons im Chip).
Merksatz: Ein Mechanismus in modernen Prozessoren, der versucht, das Ergebnis von bedingten Sprüngen (Branches) vorherzusagen, um die Befehlspipeline effizient gefüllt zu halten und Leerlaufzeiten zu vermeiden.
Als Programmierer:
Vermeide unvorhersehbare Sprünge in engen Loops.
if (random() > 0.5) ist der Horror für die CPU (50% Fehlrate).
Sortierte Daten sind schneller zu verarbeiten als unsortierte.
if (data[i] > 128) ist bei sortierten Daten immer "True" dann immer "False". Perfekt vorhersagbar.
1. Branch Target Buffer (BTB) & Pattern History Table (PHT)
Der Predictor merkt sich: "Dieser IF-Befehl an Adresse 0x1234 war die letzten 10 Male 'TAKEN'". Er nutzt 2-Bit Sättigungszähler (Strongly Taken, Weakly Taken...). Moderne Ryzens/Intels nutzen TAGE (Tagged Geometric History Length) oder Perceptron-Predictors, die globale Muster erkennen ("Immer wenn A wahr ist, ist auch B wahr").
2. Pipeline Flush Cost
Wenn die Vorhersage falsch war (Branch Misprediction), muss die CPU 15-20 Taktzyklen Arbeit wegwerfen.
Das ist extrem teuer.
Deshalb nutzen Compiler Techniken wie Branchless Programming (z. B. x = x * (a > b) statt if (a > b) x = 0).
1. Loop Unrolling & Vectorization
Der krasseste Feind des Branch Predictors ist eine Schleife, die unberechenbar iteriert.
Clevere Compiler (C++ -O3, Rust) betreiben Loop Unrolling. Statt einer for-Schleife, die 16 Mal prüft if (i < 16), kopiert der Compiler den Code im Body stumpf 16 Mal hintereinander ins Assembly (x++; x++; x++; ...). Das bläht zwar die .exe-Datei etwas auf, beseitigt aber das Loop-Condition-Branching restlos.
Modern kombiniert man das mit SIMD (Single Instruction Multiple Data: AVX-512): Ein CPU-Befehl rechnet 16 Operationen zeitgleich – ohne jeden bedingten Sprung. Das ist das Rückgrat von Pytorch-Laufzeiten.
2. Return Stack Buffer (RSB)
Neben Conditional Branches (if/else) gibt es die Return-Branches (return). Eine Funktion muss wissen, wohin im Code sie zurückspringt (die Return-Adresse).
Da der Return-Ort dynamisch sein kann, dachte man früher, das sei schwer vorherzusehen. Heutige CPUs haben dafür in Hardware den winzigen, extrem schnellen Return Stack Buffer (RSB). Wenn die Architektur ein CALL-Kommando sieht (Funktion springt ab), wirft sie die nächste Adresse wie einen Teller auf den RSB. Kommt dann das RET-Kommando (Return), poppt die CPU den Wert ab und rät: "Ich springe dorthin zurück". Ist die Aufruftiefe gigantisch tief (Deep Recursion) läuft dieser 16-Einträge kleine Puffer leider über und die CPU gerät tief ins Mispredict-Straucheln.
3. Eviction und Seiteneffekt-Analysen (Spectre/Meltdown)
Warum ist die Branch Prediction ein Sicherheitsrisiko? Eine Misprediction ("Ich überschreite eine Array Boundary auf Verdacht") wird sofort korrigiert und der flüchtige spekulative RAM-Wert eigentlich verworfen (Microarchitectural Rollback). Der Seiteneffekt bleibt aber im L1-Cache der CPU physisch liegen. Ein bösartiger Prozess kann durch gnadenloses Time-Messen (Evict and Time) Sekundenbruchteile später nachschauen, wie lang das Lesen einer Speicheradresse dauerte. War es sehr schnell? Dann hatte die Speculative Execution diesen Wert vorab aus unprivilegiertem Kernel-Space dorthin geladen. Der Branch-Predictor wurde so zur mächtigsten Cyberwaffe des Jahrhunderts (Spectre).
Quick-Check
Likely/Unlikely?
In C++ als Attributlikely/unlikelyoder im Kernel-Code alslikely(). Das sagt dem Compiler: "Optimiere den Code so, dass der erwartete Pfad geradeaus läuft." Das hilft dem Instruction Cache, nicht zwingend dem Branch Predictor, der zur Laufzeit lernt.Spectre?
Spectre nutzt Branch Prediction aus, um die CPU dazu zu bringen, spekulativ auf geheimen Speicher zuzugreifen. Man misst dann die Zeit (Cache Side Channel) und errät das Geheimnis.Static Prediction?
Wenn die CPU keine Historie hat (erster Besuch): "Rückwärtssprünge (Loops) werden meist genommen. Vorwärtssprünge (Ifs) eher nicht."