Previsione dei rami in Java

1. Introduzione

Branch Prediction è un concetto interessante nell'informatica e può avere un profondo impatto sulle prestazioni delle nostre applicazioni. Eppure generalmente non è ben compreso e la maggior parte degli sviluppatori vi presta pochissima attenzione.

In questo articolo, esploreremo esattamente cos'è, come influisce sul nostro software e cosa possiamo fare al riguardo.

2. Cosa sono le condutture di istruzioni?

Quando scriviamo un programma per computer, stiamo scrivendo una serie di comandi che ci aspettiamo che il computer esegua in sequenza.

I primi computer eseguivano questi uno alla volta. Ciò significa che ogni comando viene caricato in memoria, eseguito nella sua interezza e solo quando è completato verrà caricato il successivo.

Le pipeline di istruzioni sono un miglioramento rispetto a questo. Consentono al processore di dividere il lavoro in pezzi e quindi eseguire diverse parti in parallelo. Ciò consentirebbe quindi al processore di eseguire un comando durante il caricamento del successivo, pronto per l'uso.

Tubazioni più lunghe all'interno del processore non solo consentono di semplificare ogni parte, ma consentono anche di eseguire più parti in parallelo. Ciò può migliorare le prestazioni complessive del sistema.

Ad esempio, potremmo avere un semplice programma:

int a = 0; a += 1; a += 2; a += 3;

Questo potrebbe essere elaborato da una pipeline composta da segmenti Fetch, Decode, Execute, Store come:

Possiamo vedere qui come l'esecuzione complessiva dei quattro comandi viene eseguita in parallelo, rendendo così più veloce l'intera sequenza.

3. Quali sono i pericoli?

Certo, i comandi che il processore deve eseguire causeranno problemi per il pipelining . Questi sono tutti i comandi in cui l'esecuzione di una parte della pipeline dipende da parti precedenti, ma in cui quelle parti precedenti potrebbero non essere state ancora eseguite.

I rami sono una forma specifica di pericolo. Fanno sì che l'esecuzione vada in una delle due direzioni e non è possibile sapere in quale direzione finché il ramo non viene risolto. Ciò significa che qualsiasi tentativo di caricare i comandi oltre il ramo non è sicuro perché non abbiamo modo di sapere da dove caricarli.

Cambiamo il nostro semplice programma per introdurre un ramo:

int a = 0; a += 1; if (a < 10) { a += 2; } a += 3;

Il risultato è lo stesso di prima, ma abbiamo introdotto un'istruzione if nel mezzo. Il computer lo vedrà e non sarà in grado di caricare i comandi oltre finché non sarà stato risolto . In quanto tale, il flusso sarà simile a:

Possiamo immediatamente vedere l'impatto che questo ha sull'esecuzione del nostro programma e quanti passi di clock sono stati necessari per eseguire lo stesso risultato.

4. Che cos'è la previsione di filiale?

Branch Prediction è un miglioramento di quanto sopra, in cui il nostro computer tenterà di prevedere in che direzione andrà un ramo e quindi agirà di conseguenza.

Nel nostro esempio precedente, il processore potrebbe prevedere che se (a <10) è probabile che sia vero , e quindi agirà come se l'istruzione a + = 2 fosse la successiva da eseguire. In questo modo il flusso avrà un aspetto simile a:

Possiamo vedere subito che questo ha migliorato le prestazioni del nostro programma : ora richiede nove tick e non 11, quindi è più veloce del 19%.

Questo non è senza rischi, però. Se la predizione del ramo sbaglia, inizierà a mettere in coda le istruzioni che non dovrebbero essere eseguite. Se ciò accade, il computer dovrà buttarli via e ricominciare da capo.

Trasformiamo il nostro condizionale in modo che ora sia falso :

int a = 0; a += 1; if (a > 10) { a += 2; } a += 3;

Questo potrebbe eseguire qualcosa come:

Ora è più lento del flusso precedente, anche se stiamo facendo di meno! Il processore ha previsto erroneamente che il ramo avrebbe valutato true , ha iniziato ad accodare l' istruzione a + = 2 , quindi ha dovuto scartarlo e ricominciare da capo quando il ramo è risultato falso.

5. Impatto reale sul codice

Ora che sappiamo cos'è la previsione del ramo e quali sono i vantaggi, come può influire su di noi? Dopotutto, stiamo parlando di perdere alcuni cicli del processore su computer ad alta velocità, quindi sicuramente non sarà evidente.

E a volte è vero. Ma a volte può fare una differenza sorprendente per le prestazioni delle nostre applicazioni. Dipende molto da quello che stiamo facendo esattamente. Nello specifico, dipende da quanto stiamo facendo in poco tempo.

