Branch Prediction della CPU: il collo di bottiglia nascosto del tuo codice

C'è una risposta famosa su Stack Overflow che è stata vista più di 3 milioni di volte. La domanda: perché elaborare un array ordinato è più veloce che elaborarne uno non ordinato? Il codice è identico, un loop con un if. L'unica differenza è se l'array in input è ordinato. La versione ordinata gira 6 volte più veloce. La spiegazione, cioè la branch prediction della CPU, rivela uno dei fattori di performance più rilevanti nell'informatica moderna.

Ogni if, ogni condizione di un loop, ogni case di uno switch sono branch nel tuo codice. La CPU ne incontra miliardi al secondo e deve prevedere l'esito di ciascuno prima di conoscere la risposta effettiva. Quando prevede bene, l'esecuzione prosegue a piena velocità. Quando sbaglia, la CPU butta via 10-20 cicli di lavoro e ricomincia da capo. Capire questo meccanismo cambia il modo in cui pensi al codice critico per le performance.

Perché le CPU devono prevedere

Le CPU moderne sono pipelined: non aspettano che un'istruzione finisca prima di iniziare la successiva. Una pipeline tipica è profonda 12-20 stadi. Mentre un'istruzione viene eseguita, le altre 15 circa sono già in fase di fetch, decodifica e preparazione. È questo pipelining che permette alle CPU di eseguire circa un'istruzione per ciclo di clock, anche se ciascuna richiede molti cicli per completarsi.

Ma quando la CPU incontra un branch (if x > 0), ha un problema. L'istruzione successiva dipende dal fatto che il branch sia preso o non preso. La CPU non conosce la risposta per diversi cicli, perché il risultato del confronto deve attraversare la pipeline. Ha due opzioni: fermare la pipeline e aspettare (sprecando 15+ cicli senza fare nulla), oppure indovinare la direzione del branch e continuare a lavorare.

Le CPU indovinano sempre. Il branch predictor fa una previsione e la CPU recupera ed esegue le istruzioni lungo il percorso previsto. Se la previsione era corretta, non si spreca nulla. Se era sbagliata, la CPU deve scartare le istruzioni eseguite per errore, buttare via i loro risultati e ripartire dal percorso corretto. Questo 'pipeline flush' costa circa 15-20 cicli sulle CPU x86 moderne, l'equivalente di 15-20 istruzioni di lavoro perso.

Come funzionano i branch predictor

I branch predictor moderni sono straordinariamente sofisticati. Sono essenzialmente hardware di riconoscimento di pattern che impara dalla cronologia di ciascuna istruzione di branch.

Il caso semplice: branch sbilanciati

Molti branch sono fortemente sbilanciati e quasi sempre vanno nella stessa direzione. Un controllo degli errori che va a buon fine il 99,9% delle volte, una condizione di loop vera per 999 iterazioni e falsa una sola volta. Il branch predictor impara rapidamente questi pattern e raggiunge un'accuratezza quasi perfetta. Un branch che va nella stessa direzione il 99% delle volte ha al massimo un tasso di errore dell'1%.

Riconoscimento di pattern

I predictor moderni vanno oltre il semplice tracciamento della tendenza e riconoscono pattern ripetitivi. Se un branch segue la sequenza preso-preso-non preso-preso-preso-non preso... (periodo 3), il predictor imparerà questo pattern e lo prevederà correttamente. Il predictor TAGE (TAgged GEometric history length), usato nelle CPU Intel e AMD moderne, mantiene più tabelle della cronologia con lunghezze diverse, catturando pattern con periodi da 2 a diverse centinaia.

Branch correlati

I predictor più avanzati imparano anche le correlazioni tra branch. Se il fatto che il branch A sia preso significa sempre che il branch B (più avanti nel codice) non è preso, il predictor può apprendere questa relazione. Si chiama 'predizione adattiva a due livelli' e gestisce pattern di codice come:

// 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

Il mistero dell'array ordinato spiegato

Torniamo alla famosa domanda di Stack Overflow. Il codice è più o meno questo:

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

Con dati ordinati, il branch è perfettamente prevedibile: non è preso per la prima metà dell'array, poi è preso per la seconda. Il predictor impara rapidamente ciascuna fase e sbaglia solo nel singolo punto di transizione. Con dati casuali, il branch è essenzialmente un testa o croce: il predictor non può fare meglio di un'accuratezza del 50% circa, e metà delle iterazioni sprecano 15 cicli per i flush della pipeline.

Con 100.000 iterazioni e un tasso di errore del 50% circa, sono 50.000 previsioni sbagliate × 15 cicli = 750.000 cicli sprecati. Su una CPU a 3 GHz sono un quarto di millisecondo, una frazione significativa del tempo totale di esecuzione di un loop così semplice.

Quanti branch può gestire la tua CPU?

