Ottimizzare C++/Scrivere codice C++ efficiente/Costrutti che migliorano le prestazioni

Alcuni costrutti del linguaggio C++, se usati opportunamente, permettono di aumentare la velocità del software risultante.

In questa sezione si presentano le linee-guida per approfittare di tali costrutti.

I tipi più efficienti

Quando definisci un oggetto per memorizzare un numero intero, usa il tipo int o il tipo unsigned int, a meno che sia necessario un tipo più lungo; quando definisci un oggetto per memorizzare un carattere, usa il tipo char, a meno che serva il tipo wchar_t; e quando definisci un oggetto per memorizzare un numero a virgola mobile, usa il tipo double, a meno che sia necessario il tipo long double. Se l'oggetto composto risultante è medio o grande, sostituisci tutti i tipi interi con il tipo intero più piccolo in grado di contenerlo, ma senza usare i bit-field, e sostituisci tutti i tipi a virgola mobile con il tipo float, a meno che sia necessaria maggiore precisione.

I tipi int e unsigned int sono per definizione quelli più efficienti su qualunque piattaforma.

Generalmente, il tipo double è efficiente quanto il tipo float, ma è più preciso. Su alcune piattaforme, soprattutto le cosiddette piattaforme embedded, ma non solo, il tipo double è notevolmente meno efficiente di float: in tali casi float è sempre da preferire.

Alcuni tipi di processore elaborano più velocemente gli oggetti di tipo signed char, mentre altri elaborano più velocemente gli oggetti di tipo unsigned char. Pertanto, sia in C che in C++ è stato introdotto il tipo char, diverso dal tipo signed char, che corrisponde al tipo di carattere elaborato più velocemente dal processore target.

Il tipo char può contenere solo piccoli insiemi di caratteri; tipicamente fino a un massimo di 255 caratteri distinti. Per memorizzare set di caratteri più grandi, si deve ricorrere al tipo wchar_t, che ovviamente è meno efficiente.

Nel caso di numeri contenuti in un oggetto composto di media o grande dimensione, o in una collezione che si presume sarà di media o grande dimensione, è meglio minimizzare la dimensione in byte dell'oggetto composto o della collezione. Questo si può fare sostituendo gli int con short o con signed char, sostituendo gli unsigned int con unsigned short o con unsigned char, e sostituendo i double con float. Per esempio, per memorizzare un numero intero che può essere compreso tra 0 e 1000, si può usare un unsigned short, mentre per memorizzare un numero intero che può essere compreso tra -100 e 100, si può usare un signed char.

I bit-field contribuirebbero a minimizzare la dimensione in byte dell'oggetto o della collezione, ma la loro elaborazione introduce un rallentamento che potrebbe essere eccessivo; pertanto, posponi la loro introduzione alla fase di ottimizzazione.

Gli oggetti-funzione

Invece di passare come argomento di funzione un puntatore a funzione, passa un oggetto-funzione, o, se stai usando lo standard C++0x, un'espressione lambda.

Per esempio, se hai il seguente array di strutture:

struct S {
    int a, b;
};
S arr[n_voci];

e vuoi ordinarlo in base al campo b, potresti definire la seguente funzione di confronto:

bool confronta(const S& s1, const S& s2) {
    return s1.b < s2.b;
}

e passarla all'algoritmo std::sort:

std::sort(arr, arr + n_voci, confronta);

Ma probabilmente è più efficiente definire la seguente classe di oggetto-funzione (nota anche come funtore):

struct Comparatore {
    bool operator()(const S& s1, const S& s2) const {
        return s1.b < s2.b;
    }
};

e passarne un'istanza temporanea all'algoritmo std::sort:

std::sort(arr, arr + n_voci, Comparatore());

Le funzioni degli oggetti-funzione di solito sono espansi inline, e perciò sono altrettanto efficienti quanto il codice scritto sul posto, mentre le funzioni passate per puntatore vengono raramente espanse inline.

Le espressioni lambda sono implementate come oggetti-funzione, e quindi hanno le loro stesse prestazioni.

Funzioni qsort e bsearch

Invece delle funzioni della libreria standard del C qsort e bsearch, usa le funzioni della libreria standard del C++ std:sort e std:lower_bound.

