Ottimizzare C++/Ottimizzazione del codice C++/Pipeline

Le istruzioni in linguaggio macchina di salto condizionato (chiamate anche branch), possono essere generate dalla compilazione di vari costrutti C++, tra cui le istruzioni if-else, for, while, do-while, switch-case, e dagli operatori booleani e dall'operatore di espressione condizionale (?:).

I moderni processori elaborano efficientemente i salti condizionati solo se riescono a prevederli. In caso di errore di previsione, il lavoro che hanno già incominciato a fare, caricando nella pipeline le istruzioni successive, risulta inutile e devono ripartire dall'istruzione di destinazione del salto.

La predizione del salto si basa sulle iterazioni precedenti. Se queste sono regolari, il salto viene predetto correttamente.

I casi migliori sono quelli in cui un'istruzione di salto ha sempre lo stesso effetto; in tali casi, la predizione è quasi sempre corretta. Il caso peggiore è quello in cui l'istruzione di salto ha un esito casuale, con una probabilità del 50% di eseguire il salto; in tale caso, la predizione è corretta mediamente solo la metà delle volte, ma non è impossibile che sia sempre sbagliata.

Nei colli di bottiglia, si dovrebbero evitare le istruzioni di salto difficilmente prevedibili. Se un salto è predetto molto male, anche sostituendolo con una serie di istruzioni piuttosto lenta si può ottenere un incremento di velocità.

In questa sezione, vengono presentate alcune tecniche per sostituire le istruzioni di salto con istruzioni equivalenti.

Verifica di intervallo

Se devi verificare se un numero intero i è compreso tra i due numeri interi min_i e max_i, estremi inclusi, e sei sicuro che min_i <= max_i, usa la seguente espressione:

unsigned(i – min_i) <= unsigned(max_i – min_i)

Nelle condizioni date, la suddetta formula è equivalente alla seguente formula, più intuitiva:

min_i <= i && i <= max_i

La prima formula esegue due differenze e un confronto, mentre la seconda esegue due confronti e nessuna differenza. Per i processori con pipeline, i confronti sono più lenti delle differenze, perché comportano dei salti condizionati.

Inoltre, se min_i è un'espressione costante di valore zero, le due differenze non sono più necessarie.

In particolare, per verificare se un numero i è valido come indice per accedere a un array di size elementi, la formula si riduce alla seguente:

unsigned(i) < unsigned(size)

Ovviamente, se le espressioni utilizzate sono già di un tipo unsigned, le conversioni non sono necessarie.

La look-up table binaria.

Invece di un'espressione condizionale con entrambi i casi costanti, usa una look-up table a due valori.

Ossia, se hai del codice come il seguente, in cui c e d rappresentano espressioni costanti e b rappresenta un'espressione booleana:

a = b ? c : d;

che è equivalente al seguente codice:

if (b) a = c;
else a = d;

prova a sostituirla con il seguente codice, equivalente ma forse più veloce:

static const tipo lookup_table[] = { d, c };
a = lookup_table[b];

L'espressione condizionale viene compilata in un salto condizionato. Se tale salto non è predetto bene, costa di più della lookup-table.

Ovviamente questa tecnica può essere estesa a cascate di espressioni condizionali. Per esempio, invece del seguente codice:

a = b1 ? c : b2 ? d : b3 ? e : f;

che è equivalente al seguente codice:

if (b1) a = c;
else if (b2) a = d;
else if (b3) a = e;
else a = f;

puoi provare a vedere se il seguente codice equivalente è più veloce:

static const tipo lookup_table[] = { f, e, d, d, c, c, c, c };
a = lookup_table[b1 * 4 + b2 * 2 + b3];

Anticipazione del calcolo degli indirizzi

Cerca di calcolare il valore di un puntatore o iteratore un po' prima di quando devi accedere all'oggetto referenziato.

Per esempio, in un ciclo, la seguente istruzione:

a = *++p;

può essere un po' meno efficiente della seguente:

a = *p++;

Nel primo caso il valore del puntatore o iteratore è calcolato appena prima di accedere all'oggetto referenziato, mentre nel secondo caso è calcolato nell'iterazione precedente. In un processore con pipeline, nel secondo caso, l'incremento dell'iteratore o puntatore può essere eseguito contemporaneamente all'accesso all'oggetto referenziato, mentre nel primo caso le due operazioni devono essere serializzate.