Il branch predictor ha uno spazio di archiviazione limitato. Tiene traccia della cronologia per un numero finito di posizioni di branch, usando una struttura chiamata Branch Target Buffer (BTB) e le relative tabelle della cronologia. Le CPU moderne possono tracciare decine di migliaia di posizioni di branch, ma i codebase grandi possono superare questo limite.

Quando due istruzioni di branch diverse finiscono nella stessa voce del predictor (perché il BTB è indicizzato tramite un hash dell'indirizzo dell'istruzione), interferiscono nelle reciproche previsioni. È raro nel codice normale, ma diventa rilevante in funzioni molto grandi o quando molte piccole funzioni contengono ciascuna dei branch.

Daniel Lemire ha pubblicato un'ottima ricerca che misura la capacità dei branch predictor su diverse CPU. I risultati mostrano che le CPU Intel moderne (Alder Lake e successive) riescono a prevedere efficacemente i branch con cronologie profonde fino a circa 200 branch, cioè il predictor considera gli esiti degli ultimi ~200 branch quando prevede quello attuale. Le CPU AMD hanno una capacità simile. I chip ARM variano di più; i chip Apple della serie M hanno predictor particolarmente potenti.

Scrivere codice amichevole per la branch prediction

Nella maggior parte del codice la branch prediction non conta: il predictor è abbastanza bravo e i branch non si trovano in loop critici. Ma quando ottimizzi percorsi critici per le performance, come loop interni, pipeline di elaborazione dati, parser e codec, il comportamento dei branch può dominare il tempo di esecuzione.

Sostituire i branch con l'aritmetica

Il branch più veloce è quello che non esiste. Molti pattern condizionali possono essere sostituiti con aritmetica senza branch.

// 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
}

I compilatori moderni sono generalmente bravi a convertire i condizionali semplici in istruzioni CMOV (conditional move), che evitano del tutto i branch. Non sempre ci riescono, però, soprattutto quando i branch hanno effetti collaterali o quando il percorso 'then' è costoso. I pattern espliciti senza branch aiutano nei loop critici dove il compilatore non genera codice ottimale.

Ordinare prima di elaborare

Se devi filtrare dati con un branch, ordinarli prima rende il branch perfettamente prevedibile. Sembra controintuitivo, perché l'ordinamento ha un costo O(n log n), ma per dataset grandi, dove il loop di elaborazione gira molte volte o dove il costo di una previsione sbagliata è alto, ordinare si ripaga.

Usare le lookup table

La logica condizionale complessa (switch con molti case) può essere sostituita con lookup table. Invece di una catena di confronti, si indicizza un array. L'accesso all'array può causare un cache miss, ma di solito costa meno di una cascata di branch sbagliati.

// 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];
}

Dare suggerimenti al compilatore

GCC e Clang supportano __builtin_expect per indicare al compilatore quale direzione del branch è più probabile. Questo non controlla direttamente il predictor della CPU, che impara a runtime, ma influenza il modo in cui il compilatore dispone il codice: mettere il percorso probabile in linea retta, senza salti, è più veloce grazie agli effetti della cache delle istruzioni.

// 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");
}

Misurare il comportamento dei branch

Puoi misurare direttamente le prestazioni della branch prediction usando i contatori hardware. Su Linux, perf stat ti fornisce i tassi di errore di previsione per qualsiasi programma.

# 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.

Per i micro-benchmark, strumenti come Google Benchmark possono tracciare i branch-misses per iterazione, dandoti un feedback preciso su una modifica che ha migliorato o meno il comportamento dei branch. È più utile del tempo di esecuzione reale, che include il rumore di altre attività di sistema.

Quando preoccuparsene (e quando no)

L'ottimizzazione della branch prediction conta in una categoria di codice stretta ma importante: i loop interni che elaborano grandi quantità di dati. Parser, compressori, elaborazione di immagini, calcolo numerico e valutazione di query nei database sono i casi in cui il comportamento dei branch domina.

Per tutto il resto, come logica di business, handler di API e operazioni CRUD, la branch prediction è irrilevante. I branch nel router delle richieste del tuo web server non sono il tuo collo di bottiglia. Non riscrivere catene if/else leggibili in aritmetica illeggibile senza branch in codice che gira una volta per richiesta HTTP. Ottimizza dove ti indica il profiler, non dove la teoria suggerisce che ci possa essere un problema.

Il vero valore di capire la branch prediction non sta nell'ottimizzazione manuale, ma nel capire perché il tuo codice va come va. Quando un profiler mostra che un semplice loop con un if è più lento del previsto, spesso la spiegazione è un errore di previsione del branch. Quando ordinare i dati in input accelera magicamente l'elaborazione, il motivo è ancora la branch prediction. Avere questo modello mentale ti permette di diagnosticare problemi di performance che altrimenti sembrerebbero misteriosi.