Ottimizzare C++/Ottimizzazione del codice C++/Operazioni veloci

Alcune operazioni elementari, per quanto concettualmente altrettanto semplici di altre, sono molto più veloci per il processore. Un abile programmatore sa scegliere le istruzioni più veloci per eseguire un dato compito.

Tuttavia, ogni buon compilatore ottimizzante è già in grado di scegliere le istruzioni più veloci per il processore target, per cui alcune tecniche sono inutili su alcuni compilatori.

Inoltre, alcune tecniche possono persino peggiorare le prestazioni su alcuni processori.

In questa sezione vengono presentate alcune tecniche che possono offrire vantaggi prestazionali su alcune combinazioni di compilatore/processore.

Ordinamento dei campi di strutture

Disponi le variabili membro di classi e strutture in modo che le variabili più usate siano nei primi 128 byte, e poi in ordine dall'oggetto più lungo a quello più corto.

Se nella seguente struttura il membro msg viene usato solamente per messaggi d'errore, mentre gli altri membri sono usati per effettuare calcoli:

struct {
    char msg[400];
    double d;
    int i;
};

si possono velocizzare i calcoli trasformando tale struttura nella seguente:

struct {
    double d;
    int i;
    char msg[400];
};

Su alcuni processori, l'indirizzamento di un membro è più efficiente se la sua distanza dall'inizio della struttura non supera i 128 byte.

Nel primo esempio, per indirizzare i campi d e i usando un puntatore all'inizio della struttura, si è costretti a usare un offset di almeno 400 byte.

Invece, nel secondo esempio, contenente gli stessi campi in un altro ordine, gli offset per indirizzare i campi d e i sono di pochi byte, e ciò permette l'uso di istruzioni più compatte.

Adesso, supponiamo di aver scritto la seguente struttura:

struct {
    bool b;
    double d;
    short s;
    int i;
};

Tale struttura, a causa dei requisiti di allineamento dei campi, tipicamente occupa 1 (bool) + 7 (padding) + 8 (double) + 2 (short) + 2 (padding) + 4 (int) = 24 byte.

La seguente struttura è ottenuta dalla precedente ordinando i campi dal più lungo al più corto:

struct {
    double d;
    int i;
    short s;
    bool b;
};

Tale struttura tipicamente occupa 8 (double) + 4 (int) + 2 (short) + 1 (bool) + 1 (padding) = 16 byte. L'ordinamento ha minimizza gli spazi per l'allineamento (padding), e così genera una struttura più compatta.

Conversione da numero a virgola mobile a numero intero

Sfrutta routine non-standard per arrotondare a interi i numeri in virgola mobile.

Il linguaggio C++ non fornisce una primitiva per arrotondare numeri a virgola mobile. La tecnica più semplice per convertire un numero a virgola mobile x all'intero più vicino n, è la seguente istruzione:

n = int(floor(x + 0.5f));

Usando tale tecnica, se x è esattamente equidistante tra due interi, n sarà l'intero superiore (per esempio, 0.5 genera 1, 1.5 genera 2, -0.5 genera 0, e -1.5 genera -1).

Purtroppo, su alcuni processori (in particolare quelli della famiglia Pentium), tale espressione viene compilata in un codice macchina molto lento. Ma alcuni processori hanno istruzioni specifiche per arrotondare i numeri.

In particolare, la famiglia Pentium ha l'istruzione macchina fistp, che, usata nel seguente codice, risulta molto più veloce, sebbene non esattamente equivalente:

#if defined(__unix__) || defined(__GNUC__)
    // Per Linux a 32-bit, con sintassi Gnu/AT&T
    __asm ("fldl %1 \n fistpl %0 " : "=m"(n) : "m"(x) : "memory" );
#else
    // Per Windows a 32-bit, con sintassi Intel/MASM
    __asm fld qword ptr x;
    __asm fistp dword ptr n;
#endif

Il codice precedente arrotonda x all'intero più vicino, ma se x è esattamente equidistante tra due interi, n sarà l'intero pari più vicino (per esempio, 0.5 genera 0, 1.5 genera 2, -0.5 genera 0, e -1.5 genera -2).

Se questo risultato è tollerabile o addirittura desiderato, e ti è consentito usare il linguaggio assembly, allora questo codice è consigliabile. Ovviamente, non è portabile ad altre famiglie di processori.

Manipolazione dei bit di numeri interi

Manipola i bit dei numeri interi sfruttando la conoscenza del formato di rappresentazione.

Una raccolta di trucchi di questo tipo si trova qui. Alcuni di questi trucchi sono in realtà già utilizzati da alcuni compilatori, altri servono per risolvere problemi rari, altri sono utili solo su alcune piattaforme.

Manipolazione dei bit di numeri a virgola mobile

Manipola i bit dei numeri a virgola mobile, dopo averli reinterpretati come numeri interi, sfruttando la conoscenza del formato di rappresentazione.

Per le operazioni più comuni, i compilatori generano già codice ottimizzato, ma alcune operazioni meno comuni possono diventare leggermente più veloci se i bit sono manipolati usando operatori interi bit-a-bit.

Una di tali operazioni è la moltiplicazione o la divisione per una potenza di due. Per eseguire tali operazioni, basta aggiungere l'esponente di tale potenza all'esponente del numero a virgola mobile.

Per esempio, data una variabile f del tipo float conforme al formato IEEE 754, e data un'espressione intera positiva n, invece della seguente istruzione:

f *= pow(2, n);

si può usare il seguente codice:

if (*(int*)&f & 0x7FFFFFFF) { // se f==0 non fare niente
    *(int*)&f += n << 23; // aggiungi n all’esponente
}

