Che cos’è la branch prediction? All’interno di un computer abbiamo un circuito che ha il compito di capire quale ramo di un “if” eseguire. In differenti linguaggi di programmazione, se calcolassi il tempo necessario a processare un array ordinato e uno non ordinato, noterai che nel secondo caso ci vorrà più tempo. In questo articolo scoprirai tutto questo
A prescindere dalla dimensione dell’array e del suo contenuto, il motivo sta nella “branch prediction”.
Partiamo dalla definizione di branch prediction
Cerchiamo di capire cosa mai vorrà dire questa definizione con meno #tecnichese possibile 🙂
Ciao mi chiamo Lorenzo Neri e sono un informatico: realizzo contenuti per aiutare le persone a padroneggiare l’arte del nuovo millennio, ovvero l’informatica!
All’interno di un computer abbiamo un circuito digitale che ha il compito di capire quale ramo di un “if”, quindi branch in inglese, deve eseguire prima ancora che si sappia in via definitiva.
Ci arriviamo a lui, a questo famoso circuito!
Ma prima di tutto: perché mai dovrebbe essere necessaria una cosa del genere?
Pensiamo un attimo alla classica struttura di un “if-then-else”: abbiamo due rami con all’interno del codice da eseguire.
Il primo ramo verrà eseguito se la condizione viene verificata, diversamente verrà eseguito il secondo.
E qui, dobbiamo fare un piccolo passo indietro: i salti condizionati.
Erano molto in voga quando si programmava con il famoso codice spaghetti 😀
Per fartela molto breve, i salti condizionati funzionano così: abbiamo un punto del codice in cui scriviamo la nostra condizione, quella dell’if per intenderci.
Se questa viene verificata, il programma “salta” direttamente alla porzione di codice che dev’essere eseguita: in altre parole, quella che viene scritta all’interno dell’if stesso.
Diversamente, se la condizione non viene verificata, il programma NON salta alla porzione di codice dell’if ed esegue subito quella scritta nelle righe successive al salto.
In altre parole funziona come il classico if-then-else ma ribaltato!
E questo potrebbe essere un buon motivo anche per leggere qualcosa sull’imparare a programmare 😉
Per nostra sfortuna però, il processore non sa immediatamente cosa deve fare: non è così tanto intelligente come può sembrare!
Infatti, deve aspettare che il salto condizionato venga calcolato e quindi interrompe l’esecuzione del programma finché non sa la risposta!
Il processore dice a se stesso: “Bene, aspettiamo che venga calcolata questa condizione del salto, poi provvedo ad eseguire il codice dell’if oppure dell’else”.
Non ci possiamo permettere una tale attesa, immagina a ragionare in questi termini con un array da un milione di celle!
Ed è qui che subentra l’alleato del processore: il branch predictor.
Il branch predictor non è nient’altro che il circuito digitale di cui parlavamo poco fa.
Chi è il Branch Predictor, cosa fa e a cosa serve
Torniamo al problema del processore: vede il branch, ma non sa come gestirlo.
Cosa facciamo? Stoppiamo l’esecuzione ed aspettiamo di essere sicuri che la condizione sia verificata oppure no?
Assolutamente no! Immagina quanto spreco di tempo!
Il branch predictor è un po’ come un mago indovino.
Fa una predizione in questo modo:
“Secondo me questo if è verificato”: il branch predictor azzecca la previsione e si prosegue ad eseguire il codice.
Oppure succede che non ci azzecca, si torna momentaneamente indietro per eseguire l’altro ramo del nostro if-then-else.
Quindi che cos’è la branch prediction? È come tirare una moneta: avrò sempre il 50% di probabilità di azzeccarci!
… Per nostra fortuna no!
Il branch predictor non è così stupido: gode di buona memoria sulle previsioni che ha fatto in passato, ve lo dicevo che era un mago.
Ogni volta che deve fare una previsione e capire quale ramo eseguire, prima ancora di annunciare la sua “visione”, guarda alla storia passata e si confronta con se stesso.
In questo modo, il branch predictor, almeno in quelli moderni usati oggigiorno, può raggiungere una probabilità di successo maggiore del 90%.