Le prime due funzioni richiedono necessariamente un puntatore a funzione, mentre le seconde due possono usare un oggetto-funzione (o, usando C++0x, un'espressione lambda). I puntatori a funzione spesso non sono espansi inline e sono quindi meno efficienti degli oggetti-funzione, che sono quasi sempre espansi inline.

Collezioni incapsulate

Incapsula in apposite classi le collezioni accessibili da più unità di compilazione, in modo da garantire l'intercambiabilità di implementazione.

In fase di progettazione, è difficile decidere quale struttura dati avrà prestazioni ottimali nell'uso effettivo dell'applicazione. In fase di ottimizzazione, si può misurare se cambiando il tipo di un contenitore, per esempio passando da std::vector a std::list, si ottengono prestazioni migliori. Tuttavia, tale cambio di implementazione comporta la modifica di gran parte del codice sorgente che utilizza direttamente il contenitore che ha cambiato di tipo.

Se una collezione è privata a una sola unità di compilazione, tale modifica avrà impatto solamente sul codice sorgente contenuto in questa unità, e quindi non è necessario incapsulare tale collezione. Se invece quella collezione non è privata, cioè è accessibile direttamente da altre unità di compilazione, in futuro ci potrà essere una quantità enorme di codice che dovrà essere modificata a fronte di tale cambio di tipo. Quindi, per rendere fattibile in tempi ragionevoli tale ottimizzazione, si deve incapsulare la collezione in una classe la cui interfaccia non cambia al cambiare dell'implementazione del contenitore.

I contenitori STL perseguono già questo principio, ma alcune operazioni sono disponibili solo per alcuni contenitori (come l'operator[], che esiste per std::vector ma non per std::list).

Uso dei contenitori STL

Nell'uso dei contenitori STL, se più espressioni equivalenti hanno le stesse prestazioni, scegli l'espressione più generale.

Per esempio, chiama a.empty() invece di a.size() == 0, chiama iter != a.end() invece di iter < a.end(), e chiama distance(iter1, iter2) invece di iter2 - iter1. Le prime espressioni sono valide per ogni tipo di contenitore, mentre le seconde solamente per alcuni tipi, e le prime non sono meno efficienti delle seconde.

Purtroppo, non è sempre possibile scrivere del codice egualmente valido ed efficiente per ogni tipo di contenitore. Tuttavia, riducendo il numero di istruzioni dipendenti dal tipo di contenitore, si riduce anche il numero di istruzioni da modificare qualora, in fase di ottimizzazione, il tipo del contenitore venisse cambiato.

Scelta del contenitore di default

Nella scelta di un contenitore a lunghezza variabile, in caso di dubbio, scegli un vector.

Fino a 8 elementi, il vector è il contenitore a lunghezza variabile più efficiente per qualunque operazione.

Per insiemi più grandi, altri contenitori possono diventare sempre più efficienti per alcune operazioni, ma il vector rimane quello che ha minore occupazione di memoria (purché non ci sia capacità in eccesso), e maggiore località di riferimento dei dati.

Funzioni espanse inline

Se usi compilatori che consentono l'ottimizzazione dell'intero programma e l'espansione inline automatica delle funzioni, usa tali opzioni, e non dichiarare inline nessuna funzione. Se tali funzionalità del compilatore non fossero disponibili, dichiara inline nei file di intestazione solo le funzioni che contengono non più di tre righe di codice, tra le quali non ci siano cicli.

Le funzioni espanse inline non hanno il costo della chiamata di funzione, che è tanto più grande quanti più sono gli argomenti della funzione. Inoltre, dato che il codice è vicino a quello del chiamante, hanno migliore località di riferimento del codice. Infine, dato che il codice intermedio delle funzioni espanse inline si fonde con quello del chiamante, tale codice può essere facilmente ottimizzato dal compilatore.

Espandere inline una funzione estremamente piccola, cioè un semplice assegnamento o una semplice istruzione return, comporta addirittura una riduzione del codice macchina generato.

Tuttavia, ogni volta che una routine che contiene una quantità notevole di codice viene espansa inline, il suo codice macchina viene duplicato, e quindi la dimensione complessiva del programma aumenta, peggiorando la località di riferimento del codice.

Inoltre, il codice espanso inline è più difficile da analizzare con un profiler. Se una funzione non espansa inline è un collo di bottiglia, viene individuata dal profiler. Ma se quella funzione viene espansa inline in tutti i punti in cui è chiamata, il suo tempo di esecuzione viene sparpagliato fra tutte le funzioni che la chiamano.

In fase di ottimizzazione, tra le funzioni non piccolissime, solo quelle critiche per la velocità dovranno essere dichiarate inline.

Rappresentazione di simboli

Per rappresentare dei simboli interni, usa degli enumerati, invece di stringhe.

Per esempio, invece del seguente codice:

const char* direzioni[] = { "Nord", "Sud", "Est", "Ovest" };

scrivi il seguente codice:

enum direzioni { Nord, Sud, Est, Ovest };

Un enumerato è implementato come un intero. Tipicamente, rispetto ad un intero, una stringa occupa più spazio, ed è più lenta da copiare e da confrontare.

Istruzioni if e switch

Se devi confrontare un valore intero con una serie di valori costanti, invece di una serie di istruzioni if, usa un'istruzione switch.

Per esempio, invece del seguente codice:

if (a[i] == 1) f();
else if (a[i] == 2) g();
else if (a[i] == 5) h();

scrivi il seguente codice:

switch (a[i]) {
case 1: f(); break;
case 2: g(); break;
case 5: h(); break;
}

I compilatori possono sfruttare la regolarità delle istruzioni switch per applicare alcune ottimizzazioni, in particolare se viene applicata la linea-guida "Valori dei casi di istruzioni switch" di questa sezione.

Valori dei casi di istruzioni switch

Come costanti per i casi delle istruzioni switch, usa sequenze compatte di valori, cioè senza lacune o con poche piccole lacune.

I compilatori ottimizzanti, quando compilano un'istruzione switch i cui valori dei casi costituiscono la maggior parte dei valori interi compresi in un intervallo, invece di generare una sequenza di istruzioni if, generano una jump-table, ossia un array degli indirizzi a cui inizia il codice di ogni caso, e per eseguire l'istruzione switch, usano tale tabella per saltare al codice associato al numero del caso.

Per esempio, il seguente codice C++:

switch (i) {
case 10:
case 13:
    funz_a();
    break;
case 11:
    funz_b();
    break;
}

probabilmente genera del codice macchina corrispondente al seguente pseudo-codice:

// N.B.: Questo non è codice C++
static indirizzo a[] = { caso_a, caso_b, fine, caso_a };
unsigned int indice = i - 10;
if (indice > 3) goto fine;
goto a[indice];
caso_a: funz_a(); goto fine;
caso_b: funz_b();
fine:

Invece, il seguente codice C++:

switch (i) {
case 100:
case 130:
    funz_a();
    break;
case 110:
    funz_b();
    break;
}

probabilmente genera del codice macchina corrispondente al seguente codice:

if (i == 100) goto caso_a;
if (i == 130) goto caso_a;
if (i == 110) goto caso_b;
goto fine;
caso_a: funz_a(); goto fine;
caso_b: funz_b();
fine:

Per così pochi casi, probabilmente non ci sono molte differenze tra le due situazioni, ma con l'aumentare del numero di casi, il primo codice diventa più efficiente, in quanto esegue un solo goto calcolato invece di una serie di if.

Ordine dei casi dell'istruzione switch

Nelle istruzioni switch, poni prima i casi più tipici.

Se il compilatore non generasse la jump-table, i casi verrebbero confrontati in ordine di comparizione; pertanto, nei casi più tipici verrebbero fatti meno confronti.

Raggruppamento di più array in un solo array di strutture

Invece di elaborare in parallelo due o più array della stessa lunghezza, elabora un solo array di oggetti composti.

Esempio: Invece del seguente codice:

const int n = 10000;
double a[n], b[n], c[n];
for (int i = 0; i < n; ++i) {
    a[i] = b[i] + c[i];
}

scrivi il seguente codice:

const int n = 10000;
struct { double a, b, c; } s[n];
for (int i = 0; i < n; ++i) {
    s[i].a = s[i].b + s[i].c;
}

In tal modo, i dati da elaborare insieme sono più vicini tra di loro in memoria, e questo permette di ottimizzare l'uso della cache dei dati, e di indirizzare tali dati con istruzioni più compatte, che quindi ottimizzano anche l'uso della cache del codice.

Raggruppamento di argomenti di funzione

Se una funzione riceve almeno sei argomenti, e viene chiamata in un ciclo con gli stessi valori tranne al più due, prima del ciclo crea una struttura che contiene tutti gli argomenti, e passa alla funzione tale struttura.

Per esempio, invece del seguente codice:

for (int i = 0; i < 1000; ++i) {
    f(i, a1, a2, a3, a4, a5, a6, a7, a8);
}

scrivi il seguente codice:

struct {
    int i;
    tipo a1, a2, a3, a4, a5, a6, a7, a8;
} s;
s.a1 = a1; s.a2 = a2; s.a3 = a3; s.a4 = a4;
s.a5 = a5; s.a6 = a6; s.a7 = a7; s.a8 = a8;
for (int i = 0; i < 1000; ++i) {
    s.i = i;
    f(s);
}

Se una funzione riceve pochi argomenti, questi vengono posti direttamente nei registri, e quindi il loro passaggio è molto veloce; ma se gli argomenti non sono pochi, devono essere posti nello stack ad ogni chiamata, anche se non sono cambiati dall'iterazione precedente.

Se invece si passa alla funzione solo l'indirizzo di una struttura, questo indirizzo viene probabilmente posto in un registro, e, dopo l'inizializzazione della struttura, solamente i campi della struttura che sono modificati tra chiamate successive devono essere assegnati.

Uso di funzioni membro di contenitori

Per cercare un elemento in un contenitore, usa una funzione membro del contenitore, invece di un algoritmo STL.

Se è stata creata una tale funzione membro specifica, quando esisteva già un algoritmo STL generico, è solo perché tale funzione membro è più efficiente.

Per esempio, per cercare in un oggetto std::set, si può usare l'algoritmo generico std::find, o la funzione membro std::set::find; ma il primo ha complessità lineare (O(n)), mentre la seconda ha complessità logaritmica (O(log(n))).

Ricerca in sequenze ordinate

Per cercare un elemento in una sequenza ordinata, usa gli algoritmi lower_bound, upper_bound, equal_range, o binary_search.

Tutti i citati algoritmi, dato che usano la ricerca binaria, avente complessità logaritmica (O(log(n))), sono più veloci dell'algoritmo std::find, che usa la ricerca sequenziale, avente complessità lineare (O(n)).