Dimensione delle celle di array

Assicurati che la dimensione (ottenibile con l'operatore sizeof) delle celle non grandi degli array e dei vector sia una potenza di due, e che la dimensione delle celle grandi degli array e dei vector non sia una potenza di due.

L'accesso diretto alla cella di un array viene fatto moltiplicando l'indice per la dimensione di ogni cella, che è una costante. Se il secondo fattore di questa moltiplicazione è una potenza di due, tale operazione è molto più rapida, in quanto è implementata da uno scorrimento dei bit. Analogamente, negli array multidimensionali, tutte le dimensioni, eccetto al più la prima, dovrebbero essere potenze di due.

Questo dimensionamento si ottiene aggiungendo alle strutture dei campi inutilizzati e agli array delle celle inutilizzate. Per esempio, se ogni cella è una terna di oggetti float, basta aggiungere a ogni cella un quarto oggetto float dummy (cioè fantoccio).

Tuttavia, nell'accedere alle celle di un array multidimensionale in cui una dimensione diversa dalla prima è una potenza di 2 abbastanza grande, si può cadere nel fenomeno della contesa per la cache dei dati (in inglese data cache conflict o data cache contention), che può rallentare l'elaborazione fino a più di 10 volte. Questo fenomeno si verifica solo quando le celle dell'array superano una certa dimensione, che dipende dal sistema, ma che orientativamente è da 1 a 8 KB. Pertanto, nel caso in cui un algoritmo deve elaborare un array le cui celle hanno o potrebbero avere come dimensione una potenza di 2 maggiore o uguale a 1024 byte, in primo luogo si deve scoprire se si ha la contesa per la cache, e in caso affermativo evitare tale fenomeno.

Per esempio, una matrice di 100 x 512 float è un array di 100 array di 512 float. Ogni cella dell'array di primo livello è grande 512 x 4 = 2048 byte, e quindi è a rischio di contesa per la cache dei dati.

Per scoprire l'esistenza della contesa per la cache, basta aggiungere una cella array di ultimo livello, ma continuare a elaborare le stesse celle di prima, e misurare se il tempo di elaborazione si riduce sostanzialmente (di almeno il 20%). In caso affermativo, si deve fare in modo che tale riduzione ci sia sempre. A tale scopo, si può adottare una delle seguenti tecniche:

• Aggiungere una o alcune celle inutilizzate alla fine di ogni riga. Per esempio l'array double a[100][1024] potrebbe essere trasformato in double a[100][1026], anche se nel codice si terrà conto che la dimensione utile rimane 100x1024.
• Lasciare le dimensioni appropriate dell'array, ma suddividere le matrici in blocchi rettangolari, ed elaborare tutte le celle di ogni blocco prima di passare al blocco successivo.

Espansione inline esplicita

Se non usi le opzioni di ottimizzazione dell'intero programma e di espansione inline automatica, prova a spostare nelle intestazioni e a dichiarare inline le funzioni chiamate dai colli di bottiglia.

Come spiegato nella linea-guida "Funzioni espanse inline" della sezione 3.1, le singole funzioni espanse inline sono più veloci, ma un eccesso di funzioni espanse inline rallenta complessivamente il programma.

Prova a dichiarare inline un paio di funzioni per volta, fin tanto che si ottengono miglioramenti significativi della velocità (almeno del 10%) per un dato comando.

Operazioni con potenze di due

Se devi scegliere una costante intera per cui devi moltiplicare o dividere spesso, scegli una potenza di due.

Le operazioni di moltiplicazione, divisione e modulo tra numeri interi sono molto più veloci se il secondo operando è una potenza di due costante, in quanto in tal caso vengono implementate come scorrimenti di bit o mascherature di bit.

Divisione intera per costanti

Se un numero intero signed è sicuramente non-negativo, quando lo dividi per una costante, convertilo in unsigned.

Se s è un intero signed, u è un intero unsigned, e c è un'espressione costante intera (positiva o negativa), l'operazione s / c è più lenta di u / c e l'operazione s % c è più lenta di u % c, soprattutto quando c è una potenza di due, ma anche quando non lo è, in quanto nei primi due casi si deve tenere conto del segno.

D'altra parte, la conversione da signed a unsigned non costa niente, in quanto si tratta solo di una reinterpretazione degli stessi bit. Pertanto, se s è un intero con segno, che sai essere sicuramente positivo o nullo, ne velocizzi la divisione se usi le seguenti espressioni equivalenti: unsigned(s) / c e unsigned(s) % c.

Processori con bus dati ridotto

Se il processore target ha il bus dati più piccolo dei registri interni, se possibile, usa tipi interi non più grandi del bus dati per tutte le variabili eccetto i parametri di funzione e le variabili locali più utilizzate.

I tipi int e unsigned int sono quelli più efficienti, una volta caricati nei registri del processore. Tuttavia, su alcune famiglie di processori, potrebbero non essere i più efficienti da accedere in memoria.

Per esempio, esistono processori che hanno registri da 16 bit, ma bus dati da 8 bit, e altri processori che hanno registri da 32 bit, ma bus dati da 16 bit. Per i processori che hanno il bus dati più piccolo dei registri interni, solitamente i tipi int e unsigned int corrispondono alla dimensione dei registri interni.

Per tali sistemi, la lettura e la scrittura in memoria di un oggetto di tipo int richiedono un tempo maggiore di quello che sarebbe richiesto da un tipo intero non più grande del bus dati.

I parametri di funzione e le variabili locali più utilizzate sono solitamente allocate in registri, e quindi non richiedono accessi in memoria.