5.1. Conteggio voci elenco

Proviamo a contare le voci in un elenco. Creeremo un elenco di numeri, quindi conteremo quanti di essi sono inferiori a un certo limite. È molto simile agli esempi precedenti, ma lo stiamo facendo in un ciclo invece che come una singola istruzione:

List numbers = LongStream.range(0, top) .boxed() .collect(Collectors.toList()); if (shuffle) { Collections.shuffle(numbers); } long cutoff = top / 2; long count = 0; long start = System.currentTimeMillis(); for (Long number : numbers) { if (number < cutoff) { ++count; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} {} numbers in {}ms", count, top, shuffle ? "shuffled" : "sorted", end - start);

Nota che stiamo solo cronometrando il ciclo che esegue il conteggio perché questo è ciò che ci interessa. Quindi, quanto tempo ci vuole?

Se stiamo generando elenchi sufficientemente piccoli, il codice viene eseguito così velocemente che non può essere programmato: un elenco di dimensioni 100.000 mostra ancora un tempo di 0 ms. Tuttavia, quando l'elenco diventa abbastanza grande da poterlo cronometrare, possiamo vedere una differenza significativa in base al fatto che abbiamo mescolato o meno l'elenco. Per un elenco di 10.000.000 di numeri:

  • Ordinato - 44 ms
  • Mescolato - 221 ms

Cioè, l'elenco mescolato impiega 5 volte più tempo per contare rispetto all'elenco ordinato, anche se i numeri effettivi che vengono contati sono gli stessi.

Tuttavia, l'atto di ordinare l'elenco è significativamente più costoso rispetto al semplice conteggio. Dobbiamo sempre profilare il nostro codice e determinare se eventuali miglioramenti delle prestazioni sono vantaggiosi.

5.2. Ordine dei rami

Seguendo quanto sopra, sembra ragionevole che l'ordine dei rami in un'istruzione if / else debba essere importante . Cioè, potremmo aspettarci che quanto segue abbia un rendimento migliore rispetto a se riordinassimo i rami:

if (mostLikely) { // Do something } else if (lessLikely) { // Do something } else if (leastLikely) { // Do something }

Tuttavia, i computer moderni possono evitare questo problema utilizzando la cache di previsione del ramo . In effetti, possiamo testare anche questo:

List numbers = LongStream.range(0, top) .boxed() .collect(Collectors.toList()); if (shuffle) { Collections.shuffle(numbers); } long cutoff = (long)(top * cutoffPercentage); long low = 0; long high = 0; long start = System.currentTimeMillis(); for (Long number : numbers) { if (number < cutoff) { ++low; } else { ++high; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} numbers in {}ms", low, high, end - start);

Questo codice viene eseguito più o meno nello stesso tempo - ~ 35 ms per i numeri ordinati, ~ 200 ms per i numeri mescolati - quando si contano 10.000.000 di numeri, indipendentemente dal valore di cutoffPercentage .

Questo perché il predittore del ramo gestisce entrambi i rami allo stesso modo e indovina correttamente in che modo andremo per loro.

5.3. Condizioni di combinazione

What if we have a choice between one or two conditions? It might be possible to re-write our logic in a different way that has the same behavior, but should we do this?

As an example, if we are comparing two numbers to 0, an alternative approach is to multiply them together and compare the result to 0. This is then replacing a condition with a multiplication. But is this worthwhile?

Let's consider an example:

long[] first = LongStream.range(0, TOP) .map(n -> Math.random()  Math.random() < FRACTION ? 0 : n) .toArray(); long count = 0; long start = System.currentTimeMillis(); for (int i = 0; i < TOP; i++) { if (first[i] != 0 && second[i] != 0) { ++count; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} numbers using separate mode in {}ms", count, TOP, end - start);

Our condition inside the loop can be replaced, as described above. Doing so actually does affect the runtime:

  • Separate conditions – 40ms
  • Multiple and single condition – 22ms

So the option that uses two different conditions actually takes twice as long to execute.

6. Conclusion

Abbiamo visto cos'è la previsione dei rami e come può avere un impatto sui nostri programmi. Questo può darci alcuni strumenti aggiuntivi nella nostra cintura per garantire che i nostri programmi siano il più efficienti possibile.

Tuttavia, come sempre, dobbiamo ricordarci di profilare il nostro codice prima di apportare modifiche importanti . A volte può accadere che apportare modifiche per aiutare la previsione dei rami costi di più in altri modi.

Esempi dei casi di questo articolo sono disponibili su GitHub.