Community
 
Aggiungi lista preferiti Aggiungi lista nera Invia ad un amico
------------------
Crea
Profilo
Blog
Video
Sito
Foto
Amici
   
 
 

C++ ottimizzato

1. Introduzione

Il principale motivo per cui si sceglie si sviluppare del software in C++, invece che in linguaggi di più alto livello, è il fatto che questo linguaggio consente di produrre software più efficiente di quello prodotto con altri linguaggi. Si noti che il linguaggio non garantisce automaticamente di produrre software efficiente, ma lo consente soltanto. Infatti, scrivendo di getto lo stesso programma in C++ e in linguaggi di più alto livello, tipicamente la versione sviluppata in C++ è altrettanto efficiente quanto quella sviluppata negli altri linguaggi.

Tuttavia, un buon programmatore C++, seguendo delle linee-guida apprese da altri o dalla propria esperienza, è in grado in primo luogo di scrivere del software discretamente efficiente fin dalla prima stesura, e poi di ottimizzare il programma risultante, cioè incrementare sensibilmente le prestazioni complessive del programma sostituendo alcuni costrutti con altri sostanzialmente equivalenti ma più efficienti. Tale ottimizzazione richiede in primo luogo che il software sia stato scritto in modo sufficientemente modulare da isolare le parti più critiche per le prestazioni, e poi di impiegare strumenti, librerie, conoscenze, e tempo, per applicare le modifiche necessarie ad ottimizzare le prestazioni del software prodotto.

Oggigiorno, molte delle sostituzioni che ottimizano il programma sono già effettuate dai compilatori, e quindi non sono più compito del programmatore. Tuttavia, molte altre ottimizzazioni non sono ancora ottenibili dagli attuali compilatori.

Questo testo è rivolto a programmatori esperti, che conoscano già il linguaggio C++, e che lo vogliano usare per sviluppare software applicativo o librerie. Le tecniche di ottimizzazione qui trattate sono tutte indipendenti dalla piattaforma, e pertanto non si farà quasi mai riferimento né a particolari sistemi operativi, né a particolari architetture di processore, né a particolari compilatori. Tuttavia, alcune delle tecniche proposte risultano non convenienti o persino inapplicabili in alcune combinazioni di sistema operativo/processore/compilatore.

Si assumerà l’utilizzo di un buon compilatore ottimizzante, e pertanto non verranno nemmeno presentate vecchie tecniche di ottimizzazione rese inutili dall’uso di un tale compilatore.

2. Ciclo di vita dell’ottimizzazione

Lo sviluppo di un’applicazione efficiente procede nel seguente modo:

  1. Progettazione (design). Dapprima si progettano gli algoritmi e le strutture dati in modo che abbiano senso per la logica applicativa, e che siano ragionevolmente efficienti, ma senza occuparsi di ottimizzarle. Dove si deve definire una struttura dati di ampio utilizzo e per la quale non è ovvio quale sia l’implementazione ottimale (per esempio, non si sa scegliere tra un array e una lista collegata), si definisce una struttura astratta, di cui si possa cambiare l’implementazione in fase di ottimizzazione.
  2. Codifica (coding). Poi si scrive il codice che implementa gli algoritmi progettati, seguendo linee-guida che permettano in linea di massima di evitare operazioni banalmente inefficienti e di incapsulare le operazioni che richiederanno ottimizzazioni.
  3. Collaudo funzionale (functional testing). Poi si collaudo il software prodotto, in modo da aumentare la probabilità che non abbia difetti rilevanti.
  4. Ottimizzazione (tuning). Dopo aver completato lo sviluppo di un’applicazione funzionante correttamente, si passa alla fase di ottimizzazione, costituita dalle seguenti sotto-fasi:
    1. Collaudo prestazionale (performance testing). Si valuta quali comandi hanno prestazioni inadeguate, cioè quali comandi, elaborando dei dati tipici, richiedono più memoria o più tempo di quelli massimi specificati nei requisiti.
    2. Profiling . Per ogni comando avente prestazioni inadeguate, si determina, usando un profiler, quali porzioni di codice costituiscono i cosiddetti “colli di bottiglia” per tale comando, che sono le porzioni di codice nelle quali, tra l’inizio del comando e il suo completamento, viene trascorso più tempo e viene allocata più memoria.
    3. Ottimizzazione algoritmica. Nei colli di bottiglia, si applicano tecniche di ottimizzazione sostanzialmente indipendenti dal linguaggio di programmazione, e totalmente indipendenti dalla piattaforma. Sono le tecniche che si trovano nei testi di teoria degli algoritmi. In pratica, si cerca di ridurre il numero di istruzioni eseguite, e in particolare il numero delle chiamate a routine costose, o a trasformare le chiamate costose in chiamate equivalenti ma meno costose. Per esempio, si sceglie di implementare l’algoritmo di ordinamento quicksort invece dell’algoritmo selectionsort . Se questa ottimizzazione rende il programma sufficientemente veloce, si termina l’ottimizzazione.
    4. Ottimizzazione indipendente dalla piattaforma . Nei colli di bottiglia, si adottano tecniche di ottimizzazione dipendenti dal linguaggio di programmazione e dalla sua libreria standard, ma indipendenti sia dalla piattaforma software che dalla piattaforma hardware. Per esempio, si usano operazioni intere invece di operazioni a virgola mobile, o si sceglie il tipo di contenitore più appropriato tra quelli disponibili nella libreria standard. Se questo rende il programma sufficientemente veloce, si termina l’ottimizzazione.
    5. Ottimizzazione dipendente dalla piattaforma software . Nei colli di bottiglia, si adottano tecniche di ottimizzazione dipendenti sia dal linguaggio di programmazione che dalla piattaforma software, ma indipendenti dalla piattaforma hardware. Per esempio sfruttando opzioni di compilazione, direttive pragma di compilazione, estensioni al linguaggio offerte da un particolare compilatore, chiamate a librerie non-standard, chiamate dirette al sistema operativo. Se questo rende il programma sufficientemente veloce, si termina l’ottimizzazione.
    6. Ottimizzazione dipendente dalla piattaforma hardware. Nei colli di bottiglia si adottano tecniche di ottimizzazione dipendenti dalla piattaforma hardware, cioè o istruzioni che esistono solo su una particolare famiglia di processori, come le istruzioni in assembly, o istruzioni ad alto livello che, pur essendo eseguibili su qualunque processore, risultano vantaggiose solo su alcuni tipi di processore.

Questo procedimento segue due criteri:

Nei rari casi di software che dovrà funzionare con più compilatori e su più sistemi operativi ma su un solo tipo di processore, le fasi 4.5 e 4.6 dovrebbero essere invertite.

Questa sequenza di fasi non va affatto interpretata come una sequenza a senso unico, cioè tale per cui una volta raggiunta una fase non si torna più alla fase precedente. In realtà ogni fase può avere successo o fallire. Se ha successo, si passa alla fase successiva, se fallisce si passa alla fase precedente.

Inoltre, un collaudo parziale delle prestazioni deve essere eseguito dopo ogni tentativo di ottimizzazione, per verificare se il tentativo risulta utile, e, in caso affermativo, per verificare se risulta risolutivo, cioè se sono necessarie altre ottimizzazioni.

Infine, per garantire che la nuova versione ottimizzata del software non sia peggiorata né per la correttezza né per le prestazioni complessive, dopo aver completato l’ottimizzazione si devono ripetere sia il collaudo funzionale che il collaudo prestazionale completo.

Questo testo approfondisce solo tre dei punti citati: alcune tecniche generali relative al punto 4.3 (nella sezione “Tecniche generali di ottimizzazione”) e, limitatamente all’uso del linguaggio C++, il punto 2 (nella sezione “Linee-guida per scrivere codice C++ efficiente e ottimizzabile”) e il punto 4.4 (nella sezione “Tecniche di ottimizzazione specifiche del linguaggio C++, ma indipendenti dalla piattaforma”).

Notazioni terminologiche

Per oggetto si intende una sequenza contigua di dati in memoria. In particolare, sia un dato associato a una variabile di un tipo fondamentale (come booldouble, o unsigned long) che i dati associati a un'istanza di una classe sono oggetti. A ogni variabile è associato un oggetto, ma un oggetto potrebbe non avere una variabile associata; per esempio un puntatore può puntare a un oggetto senza nome.

Si dice che un oggetto possiede un altro oggetto se la deallocazione del primo oggetto comporta la deallocazione del secondo. Per esempio, un oggetto vector non vuoto tipicamente contiene un puntatore a un oggetto array contenente gli elementi; la distruzione del vector comporta la distruzione dell'array, e quindi diciamo che tale array è posseduto dal vector.

Alcune ottimizzazioni risultano applicabili solo per brevi sequenze di dati, altre per sequenze più lunghe. In seguito, si userà la seguente classificazione per la dimensioni degli oggetti:

Per esempio, un array di double è considerato “piccolissimo” solo se contiene esattamente un elemento, "piccolo” se ha da 2 a 8 elementi, “medio” se ne ha da 9 a 512, “grande” se ne ha più di 512.

Dato che ci sono architetture hardware molto variabili, i numeri suddetti sono solo indicativi. Tuttavia, tali numeri sono abbastana realistici, e possono essere considerati seriamente come criteri per sviluppare del software che copra le principali architetture in modo piuttosto efficiente.

3. Linee-guida per scrivere codice C++ efficiente e ottimizzabile

In questa sezione vengono proposte linee-guida per la programmazione in C++ finalizzate a evitare operazioni banalmente inefficienti, senza con questo rendere il codice meno manutenibile.

Tali linee-guida potrebbero non dare alcun vantaggio prestazionale, ma molto probabilmente non danno neanche svantaggi, e quindi le si può applicare senza preoccuparsi del loro impatto. Si consiglia di abituarsi ad adottare sempre tali linee-guida, fin dalla prima stesura, anche nel codice che non ha particolari requisiti di efficienza.

3.1. Come approfittare dei costrutti C++ che migliorano le prestazioni

3.1.1. Non verificare che un puntatore sia non-nullo prima di chiamare delete su di esso.

Tale controllo viene già fatto da ogni implementazione di delete conforme allo standard, e quindi sarebbe ridondante.

3.1.2. Invece delle funzioni di libreria qsort e bsearch, usa le funzioni std::sort e std:lower_bound.

Le prime due funzioni richiedono un puntatore a funzione, mentre le seconde richiedono un oggetto-funzione (o un'espressione lambda). I puntatori a funzione spesso non sono espansi inline e sono quindi meno efficienti.

3.1.3. Dichiara const ogni funzione membro che non modifica lo stato dell’oggetto.

Questa indicazione equivale a specificare l'argomento implicito this come puntatore a const. Per l'uso di const negli argomenti di funzione, vedi la linea-guida 3.3.5.

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

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

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

I compilatori possono sfruttare la regolarità di tale istruzione per applicare alcune ottimizzazioni, in particolare se viene applicata la linea-guida 3.1.11.

3.1.6. Incapsula le collezioni in astrazioni di livello più alto, in modo da garantire l’intercambiabilità di implementazione.

In fase di ottimizzazione sarà così possibile scegliere l’implementazione più efficiente per la struttura dati, senza dover modificare molto codice.

I contenitori STL attuano già parzialmente questo principio, ma alcune operazioni sono disponibili solo per alcuni contenitori.

3.1.7. Nell'uso dei contenitori STL, a parità di prestazioni, fa' in modo di rendere intercambiabile il contenitore.

Per esempio, chiama a.empty() invece di a.size() == 0, chiama iter != a.end() invece di iter < a.end().

Purtroppo, non è sempre possibile scrivere del codice egualmente efficiente e valido per ogni tipo di contenitore. Tuttavia, riducendo il numero di istruzioni dipendenti dal tipo di contenitore, se in fase di ottimizzazione si dovesse sostituire il contenitore con un'altro, si dovrà modificare meno codice.

3.1.8. Invece di scrivere un ciclo for su un contenitore STL, usa un algoritmo di STL con un'espressione lambda (usando Boost o C++0x).

Gli algoritmi di STL sono già dei cicli ottimizzati per gli specifici contenitori, ed evitano il rischio di introdurre operazioni inefficienti.

Le espressioni lambda sono implementate come oggetti-funzione espansi inline, e quindi sono altrettanto efficienti quanto il codice scritto sul posto.

Senza avere a disposizione la funzionalità lambda, nella maggior parte dei casi è troppo scomodo usare gli algoritmi STL perché ne valga la pena; invece, usando le espressioni lambda, si possono scrivere corpi arbitrari per tali cicli.

3.1.9. Se devi scegliere un contenitore a lunghezza variabile, e sei incerto su quale contenitore scegliere, usa un vector.

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

Per insiemi più grandi, altri contenitori possono diventare gradualmente più efficienti a seconda delle operazioni, ma il vector rimane quello che ha minore occupazione di memoria (purché non ci sia capacità in eccesso), minor tempo di scansione completa, e maggiore località di riferimento.

3.1.10. Se usi compilatori che consentono l’ottimizzazione dell’intero programma e l’espansione inline di qualunque funzione che il compilatore ritenga opportuno, usa tali opzioni e non dichiarare inline nessuna funzione. Se questi requisiti non fossero soddisfatti, dichiara inline nei file di intestazione solo le funzioni che contengono non più di tre righe di codice, nelle quali non ci sono cicli.

Le funzioni 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 è consecutivo con quello del chiamante, hanno migliore località di riferimento. Infine, dato che il codice intermedio delle funzioni espanse inline si fonde con quello del chiamante, tale codice può essere facilmente ottimizzato dal compilatore.

Le funzioni molto piccole, cioè un semplice assegnamento o una semplice istruzione return, quando espanse inline comportano addirittura una riduzione del codice complessivo.

Tuttavia, ogni volta che viene espansa inline una routine che contiene una quantità notevole di codice, si duplica tale codice, e quindi si ingrandisce la dimensione complessiva del programma, con conseguente rallentamento a causa della minore località di riferimento.

Tra le routine non piccolissime, solo quelle critiche per la velocità verranno rese inline in fase di ottimizzazione.

3.1.11. Come costanti per le istruzioni switch, usa sequenze compatte di valori, cioè senza lacune o con poche lacune.

I compilatori ottimizzanti, quando compilano un’istruzione switch i cui valori dei casi comprendono 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 in cui inizia il codice di ogni caso, e quando eseguono lo switch usano tale tabella per saltare al codice associato al caso.

Per esempio, il seguente codice:

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

probabilmente genera il seguente pseudo-codice:

static indirizzo a[] = { caso_a, caso_b, 0, caso_a };
unsigned int indice = i - 10;
if (indice <= 3) goto a[indice];
goto fine:
caso_a: funz_a(); goto fine;
caso_b: funz_b(); goto fine;
fine:

ed è più efficiente del seguente:

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

che probabilmente genera il seguente pseudo-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(); goto fine;
fine:

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

Se il compilatore non genera la jump-table, i casi vengono confrontati in ordine di comparizione, per cui nei casi più tipici vengono fatti meno confronti.

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

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 l'uso della cache del codice.

3.1.14. Se una funzione riceve almeno sei argomenti, e viene chiamata spesso con gli stessi valori tranne eventualmente uno o due, crea un oggetto che contiene tutti gli argomenti, e passa alla funzione tale oggetto per puntatore a costante o riferimento a costante.

Se una funzione riceve pochi argomenti, questi vengono posti direttamente nei registri e quindi il passaggio è molto veloce; ma se non sono pochi, gli argomenti devono essere posti nello stack, anche se sono gli stessi della precedente chiamata alla stessa funzione.

Se invece si passa solo l’indirizzo di una struttura, questo indirizzo viene sicuramente posto in un registro, e i campi della struttura che non sono modificati tra chiamate successive della funzione devono essere assegnati solo la prima volta.

Per esempio, rispetto al seguente codice:

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

è probabilmente più efficiente 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);
}

3.1.15. Per memorizzare in un oggetto dei numeri interi, usa il tipo “int” o il tipo “unsigned int”, a meno che sia necessario un tipo più lungo; e per memorizzare dei numeri a virgola mobile, usa il tipo “double”, a meno che sia necessario il tipo “long double”. Se l’oggetto risultante è medio o grande, sostituisci i tipi interi con il tipo intero più piccolo in grado di contenerlo, ma senza usare i bit-field, e sostituisci 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. I tipi double sono efficienti quanto i float, ma sono più precisi. Tuttavia, nel caso di interi contenuti in array medi o grandi, è meglio minimizzare la dimensione in byte dell’array. Per esempio, per memorizzare un numero intero che può essere compreso tra -1000 e 1000, si può usare uno “short”, mentre per memorizzare un numero intero che può essere compreso tra 0 e 200, si può usare un “unsigned char”.

I bit-field contribuirebbero a minimizzare la dimensione in byte dell’array, ma la loro elaborazione introduce un rallentamento che potrebbe essere eccessivo, per cui andrebbero introdotti solo in fase di ottimizzazione.

3.1.16. 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, è solo perché è più efficiente dell'algoritmo STL generico.

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

Dato che tutti i citati algoritmi usano la ricerca binaria, sono più veloci dell'algoritmo find, che usa la ricerca sequenziale

3.2. Come evitare i costi di costrutti C++ che peggiorano le prestazioni

Rispetto al linguaggio C, il linguaggio C++ aggiunge alcuni costrutti, il cui utilizzo peggiora l'efficienza.

Alcuni di tali costrutti sono piuttosto efficienti, ed è quindi del tutto ragionevole pagarne il costo quando servono, ma è altrettanto ragionevole non pagarne il costo quando non li si usa.

Altri costrutti sono alquanto inefficienti, e devono quindi essere usati con grande parsimonia.

3.2.1. Chiama “throw” solamente quando si dovrà avvisare l’utente del fallimento del comando corrente.

Il sollevamento di una eccezione ha un costo molto elevato, dell’ordine dei 10000 cicli di processore. Se tale operazione viene effettuata solamente ogni volta che un messaggio viene mostrato all’utente o scritto in un file di log, si ha la garanzia che non verrà eseguita troppo spesso. Se invece la si effettua come operazione algoritmica, anche se pensata inizialmente per essere eseguita raramente, potrebbe finire per essere eseguita frequentemente.

3.2.2. Non usare sistematicamente la derivazione virtual, ma solo quando due o più classi devono condividere la rappresentazione di una classe base comune.

Le funzioni membro delle classi base derivate in modo virtual sono un po’ più lente delle funzioni membro derivate in modo non-virtual.

Per esempio, considera le seguenti definizioni di classe:

class A { ... };
class B1: public A { ... };
class B2: public A { ... };
class C: public B1, public B2 { ... };

Con tali definizioni, ogni oggetto di classe C contiene due oggetti distinti di classe A, uno facente parte della classe base B1, e l'altro facente parte della classe base B2.

Questo non costituisce un problema se la classe A non ha nessuna variabile membro non-static.

Se invece tale oggetto di classe A contiene qualche variabile membro, e si intende che debba essere unico per ogni oggetto di classe C, si deve usare la derivazione virtual, nel seguente modo:

class A { ... };
class B1: virtual public A { ... };
class B2: virtual public A { ... };
class C: public B1, public B2 { ... };

Questa situazione è l'unica in cui è necessaria la derivazione virtual.

3.2.3. In ogni classe, non definire sistematicamente virtual tutte le funzioni membro, ma solo le funzioni membro di cui prevedi la necessità di una ridefinizione, a parte il distruttore, il quale deve essere definito virtual se e solo se la classe contiene almeno un'altra funzione membro virtual.

A parità di condizioni, le classi che contengono almeno una funzione membro virtual occupano un po’ più spazio delle classi che non ne contengono, e gli oggetti delle classi che contengono almeno una funzione membro virtual occupano un po’ più spazio e la loro costruzione richiede un po’ più di tempo rispetto agli oggetti di classi che non contengono funzioni membro virtual. Le funzioni membro virtual occupano po’ più spazio e sono un po’ più lente da chiamare delle funzioni membro non-virtual.

3.2.4. In ogni classe, dichiara static ogni funzione membro che non accede ai membri non-static di tale classe.

In altre parole, dichiara static tutte le funzioni membro che puoi.

In questo modo, non viene passato l’argomento implicito this.

3.2.5. Non definire template di classe polimorfiche.

I template di classe, ogni volta che vengono istanziati, producono una copia del codice oggetto, e se contengono funzioni virtuali producono una copia della vtable e della RTTI. Questi dati ingrandiscono eccessivamente il programma.

3.2.6. Non annullare un puntatore dopo aver chiamato delete su di esso se sei sicuro che tale puntatore non verrà più usato.

L’uso più tipico dell’operatore delete sia ha quando in un distruttore si dealloca un oggetto posseduto dall’oggetto in corso di distruzione; in tale contesto, si chiama delete su una variabile membro di tipo puntatore. Dato che solitamente un distruttore non è così complicato da faticare a capire che cosa è già stato distrutto dell’oggetto corrente e che cosa non ancora, e dato che il puntatore usato per la chiamata a delete cesserà di esistere alla fine del distruttore, anche se si lascia il valore corrente del puntatore, non si corre il rischio di deallocarlo una seconda volta. D’altra parte, annullare il puntatore richiede una seppur piccolissima quantità di tempo.

3.2.7. Non usare una libreria di garbage-collection né gli smart-pointer con reference-count (boost::shared_ptr), a meno che se ne dimostri l’opportunità per il caso specifico.

La garbage collection, cioè il recupero automatico della memoria non più referenziata, fornisce la comodità di non doversi occupare della deallocazione della memoria, e previene i memory leak. Tale funzionalità non viene fornita dalla libreria standard, ma viene fornita da librerie non-standard. Tuttavia, tale tecnica di gestione della memoria offre prestazioni peggiori della deallocazione esplicita.

La libreria standard del C++98 contiene un solo smart-pointer, l’auto_ptr, che è efficiente. Altri smart-pointer sono forniti da librerie non-standard, come Boost, o verranno forniti dal C++0x. Tra di essi, gli smart-pointer basati su su reference-count, come lo shared_ptr di Boost, sono meno efficienti, e quindi devono essere usati sono nei casi in cui se ne dimostra la necessità. In particolare, compilando con l’opzione di gestione multithreading, tali funzionalità hanno pessime prestazioni, in quanto devono garantire l’atomicità delle operazioni.

Normalmente bisognerebbe, in fase di progettazione, cercare di assegnare ogni oggetto ad un proprietario, che avrà la responsabilità di distruggerlo. Quando tale assegnazione è difficile, in quanto più oggetti tendono a rimpallarsi la responsabilità di distruggere un oggetto, allora è opportuno usare uno smart-pointer con reference-count oopure una libreria di garbage-collection.

3.3. Come evitare inutili costruzioni e le distruzioni di oggetti

3.3.1. Dichiara le variabili il più tardi possibile.

Dichiarare una variabile il più tardi possibile, significa sia dichiararla nell’ambito più stretto possibile, sia dichiararla il più avanti possibile entro quell’ambito. Essere nell’ambito più stretto possibile comporta che se tale ambito non viene mai eseguito, l'oggetto associato alla variabile non viene mai costruito né distrutto. Essere il più avanti possibile all’interno di un ambito comporta che se prima di tale dichiarazione c’è un’uscita prematura, tramite return o break o continue, l’oggetto associato alla variabile non viene mai costruito né distrutto.

Inoltre, spesso all'inizio di una routine non si ha un valore appropriato per inizializzare l'oggetto associato alla variabile, e quindi si è costretti a inizializzarla con un valore di default, e poi assegnarle il valore appropriato. Se invece la si dichiara quando si ha a disposizione il valore appropriato, la si può inizializzare con tale valore senza bisogno di fare un successivo assegnamento.

3.3.2. Usa inizializzazioni invece di assegnamenti, e in particolare nei costruttori usa le liste di inizializzazione.

Se un oggetto di classe non viene inizializzato esplicitamente, viene comunque inizializzato automaticamente dal costruttore di default. In generale, chiamare il costruttore di default seguito da un assegnamento di un valore è meno efficiente o ugualmene efficiente che chiamare solo un costruttore con tale valore.

3.3.3. Usa gli operatori prefissi di incremento (++) e decremento (--) invece dei corrispondenti operatori postfissi, se il valore dell'espressione non viene usato.

Se l’oggetto incrementato è di un tipo fondamentale, non ci sono differenze tra le due forme, ma se si tratta di un tipo composito, l’operatore postfisso comporta la creazione di un inutile oggetto temporaneo e quello prefisso no.

Siccome ogni oggetto che è attualmente di un tipo fondamentale potrebbe diventare in futuro di una classe, è bene usare sempre l’operatore che in quest’ultimo caso è più efficiente.

Se invece il valore dell’espressione formata dall’operatore di incremento o decremento viene usata in un’espressione più grande, potrebbe essere opportuno usare l’operatore postfisso.

3.3.4. Usa gli operatori con assegnamento (come in “a += b”) invece dei normali operatori infissi (come in “a + b”).

Tipicamente un operatore infisso, come nell’espressione “a + b”, crea un oggetto temporaneo. Per esempio, nel seguente codice, gli operatori “+” creano stringhe temporanee, la cui creazione e distruzione richiede tempo:

string s1("abc");
string s2 = s1 + " " + s1;

Risulta più efficiente il seguente codice equivalente:

string s1("abc");
string s2 = s1;
s2 += " ";
s2 += s1;

in quanto l’operatore += non crea oggetti temporanei.

3.3.5. Quando devi passare un argomento x di tipo T a una funzione usa il seguente criterio:
        Se x è un argomento di solo input,
                se x può essere nullo,
                        passalo per puntatore a costante (const T* x ),
                altrimenti, se l’argomento è un tipo fondamentale o un iteratore o un oggetto-funzione,
                        passalo per valore (T x) o per valore costante (const T x ),
                altrimenti,
                        passalo per riferimento a costante (const T& x ),
        altrimenti, cioè se x è un argomento di solo output o di input/output,
                se x può essere nullo,
                        passalo per puntatore a non-costante (T* x ),
                altrimenti,
                        passalo per riferimento a non-costante (T& x).

Il passaggio per riferimento è più efficiente del passaggio per puntatore in quanto facilita al compilatore l’eliminazione della variabile, e in quanto il chiamato non deve verificare se il riferimento è valido o nullo; tuttavia, il puntatore ha il pregio di poter rappresentare un valore nullo, ed è più efficiente passare solo un puntatore, che un riferimento a un oggetto insieme a un booleano che indica se tale riferimento è valido.

Per oggetti che possono essere contenuti in uno o due registri, il passaggio per valore è più efficiente o ugualmente efficiente del passaggio per riferimento, in quanto tali oggetti possono essere contenuti in registri e non hanno livelli di indirettezza, pertanto questo è il modo più efficiente di passare oggetti sicuramente piccoli, come i tipi fondamentali, gli iteratori e gli oggetti-funzione. Per oggetti più grandi di due registri, il passaggio per riferimento è più efficiente del passaggio per valore, in quanto tali oggetti non devono essere copiati.

Un oggetto composito veloce da copiare potrebbe essere efficientemente passato per valore, ma, a meno che si tratti di un iteratore o di un oggetto-funzione, per i quali si assume l’efficienza della copia, tale tecnica è rischiosa, in quanto l’oggetto potrebbe diventare in futuro più lento da copiare. Per esempio, se un oggetto di classe Point contiene solo due float, potrebbe essere efficientemente passato per valore; ma se in futuro si aggiunge un terzo float, o se i float diventano double, potrebbe diventare più efficiente il passaggio per riferimento.

3.3.6. Dichiara explicit tutti i costruttori che possono ricevere un solo argomento, eccetto i costruttori di copia delle classi concrete.

I costruttori impliciti possono essere chiamati automaticamente dal compilatore che esegue una conversione automatica. A seconda della complessità del costruttore, tale chiamata può richiedere molto più tempo del necessario. Rendendo obbligatoriamente esplicita tale conversione, il compilatore potrebbe scegliere un’altra funzione in overload, evitando così di chiamare il costruttore, oppure segnalare errore e costringere il programmatore a scegliere un’altra strada per evitare la chiamata al costruttore.

Per i costruttori di copia delle classi concrete si deve fare eccezione, per consentirne il passaggio per valore. Per le classi astratte, anche i costruttori di copia possono essere dichiarati explicit, in quanto, per definizione, le classi astratte non si possono istanziare, e quindi gli oggetti di tale tipo non dovrebbero mai essere passati per valore.

3.3.7. Non dichiarare operatori di conversione (in C++0x, dichiarali explicit).

Gli operatori di conversioni consentono conversioni implicite, e quandi incorrono nello stesso problema dei costruttori impliciti.

Se tali conversioni sono necessarie, fornisci invece una funzione membro equivalente, che può essere chiamata solo esplicitamente.

3.3.8. Non usare sistematicamente l'idioma Pimpl, ma solo quando vuoi rendere il resto del programma indipendente dall'implementazione di una classe.

L'idioma Pimpl consiste nel memorizzare nell'oggetto solamente un puntatore alla struttura che contiene tutte le informazioni utili di tale oggetto.

Il vantaggio principale di tale idioma è che velocizza la compilazione incrementale del codice, cioè rende meno probabile che una piccola modifica ai sorgenti comporti la necessità di ricompilare grandi quantità di codice.

Tale idioma consente anche di velocizzare alcune operazioni, come lo swap tra due oggetti, ma in generale rallenta gli accessi ai dati dell'oggetto a causa del livello di indirettezza, e provoca un'allocazione aggiuntiva per ogni creazione e copia di tale oggetto. Quindi non dovrebbe essere usato per classi le cui funzioni membro pubblche sono chiamate frequentemente.

3.3.9. Nelle classi di iteratori o di oggetti-funzione, fa' in modo che tali oggetti siano piccolissimi e che non allochino memoria dinamica.

Gli algoritmi di STL passano tali oggetti per valore. Pertanto, se la loro copia non è estremamente efficiente, gli algoritmi STL diventano lenti.

3.4. Come evitare inutili allocazioni e deallocazioni di memoria

L’allocazione e la deallocazione di memoria dinamica sono operazioni molto lente, se confrontate con l’allocazione e la deallocazione di memoria automatica, cioè su stack.

Inoltre, tale tipo di allocazione comporta uno spreco di spazio per ogni allocazione, genera frammentazione della memoria virtuale, e produce una scarsa località dei dati, con conseguente scadente utilizzo sia delle cache dei dati della CPU che della memoria virtuale.

Tale allocazione/deallocazione in linguaggio C veniva fatta con le funzioni malloc e free. In C++, pur essendo ancora disponibili tali funzioni, le funzioni normalmente usate a tale scopo sono gli operatori new, new[], delete, e delete[].

Ovviamente, un modo di ridurre le allocazioni è ridurre il numero di oggetti costruiti, e quindi la sezione “Come evitare inutili costruzioni e le distruzioni di oggetti” serve indirettamente anche allo scopo di questa sezione.

Tuttavia, qui si presenteranno regole per ridurre il numero di allocazioni di memoria per un dato numero di chiamate all'operatore new.

3.4.1. Se un array statico o non grande ha lunghezza costante, non usare un oggetto vector, ma usa un array del C, o un oggetto boost:array.

I vector memorizzano i dati in un buffer allocato dinamicamente, mentre le altre soluzioni proposte allocano i dati nell’oggetto stesso. Questo consente di evitare allocazioni/deallocazioni di memoria dinamica e di favorire la località dei dati. Se l’array è medio o grande, tali vantaggi diminuiscono, e invece risulta più importante evitare di usare troppo spazio sullo stack.

3.4.2. Se devi allocare numerosi blocchi di memoria della stessa dimensione, assicurati di usare un allocatore a pool.

Un allocatore a pool alloca blocchi di memoria e fornisce servizi di allocazione/deallocazione di blocchi più piccoli di dimensione costante, offrendo alta velocità di allocazione/deallocazione, bassa frammentazione della memoria, uso efficiente delle cache dei dati e della memoria virtuale, grazie alla località dei dati. In particolare, un allocatore di questo tipo migliora notevolmente le prestazioni dei contenitori standard “list”, “set”, “multi_set”, “map”, e “multi_map”. Se la tua implementazione della libreria standard non usa già un allocatore a pool per questi contenitori, dovresti procurartene uno (per esempio, questo: http://www.codeproject.com/KB/stl/blockallocator.aspx), e specificarlo come parametro di template per le istanze di tali template di contenitori.

3.4.3. Per aggiungere elementi in fondo a una collezione, usa push_back con un elemento, o back_inserter in un algoritmo STL, o insert con un range.

La funzione push_back garantisce un tempo lineare ammortizzato, in quanto, nel caso del vector, ingrandisce esponenzialmente la capacità.

La classe back_inserter chiama internamente la funzione push_back.

La funzione insert permette di inserire in modo ottimizzato un'intera sequenza, e quindi una chiamata di questo tipo è più veloce di numerose chiamate a push_back.

3.5. Come velocizzare l’accesso alla memoria principale

3.5.1. Accedi alla memoria in ordine crescente; in particolare, scandisci gli array in ordine crescente, scandisci gli array multidimensionali usando gli indice più a destra per i cicli più interni, nei costruttori delle classi e negli operatori di assegnamento (operator=) accedi alle variabili membro nell’ordine in cui sono dichiarate nella classe.

La cache dei dati ottimizza gli accessi alla memoria in ordine sequenziale crescente. Quando si itera su un array multidimensionale, il loop più interno deve iterare sull’ultimo indice. In tal modo, è garantito che le celle vengono elaborate nell’ordine in cui si trovano in memoria. Per esempio:

float a[num_livelli][num_righe][num_colonne];
for (int liv = 0; liv < num_livelli; ++ liv) {
for (int r = 0; r < num_righe; ++r) {
for (int c = 0; c < num_colonne; ++c) {
a[liv][r][c] += 1;
}
}
}

3.5.2. Lascia l’allineamento di memoria suggerito dal compilatore.

I compilatori attivano di default un criterio di allineamento dei tipi fondamentali, per cui le variabili di ogni tipo possono iniziare solo a determinati indirizzi di memoria. Tale criterio solitamente garantisce le massime prestazioni, ma può introdurre degli spazi inutilizzati tra le variabili. Se per alcune strutture è necessario eliminare tali spazi, usa le direttiva “pragma” per confinare tale impaccamento alle sole strutture per cui è necessario.

3.5.3. Definisci nella stessa unità di compilazione tutte le funzioni membro di una classe, le funzioni “friend” di tale classe e le funzioni delle classi “friend” di tale classe, a meno che il file risultante diventi scomodo da gestire per la sua dimensione eccessiva.

In tal modo, il codice macchina prodotto compilando tali routine e i dati statici a cui accederà avranno indirizzi vicini tra loro.

3.6. Quando usare i thread

3.6.1. Ogni volta che in un’applicazione interattiva devi eseguire un compito che può richiedere più di una manciata di secondi, assegna tale compito a un apposito thread di calcolo di priorità più bassa del normale.

In tal modo, il thread principale si occupa di gestire l’interfaccia utente ed è pronta per rispondere ad altri comandi. Assegnando al thread di calcolo priorità più bassa del normale, l’interfaccia utente rimane veloce quasi come se non ci fosse un’elaborazione in corso.

3.6.2. In un sistema multicore, se riesci a suddividere un’elaborazione in più thread, usa tanti thread di calcolo quanti sono i core di processore.

In tal modo ogni core può elaborare un thread. Se i thread di calcolo fossero più dei processori, ci sarebbe contesa tra i thread, e questo rallenterebbe l’elaborazione. Il thread di interfaccia utente non rallenta, in quanto è pressoché inattivo.

3.6.3. Se sviluppi un'applicazione single-threaded non usare librerie progettate per applicazioni multi-threaded.

Le tecniche per rendere thread-safe una libreria possono dover usare memoria e tempo. Se non usi i thread, evita di pagarne il costo.

3.6.4. Se sviluppi una libreria, gestisci correttamente il caso in cui sia usata da applicazioni multi-threaded, ma ottimizza anche il caso in cui sia usata da applicazioni single-threaded.

Le tecniche per rendere thread-safe una libreria possono dover usare memoria e tempo. Se gli utenti della tua libreria non usano i thread, evita di fargliene pagare il costo.

3.6.5. Usa primitive di mutua esclusione solo quando più thread accedono contemporaneamente agli stessi dati, e almeno uno degli accessi è in scrittura.

Le primitive di mutua esclusione richiedono tempo.

Se sei sicuro che un thread inizia a leggere un'area di memoria solo dopo che un altro ha finito di scriverla, non c'è bisogno di sincronizzare ulteriormente gli accessi.

Se sei sicuro che in un dato periodo di tempo nessun thread scrive in un'area di memoria, non c'è bisogno di sincronizzare gli accessi in lettura a tale area.

4. Tecniche generali di ottimizzazione

In questa sezione vengono proposte alcune tecniche di ottimizzazione algoritmica di ampia utilizzabilità, e sostanzialmente indipendenti sia dal linguaggio di programmazione, che dalla piattaforma software e hardware.

4.1. Input/Output

4.1.1. Per eseguire operazioni di input/output, invece di usare le primitive del linguaggio, usa direttamente le chiamate al sistema operativo.

Le primitive di I/O dei linguaggi di programmazione sono pensate soprattutto tenendo conto della comodità d’uso invece che le prestazioni, in quanto solitamente per tale codice il collo di bottiglia non è il processore, ma la periferica. Tuttavia, a volte si vuole ottimizzare anche il codice eseguito per effettuare operazioni di I/O. Inoltre, nel caso del C++, la libreria degli stream è particolarmente inefficiente. Le chiamate al sistema operativo garantiscono la massima efficienza, a costo di rinunciare alla portabilità ad altri sistemi operativi, e di dover gestire manualmente la formattazione, la bufferizzazione, e gli errori.

4.1.2. Invece di memorizzare i dati su file in modalità testuale, memorizzali in formato binario.

I numeri in formato binario occupano mediamente meno spazio, e quindi richiedono meno tempo per essere letti da disco e scritti su disco, ma, soprattutto, scrivendo e leggendo i dati nello stesso formato che hanno in memoria non c’è bisogno di nessuna conversione da o verso il formato testuale.

4.1.3. Eccetto che in una sezione critica di un sistema real-time, se devi accedere a gran parte di un file binario in modo non-sequenziale, invece di accedervi ripetutamente con operazioni di seek oppure di caricarlo tutto in un buffer dell’applicazione, usa i Memory Mapped File, se il sistema operativo fornisce tale strumento.

Mentre le operazioni di posizionamento (seek) richiedono un certo tempo, con i memory mapped file tali operazioni diventano semplici assegnazioni a un puntatore.

Per quanto riguarda il caricamento in memoria di un intero file per elaborazioni successive, usando le primitive di lettura di file i dati vengono letti prima nella cache del disco e poi nella memoria del processo, mentre con i memory mapped file si accede direttamente al buffer caricato dal disco, risparmiando così sia un’operazione di copia che lo spazio di memoria per la cache del disco. Analoga situazione si ha per la scrittura su disco.

Inoltre, se più processi devono caricare in memoria lo stesso file, lo spazio di memoria viene allocato per ogni processo, mentre usando i memory mapped file il sistema operativo tiene in memoria una sola copia dei dati, condivisa da tutti i processi.

Infine, in condizioni di scarsità di memoria, il sistema operativo scrive nell'area di swap del disco anche la memoria del processo che non è stata modificata, mentre si limita a scartare le pagine non modificate del memory mapped file, senza scriverle sul disco.

Tuttavia, l’uso di memory mapped file non è appropriato in una porzione critica di un sistema real-time, in quanto l'accesso a tali dati ha una latenza fortemente variabile a seconda che il dato acceduto sia in cache o su disco.

A rigore, questa è una tecnica dipendente dalla piattaforma, in quanto la funzionalità dei memory mapped files non esiste in tutti i sistemi operativi. Tuttavia, dato che tale funzionalità esiste in tutti i principali sistemi operativi dotati di memoria virtuale, questa tecnica si può considerare di ampia applicabilità.

4.2. Caching

Le tecniche di caching si basano sul principio che se una funzione pura (o funzione matematica) deve essere calcolata più volte per un dato argomento, e tale calcolo richiede parecchio tempo, si risparmia tempo salvando il risultato la prima volta che si esegue la funzione, e ritornando il valore salvato le volte successive.

4.2.1. Se devi calcolare spesso una funzione avente come dominio un piccolo intervallo di numeri interi, pre-calcola (in fase di sviluppo del software o in fase di inizializzazione dell’applicazione) tutti i valori della funzione per ogni valore del dominio e ponili in un array statico, detto “lookup-table”. Quando dovrai calcolare il valore della funzione per un dato valore del dominio, preleva l’elemento corrispondente dell’array.

L’accesso a un array, soprattutto se si trova nella cache dei dati del processore, è molto veloce. Per esempio, dovendo calcolare la radice quadrata di un numero intero compreso tra 0 e 9, si può usare la seguente funzione:

double sqrt10(int i) {
static double lookup_table[] = {
0, 1, sqrt(2.), sqrt(3.), 2,
sqrt(5.), sqrt(6.), sqrt(7.), sqrt(8.), 3,
};
assert(0 <= i && i < 10);
return lookup_table[i];
}

4.2.2. Se devi calcolare spesso una funzione con gli stessi argomenti, salva in variabili statiche gli argomenti e il risultato. Quando devi calcolare la funzione, confronta i nuovi argomenti con quelli vecchi. Se coincidono, rendi il risultato memorizzato, altrimenti calcola il risultato e memorizza nelle variabili statiche gli argomenti e il risultato.

Per esempio, invece di scrivere:

double f(double x, double y) {
    return sqrt(x * x + y * y);
}

si può scrivere:

double f(double x, double y) {
    static double prev_x = 0;
    static double prev_y = 0;
    static double result = 0;
    if (x == prev_x && y == prev_y) {
        return result;
    }
    prev_x = x;
    prev_y = y;
    result = sqrt(x * x + y * y);
    return result;
}

Si noti che, per avere un vantaggio prestazionale, non è necessario che la funzione sia chiamata con gli stessi parametri per tutta l’esecuzione del programma. È sufficiente che sia chiamata alcune volte con gli stessi parametri, poi altre volte con altri parametri, e così via. In tale caso, il calcolo viene effettuato solo al cambiamento dei parametri.

Ovviamente, questa soluzione peggiora le prestazioni, invece di migliorarle, nel caso in cui la funzione è chiamata con parametri variabili spesso, o se il confronto tra i parametri nuovi e quelli vecchi richiede più tempo del calcolo della funzione.

Questo algoritmo è detto anche "caching a un posto", in quanto si memorizza solo una coppia argomento-risultato.

4.2.3. Se devi calcolare spesso una funzione avente un dominio limitato, usa una mappa inizialmente vuota. Quando devi calcolare la funzione, cerca l’argomento nella mappa. Se lo trovi, rendi il valore associato, altrimenti calcola il risultato e inserisci nella mappa la coppia argomento-risultato.

In alcuni casi, la funzione viene chiamata con parametri variabili, ma appartenenti a un insieme molto limitato. In tale caso si può implementare una cache a più posti, invece di una cache a un singolo posto, come quella appena vista. Ecco un esempio, riferito alla stessa funzione di sopra:

double f(double x, double y) {
    static const int n_buckets = 8; // Dovrebbe essere una potenza di 2
    static struct {
        double x; double y; double result;
    } cache[n_buckets];
    static int last_read_i;
    static int last_written_i;
    int i = last_read_i;
    do {
        if (cache[i].x == x && cache[i].y == y) {
            return cache[i].result;
        }
        i = (i + 1) % n_buckets;
    } while (i != last_read_i);
    last_read_i = last_written_i = (last_written_i + 1) % n_buckets;
    cache[last_written_i].x = x;
    cache[last_written_i].y = y;
    cache[last_written_i].result = sqrt(x * x + y * y);
    return cache[last_written_i].result;
}

Si noti che l’uso di variabili statiche rende la routine non più thread-safe. Se questa routine deve poter essere chiamata contemporaneamente da più thread, è necessario sostituire le variabili statiche con variabili distinte per ogni thread.

Si noti anche che negli esempi si assumeva che la funzione valesse 0 per i parametri di input entrambi zero. In caso contrario, si dovrebbe, o inizializzare il campo result al valore appropriato, o aggiungere un flag che indica se tale campo ha un valore valido e controllare tale flag, o usare un valore inammissibile per il campo result come indicatore del fatto che non contiene un valore valido.

Per cache piccole, nel caso sopra di 8 elementi, l’algoritmo più efficiente è la scansione sequenziale su un array. Tuttavia, se si volesse fare una cache di dimensioni maggiori, sarebbero più efficienti un albero di ricerca o una hashtable.

Si noti infine, che la ricerca parte sempre dall’ultimo elemento letto, che solitamente è il più probabile, e la scrittura in cache di un elemento non presente sovrascrive l’elemento successivo all’ultimo elemento scritto, cioè si sostituisce l’elemento meno recentemente scritto. Un algoritmo migliore sarebbe sostituire l’elemento meno recentemente letto, ma richiederebbe che si prenda nota dei tempi di accesso.

Questo algoritmo è detto anche "caching a N posti".

4.3. Altre tecniche

4.3.1. Prima di confrontare una stringa con una serie di altre stringhe, trasforma tutte le stringhe in lettere maiuscole (o in minuscole), ed esegui il confronto distinguendo tra minuscole e maiuscole (case-sensitive).

Il confronto tra stringhe case-insensitive costa di più del confronto case-sensitive.

4.3.2. In una classe, invece di definire una funzione che restituisce al chiamante una collezione di dati, definisci una funzione che restituisce un iteratore di uscita, con il quale si possono generare i dati richiesti.

Supponiamo di avere una collezione (o un insieme di collezioni) incapsulati in una classe. Tale classe espone uno o più metodi per estrarre (o filtrare) da tale collezione un sottoinsieme. Un modo di ottenere ciò è costruire una nuova collezione, copiarci i dati estratti, e restituire tale collezione al chiamante. Questa tecnica è però inefficiente, perché ognuna delle suddette operazioni è costosa.

Ecco una tecnica equivalente ma più efficiente. La funzione rende un iteratore di ingresso (input iterator). Il chiamante usa tale iteratore per estrarre, uno alla volta i dati filtrati.

Si noti che questa soluzione non è del tutto equivalente, in quanto se durante l’uso dell’iteratore la collezione viene modificata da un’altra chiamata all’oggetto che incapsula la collezione, eventualmente proveniente da un altro thread, può succedere che l’iteratore sia invalidato, o anche solo che l’insieme filtrato non corrisponda ai criteri impostati. Pertanto questa tecnica è da usare solo se si ha la certezza che la collezione sottostante non viene modificata da nessuno, se non tramite l’iteratore stesso, durante tutta la vita dell'iteratore.

Questa tecnica è indipendente dal linguaggio di programmazione, in quanto il concetto di iteratore è un design pattern, implementabile in qualsiasi linguaggio.

4.3.3. Per cercare numerose volte in una collezione che viene variata raramente o mai, invece di usare un albero di ricerca o una hashtable, può essere più efficiente porre i dati in un array, ordinare l'array, e usare la ricerca binaria.

Se l'array viene saltuariamente modificato, l'algoritmo può essere ancora competitivo, purché le modifiche siano molte meno delle ricerche.

Se la modifica consiste in un singolo inserimento o modifica o eliminazione di un elemento, conviene effettuare degli scorrimenti nell'array.

Se invece la modifica è più massiccia, conviene ricreare tutto l'array.

4.3.4. Per ordinare un insieme di dati aventi un range limitato, usa l’algoritmo countingsort.

L’algoritmo countingsort ha complessità O(N+M), dove N è il numero di elementi da ordinare e M è il range delle chiavi di ordinamento, cioè la differenza tra la chiave massima e la chiave minima. Nel caso in cui si vogliano ordinare N elementi la cui chiave è un numero intero appartenente a un intervallo di non oltre 2 * N valori, questo algoritmo può essere notevolmente più veloce di quicksort. A volte è più veloce anche per range più grandi, fino a 50 * N.

Questo algoritmo può essere usato anche per un ordinamento parziale; per esempio, se la chiave è un intero compreso tra zero e un miliardo, si può ordinare solamente in base al byte più significativo della chiave, così da ottenere un ordine tale per cui per ogni n vale la formula a[n] < a[n + 1] + 256*256*256.

4.3.5. Se per una lista ti basta l’iteratore in avanti, inserire gli elementi solo all’inizio o dopo l’elemento corrente, e non ti serve sapere quanti elementi ci sono nella lista, usa un oggetto “slist” (o in C++0x, “forward_list”).

La “slist”, pur avendo molte limitazioni, occupa meno memoria ed è più veloce.

Infatti, tipicamente, l’intestazione di un oggetto “std::list” contiene un puntatore alla cima, un puntatore al fondo della lista, e il contatore del numero di elementi, mentre l’intestazione di un oggetto “slist” contiene solo un puntatore alla cima della lista. Inoltre, tipicamente, ogni nodo di un oggetto “std::list” contiene un puntatore all’elemento precedente e un puntatore all’elemento successivo, mentre ogni nodo di un oggetto “slist” contiene solo un puntatore all’elemento successivo. Infine, ogni inserimento di un elemento da un oggetto “std::list” deve aggiornare quattro puntatori e un contatore, mentre ogni inserimento da un oggetto “slist” deve aggiornare solo due puntatori.

4.3.6. Se devi solo dividere una sequenza in due gruppi in base a un criterio, usa un algoritmo di partizionamento, invece di uno di ordinamento.

In STL c'è l'algoritmo partition, che è più veloce dell'algoritmo sort, in quanto ha complessità O(N).

4.3.7. Se non devi mantenere l'ordine delle entità equivalenti, non usare un algoritmo stabile.

In STL c'è l'algoritmo stable_partition, che è leggermente più lento dell'algoritmo partition, e c'è l'algoritmo stable_sort, che è leggermente più lento dell'algoritmo sort.

4.3.8. Se devi solo individuare i primi N elementi di una sequenza, o l'N-esimo elemento di una sequenza, usa un algoritmo di partizionamento d'ordine, invece di un ordinamento.

In STL c'è l'algoritmo nth_element, che, pur essendo è leggermente più lento dell'algoritmo stable_partition, è notevolmente più veloce dell'algoritmo sort, in quanto ha complessità O(N).

4.3.9. Se devi solo ordinare i primi N elementi di una sequenza, usa un algoritmo di statistica d'ordine, invece di un ordinamento.

In STL ci sono gli algoritmi partial_sort e partial_sort_copy, che, pur essendo più lenti di dell'algoritmo nth_element, sono tanto più veloci dell'algoritmo sort quanto più è breve la sequenza parziale da ordinare rispetto a quella totale.

5. Tecniche di ottimizzazione specifiche del linguaggio C++, ma indipendenti dalla piattaforma

In questa sezione si suggeriscono dei trucchi da adottare solamente nei colli di bottiglia, in quanto, pur rendendo il codice più veloce, ne rendono più complessa la stesura e lo rendono meno manutenibile. Inoltre, tali linee-guida in alcuni casi potrebbero sortire l’effetto indesiderato di peggiorare le prestazioni invece che migliorarle, per cui bisognerebbe sempre misurarne l’effetto prima di rilasciarle. Le tecniche di ottimizzazione sono raggruppate in base all’obiettivo che si propongono di raggiungere.

5.1. Come ridurre le operazioni di allocazione e deallocazione

5.1.1. In funzioni non-ricorsive, per allocare spazio di dimensione variabile ma non grande, usa la funzione “alloca”.

È molto efficiente, in quanto alloca spazio sullo stack.

È una funzione non-standard, ma presente in molti compilatori per vari sistemi operativi.

Può essere usata anche per allocare un array di oggetti che hanno un costruttore, chiamando la placement new sullo spazio ottenuto, ma non per array di oggetti che hanno un distruttore o che, direttamente o indirettamente, contengono membri che hanno un distruttore, in quanto tali distruttori non verrebbero mai chiamati.

È piuttosto pericolosa, in quanto, se chiamata troppe volte o con un valore troppo grande, esaurisce lo stack, e, se chiamata per allocare lo spazio in cui verranno creati oggetti dotati di distruttore, provoca resourse leak.

5.1.2. Sposta prima dei colli di bottiglia le allocazioni di memoria e dopo i colli di bottiglia le deallocazioni.

La gestione di memoria dinamica di dimensione variabile è molto più lenta della gestione della memoria sullo stack. Analogo ragionamento va fatto per le operazioni che indirettamente provocano allocazioni, come la copia di oggetti che, direttamente o indirettamente, possiedono memoria dinamica.

5.1.3. Prima di aggiungere elementi a oggetti “vector” o “string”, chiama “reserve” con una dimensione sufficiente per la maggior parte dei casi.

Se si aggiungono ripetutamente elementi a oggetti “vector” o “string”, ogni tanto viene eseguita una costosa operazione di riallocazione del contenuto. Per evitarla, basta allocare inizialmente lo spazio che sarà necessario.

5.1.4. Per svuotare un oggetto " vector<T> x" senza deallocarne la memoria, usa l’istruzione "x.resize(0);"; per svuotarlo deallocandone la memoria, usa l’istruzione " vector<T>().swap(x);".

Per svuotare un oggetto vector, esiste anche l’istruzione “clear()”; tuttavia lo standard non specifica se tale istruzione conserva la capacità oppure no. Se questa istruzione deve essere eseguita spesso, e si vuole essere sicuri di evitare frequenti riallocazioni, si deve chiamare la “resize”, che secondo lo standard conserva sicuramente la capacità. Se invece si vuole essere sicuri di liberare la memoria usata da tale collezione, in quanto per un po’ tale oggetto non verrà usato, oppure verrà usato con un numero molto più piccolo di elementi, si deve chiamare la “swap” su un nuovo oggetto temporaneo vuoto.

5.1.5. A ogni classe concreta T che, direttamente o indirettamente, possiede della memoria dinamica, aggiungi una funzione membro public con la seguente firma:
void swap(T&) throw();
e nello stesso namespace che contiene la classe T aggiungi la seguente funzione non-membro:
void swap(T& lhs, T& rhs) { lhs.swap(rhs); }
e, se la classe non è un template di classe, nello stesso file in cui è dichiarata la classe T aggiungi la seguente funzione non-membro:
namespace std { template<> swap(T& lhs, T& rhs) { lhs.swap(rhs); } }

Nella libreria standard la funzione std::swap viene richiamata in molti algoritmi. Tale funzione ha una implementazione generica e specializzazioni per vari tipi della libreria standard.

Se gli oggetti di una classe non-standard vengono usati in algoritmi della libreria standard, e non viene fornito un overload della funzione swap, viene usata l'implementazione generica.

L'implementazione generica di swap comporta la creazione e distruzione di un oggetto temporaneo e l'esecuzione di due assegnamenti di oggetti. Tali operazioni richiedono molto tempo se applicate ad oggetti che possiedono della memoria dinamica, in quanto tale memoria viene riallocata per tre volte.

Il possesso può essere indiretto. Per esempio, se una variabile membro è un oggetto string o vector, o è un oggetto che contiene un oggetto string o vector, la memoria posseduta da tali oggetti viene riallocata ogni volta che si copia l'oggetto che li contiene. Se l'oggetto non possiede memoria dinamica, la copia dell'oggetto è molto più veloce, e comunque non sensibilmente più lenta che usando altre tecniche, e quindi non si deve fare niente. Se la classe è astratta, non dovrebbe mai essere chiamata la funzione swap sugli oggetti di tale tipo, e anche in questo caso non si deve fare niente.

Per velocizzare la funzione swap, la si deve specializzare per la propria classe. Ci sono due modi possibili: nel namespace della stessa classe (che può essere quello globale) come overload, o nel namespace std come specializzazione del template standard. È meglio definirla in entrambi i modi, in quanto, in primo luogo, se si tratta di un template di classe solo il primo modo è possibile, e poi alcuni compilatori non accettano o segnalano un avvertimento se è definita solo nel primo modo.

L'implementazione di tali funzioni devono accedere a tutti i membri dell'oggetto, e quindi hanno bisogno di richiamare una funzione membro, che per convenzione si chiama ancora swap, che effettua il lavoro.

Tale lavoro deve consistere nell'effettuare lo swap di tutti i membri non-static dei due oggetti, tipicamente chiamando la funzione swap su di essi, senza qualificarne il namespace.

Per consentire di trovare la funzione std:: swap, la funzione deve iniziare con la seguente istruzione:

using std::swap;

5.2. Come ridurre i costrutti che richiamano routine del supporto run-time

5.2.1. Evita di usare l’operatore “typeid”. Al suo posto, cerca di usare una funzione virtual o il design pattern Visitor.

Tale operatore può richiedere un tempo superiore a quello richiesto da una semplice chiamata a funzione.

5.2.2. Evita di usare l’operatore “dynamic_cast”. Piuttosto, usa l’operatore “typeid”.

Tale operatore può richiedere un tempo notevolmente superiore a quello richiesto da una semplice chiamata a funzione, e maggiore anche a quello richiesto dall’operatore “typeid”.

5.2.3. Usa la specifica di eccezioni vuota (cioè aggiungi “throw()” dopo la dichiarazione) alle funzioni di cui sei certo che non solleveranno eccezioni.

Alcuni compilatori utilizzano tale informazione per ottimizzare la contabilità necessaria per gestire le eventuali eccezioni.

5.2.4. Sposta le istruzioni “try” prima dei colli di bottiglia, e le istruzioni “catch” dopo, in modo che includano l’intero collo di bottiglia.

L’esecuzione di un blocco try/catch talvolta ha costo zero, ma altre volte comporta un rallentamento. Evita di eseguire tale blocco all’interno dei colli di bottiglia.

5.2.5. Se il processore non contiene un’unità a virgola mobile, evita le operazioni a virgola mobile.

Gli odierni processori per sistemi desktop e server contengono hardware dedicato all’aritmetica a virgola mobile, per cui tali operazioni, eccettuate somme e sottrazioni, sono pressoché altrettanto veloci quanto quelle su numeri interi. Alcuni processori dedicati per sistemi embedded, invece, non contengono hardware dedicato all’aritmetica a virgola mobile. Pertanto tali operazioni vengono solamente emulate con lentissime funzioni di libreria. In tal caso, risulta molto più veloce utilizzare l’aritmetica intera, o meglio a virgola fissa, cioè usando degli interi intendendoli moltiplicati per un fattore di scala. Ogni numero viene moltiplicato per tale fattore in fase di input e viene per lo stesso fattore in fase di output, o viceversa.

5.2.6. Le funzioni standard di conversione da numero intero a stringa e da numero a virgola mobile a stringa sono inefficienti. Per ottimizzarle, usa librerie non-standard o riscrivi tali funzioni.

5.3. Come diminuire il numero di istruzioni eseguite

5.3.1. Per controllare se un numero intero “i” è compreso tra “min_i” e “max_i”, estremi inclusi, usa l’espressione “unsigned(i – min_i) <= unsigned(max_i – min_i)”.

La suddetta formula è equivalente a quella più intuitiva:

    min_i <= i && i <= max_i

la quale tuttavia richiede due confronti invece di uno solo. In particolare, per controllare che un numero “i” sia valido come indice per accedere a un array di “size” elementi, si può scrivere l’espressione:

 unsigned(i) < unsigned(size)

Se le espressioni sono già unsigned, le conversioni non sono necessarie.

5.3.2. Nelle istruzioni switch, poni i casi in ordine di probabilità decrescente.

Nella linea-guida 3.1.12 si consigliava di porre prima di casi più tipici, cioè quelli che si presume siano più probabili. Come ulteriore ottimizzazione, si dovrebbe contare, in esecuzioni tipiche, il numero di volte in cui viene eseguito ognuno dei singoli casi, e porre i casi in ordine da quello eseguito più volte a quello eseguito meno volte.

5.3.3. Se un certo valore intero è una costante nel codice applicativo, ma è una variabile nel codice di libreria, rendilo un parametro di template.

Supponi che stai scrivendo il seguente template di funzione di libreria, in cui sia x che y non hanno un valore definito in fase di sviluppo della libreria:

template <typename T> T f1(T x, T y) { return x * y; }

Tale funzione può essere chiamata dal seguente codice applicativo, nel quale x non ha un valore costante, ma y è la costante 4:

int a = f1(b, 4);

Tale chiamata istanzia automaticamente la seguente funzione:

int f1(int x, int y) { return x * y; }

Se mentre scrivi la libreria sai che il chiamante ti passerà sicuramente una costante intera come argomento y, puoi trasformare il template nel seguente:

template <typename T, int Y> T f2(T x) { return x * Y; }

Tale funzione può essere chiamata dal seguente codice applicativo:

int a = f2<int, 4>(b);

Tale chiamata istanzia automaticamente la seguente funzione:

int f2(int x) { return x * 4; }

Questa funzione è più veloce della precedente istanza di f1, per i seguenti motivi:

In generale, i parametri di template interi sono delle costanti per chi istanzia il template e quindi per il compilatore, e le costanti sono gestite in modo più efficiente delle variabili. Inoltre, alcune operazioni su costanti vengono calcolate in fase di compilazione.

5.3.4. Se devi scrivere una classe base astratta di libreria tale che in ogni algoritmo applicativo si userà una sola classe derivata da tale classe base, usa il “Curiously Recurring Template Pattern”.

Supponi che stai scrivendo la seguente classe base di libreria:

class Base {
public:
virtual void f() = 0;
void g() { f(); }
};

In questa classe, la funzione g esegue un algoritmo che usa una chiamata a f come punto di personalizzazione dell'algoritmo. Lo scopo è consentire di scrivere il seguente codice applicativo:

class Derivata1: public Base {
public: virtual void f() { ... }
};



class Derivata2: public Base {
public: virtual void f() { ... }
};
...
Base* p1 = new Derivata1;
p1->g();
Base* p2 = new Derivata2;
p2->g();

In tal caso, è possibile convertire il precedente codice di libreria nel seguente:

template <class Derivata> class Base {
public:
void f() { static_cast<Derivata*>(this)->f(); }
void g() { f(); }
};

Il codice applicativo, di conseguenza, diventerà il seguente:

class Derivata1: public Base<Derivata1> {
public: void f() { ... }

};



class Derivata2: public Base<Derivata2> {
public: void f() { ... }

};
...
Derivata1* p1 = new Derivata1;
p1->g();
Derivata2* p2 = new Derivata2;
p2->g();

In tal modo, si ha binding statico delle funzioni membro Derivata1::f e Derivata2::f rispettivamente alla funzioni membro Base<Derivata1>::g e Base<Derivata1>::g, cioè si evitano chiamate a funzioni virtuali.

Tuttavia, con questa soluzione non è possibile definire un puntatore o riferimento a una classe base di Derivata1 e Derivata2, in quanto risultano due tipi senza acluna relazione, e quindi questa soluzione non è adatta se si vuole permettere al codice applicativo di definire un contenitore di oggetti di tipo Base.

Altre limitazioni sono che il tipo Base è necessariamente un tipo astratto, che un oggetto di tipo Derivata1 non può essere convertito in un oggetto di tipo Derivata2 o viceversa, e che per ogni derivazione di Base tutto il codice di Base viene duplicato.

5.3.5. Se un oggetto che implementa il pattern strategy (detto anche policy) è una costante nel codice applicativo, ma il codice di libreria deve poter gestire più strategie, rendi la classe di tale oggetto un parametro di template.

Supponi che stai scrivendo il seguente codice di libreria, che implementa il pattern strategy,

class C;
class Strategy {
public:
virtual bool is_valid(const C&) const = 0;
virtual void run(C&) const = 0;


};

class C {
public:
void set_strategy(const Strategy& s): s_(s) { }

void f() { if (s.is_valid(*this)) s.run(*this); }
private:
Strategy s_;
};

avente lo scopo di consentire il seguente codice applicativo:

class MyStrategy: public Strategy {
public:
virtual bool is_valid(const C& c) const { ... }
virtual void run(C& c) const { ... }
};
...

MyStrategy s; // Oggetto che rappresenta la strategia.
C c; // Oggetto con strategia personalizzabile.
c.set_strategy(s); // Assegnazione della strategia.
c.f(); // Esecuzione con strategia assegnata.

In tal caso, è possibile convertire il precedente codice di libreria nel seguente:

template <class Strategy>

class C {
public:

void f() { if (Strategy::is_valid(*this)) Strategy::run(*this); }
};

Il codice applicativo, di conseguenza, diventerà il seguente:

class MyStrategy {
public:
static bool is_valid(const C<MyStrategy>& c) { ... }
static void run(C<MyStrategy>& c) { ... }
};
...

C<MyStrategy> c; // Oggetto con strategia preassegnata.
c.f(); // Esecuzione con strategia preassegnata.

In tal modo, si evita l'oggetto-strategia, e si ha il binding statico delle funzioni membro MyStrategy::is_valid e MyStrategy::run, cioè si evitano chiamate a funzioni virtuali.

Tuttavia, tale soluzione non consente né di decidere la strategia in fase di esecuzione, né di cambiarla durante la vita dell'oggetto, e duplica il codice della strategia per ogni istanziazione di tale classe.

5.3.6. Dovendo eseguire operazioni booleane su un insieme di singoli bit, affianca tali bit in una variabile di tipo “unsigned int”, e usa gli operatori bit-a-bit su tale oggetto.

Gli operatori bit-a-bit (“&”, “|”, “^”, “<<”, e “>>”) sono tradotti in singole istruzioni veloci, e operano su tutti i bit di un registro in una sola istruzione.

5.4. Come ridurre le costruzioni e distruzioni di oggetti

Spesso capita che per elaborare un’espressione venga creato un oggetto temporaneo, che viene distrutto alla fine della stessa espressione in cui viene creato. Se tale oggetto è di un tipo fondamentale, il compilatore quasi sempre riesce a evitarne la creazione, e comunque la creazione e distruzione di un oggetto di un tipo fondamentale sono veloci. Se l’oggetto è invece di un tipo composito. La creazione e distruzione possono avere un costo arbitrariamente alto, in quanto comportano la chiamata di un costruttore e di un distruttore. In questa sezione si descrivono alcune tecniche per evitare che siano creati oggetti temporanei di tipo composito, e quindi che siano chiamati i relativi costruttori e distruttori.

5.4.1. Per le funzioni che non siano espanse inline, cerca di dichiarare il tipo di ritorno “void” o “bool” o intero o puntatore o riferimento. Comunque, evita di dichiarare un tipo di ritorno la cui copia sposta oltre 8 byte. Se non fosse fattibile, almeno costruisci l’oggetto da ritornare nelle stesse istruzioni “return”.

Nella compilazione di una funzione non espansa inline, il compilatore non può sapere se il valore di ritorno verrà usato, e quindi lo deve comunque generare. Generare un intero o un puntatore o un riferimento costa poco o niente, ma generare numeri a virgola mobile od oggetti più complessi richiede tempo. Se la copia comporta l’allocazione di risorse, il tempo richiesto è enormemente maggiore, ma anche senza allocazioni, il tempo richiesto è cresce al crescere dei numero delle word che vengono copiate quando si copia un oggetto di tale tipo. Comunque, se si costruisce l’oggetto da ritornare nelle stesse istruzioni “return”, senza quindi assegnare tale valore a una variabile, si sfrutta l’ottimizzazione garantita dallo standard detta Return Value Optimization, che previene la creazione di oggetti temporanei. Alcuni compilatori riescono a evitare la creazione di oggetti temporanei anche se sono legati a variabili locali (Named Return Value Optimization), ma in generale questo non è garantito. Per verificare se viene attuata una di tali ottimizzazioni, inserisci un contatore nei costruttori, nei distruttori, e negli operatori di assegnamento della classe dell’oggetto ritornato. Nel caso non risultassero applicate ottimizzazioni, ricorri a una delle seguenti tecniche alternative:

5.4.2. Se una variabile è dichiarata all’interno di un ciclo, e l’assegnamento ad essa costa di meno di una costruzione e una distruzione, sposta tale dichiarazione prima del ciclo.

Se la variabile è dichiarata all’interno del ciclo, l’oggetto associato ad essa viene costruito e distrutto ad ogni iterazione, mentre se è esterna tale oggetto viene costruito e distrutto una volta sola. Tuttavia, in molti casi un assegnamento costa esattamente quanto una coppia costruzione+distruzione, per cui in tali casi non ci sono vantaggi a spostare la dichiarazione all’esterno.

5.4.3. In un overload dell’operatore di assegnamento (operator=), se sei sicuro che non solleverà eccezioni, non usare la tecnica “copy&swap”, che crea una copia temporanea dell’oggetto sorgente, ma copia i singoli membri.

La tecnica più efficiente per copiare un oggetto è imitare il costruttore di copia, cioè prima copiare gli oggetti base e poi gli oggetti membro, in ordine di dichiarazione.

Tuttavia, tale tecnica non è “exception-safe”, cioè corre il rischio di non chiamare il distruttore di qualche oggetto nel caso venga sollevata un’eccezione durante la copia. Pertanto, se c’è la possibilità che durante la copia venga sollevata un’eccezione, si deve usare una tecnica “exception-safe”, che tuttavia non avrà prestazioni ottimali. La tecnica di assegnamento “exception-safe” più elegante è quella detta “copy&swap”, esemplificata dal seguente codice:

C& C::operator=(C new_value) {
    swap(new_value);
    return *this;
}

5.4.4. Definisci funzioni in overload per i tipi di argomento più comune, per evitare conversioni.

Spesso si vuole chiamare una funzione passando come argomento un'espressione che non è del tipo dell'argomento, ma può essere convertita in tale tipo.

Tale conversione, sia esplicita che implicita, crea un oggetto temporaneo.

Talvolta è possibile creare un overload della funzione originale che prende un argomento proprio del tipo corrispondente, evitando quindi la conversione.

5.5. Come ottimizzare l’uso della pipeline del processore

Le istruzioni in linguaggio macchina di salto condizionato (chiamate anche “branch”), possono essere generate dalla compilazione delle istruzioni C++ if-else, for, while, do-while, switch-case, e dell’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 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 viene eseguita quasi sempre o quasi mai; in tali casi, la predizione è quasi sempre corretta. Il caso peggiore è quello in cui l’istruzione di salto viene eseguita in modo casuale circa la metà delle volte; in tale caso la predizione è corretta mediamente solo la metà delle volte. Nelle porzioni critiche del codice, si dovrebbero eliminare le istruzioni di salto. Se un salto è predetto molto bene, si può ottenere un incremento di velocità solo sostituendolo con nessuna istruzione o con un’istruzione molto veloce. Se invece un salto è predetto molto male, si può ottenere un incremento di velocità anche sostituendolo con una serie di istruzioni piuttosto lenta. Ecco alcune tecniche per sostituire le istruzioni di salto con istruzioni equivalenti.

5.5.1. La lookup-table binaria. Invece del seguente codice, in cui c e d sono espressioni costanti e b è un’espressione booleana:
a = b ? c : d;
scrivi il seguente codice:
static const tipo lookup_table[] = { d, c };
a = lookup_table[b];

L'espressione condizionale viene compilato 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;

scrivi il seguente

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

5.5.2. Cerca di calcolare il valore di un puntatore un po’ prima di quando devi accedere all’oggetto puntato.

Per esempio, in un loop la seguente istruzione:

    a = *++p;

è meno efficiente della seguente:

    a = *p++;

in quanto nel primo caso il valore del puntatore è calcolato appena prima di accedere all’oggetto puntato, mentre nel secondo caso è calcolato nell’iterazione precedente. In un processore con pipeline, nel secondo caso si può eseguire contemporaneamente l'accesso all'oggetto puntato da p e l'incremento di p.

5.6 Come ottimizzare l’uso delle cache e della memoria virtuale

5.6.1. Dichiara vicine nella stessa unità di compilazione tutte le routine appartenenti a un collo di bottiglia.

In tal modo, il codice macchina prodotto compilando tali routine avrà indirizzi vicini, e quindi maggiore località di riferimento del codice e dei dati statici.

5.6.2. In array medi o grandi, usa le union.

Le union permettono di risparmiare memoria in strutture di tipi variabili e quindi di renderle più compatte. Non usarle in oggetti piccoli o piccolissimi, in quanto non si hanno vantaggi significativi per il risparmio di memoria, e con alcuni compilatori le variabili poste nella union non vengono tenute nei registri del processore.

5.6.3. Se un oggetto medio o grande contiene dei numeri interi con un range limitato, trasformali in bit-field.

I bit-field riducono le dimensioni dell’oggetto, e quindi permettono di far stare più oggetti nella cache dei dati e nella memoria fisica, riducendo, rispettivamente, il ricorso alla memoria principale e al disco fisso. Per esempio, per memorizzare tre numeri che possono essere compresi tra 0 e 1000, puoi usare tre campi unsigned di 10 bit ciascuno (10 + 10 + 10 = 30, 30 <= 32), mentre per memorizzare cinque numeri che possono essere compresi tra -20 e +20, puoi usare cinque campi signed di 6 bit ciascuno.

5.6.4. Nei template di classe, evita funzioni membro non banali che non dipendano da nessun parametro del template.

Piuttosto, definisci tali funzioni come non appartenenti al template e richiamale dalle funzioni membro del template. Altrimenti, il codice di tali funzioni verrà espanso ad ogni istanziazione del template, ingrandendo eccessivamente il programma.

5.7. Come sostituire operazioni elementari con altre più veloci

Alla metà degli anni '80 esistevano parecchie decine di trucchi di questo tipo. Tuttavia, in seguito, il miglioramento delle tecniche di compilazione ottimizzante ha incorporato nel compilatore molte di tali tecniche, e le ha quindi rese inutili; l'evoluzione delle architetture dei computer ha reso obsolete altri trucchi.

Pertanto qui rimangono i trucchi che possono portare dei sensibili vantaggi prestazionali sugli attuali computer e usando gli attuali compilatori.

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

Su alcuni processori, l’indirizzamento è più efficiente se la distanza dall’inizio della struttura non supera i 128 byte.

Per esempio usando seguente struttura

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

per indirizzare i campi d e i usando un puntatore all'inizio della struttura, si deve usare un offset di almeno 400 byte.

Invece, usando la seguente struttura contenente gli stessi campi in un altro ordine

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

per indirizzare i campi d e i usando un puntatore all'inizio della struttura, si può usare un offset di pochi byte, che permette l'uso di istruzioni più compatte.

Ordinando gli oggetti dal più lungo al più corto si minimizzano i buchi dovuti all’allineamento.

Per esempio, la seguente struttura

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

tipicamente occupa 1 (bool) + 7 (padding) + 8 (double) + 2 (short) + 2 (padding) + 4 (int) = 24 byte.

Invece, la seguente struttura contenente gli stessi campi in un altro ordine

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

tipicamente occupa 8 (double) + 4 (int) + 2 (short) + 1 (bool) + 1 (padding) = 16 byte.

5.7.2. Sfrutta le istruzioni assembly 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 espressione:

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

Se x è esattamente equidistante tra due interi, n sarà l’intero superiore (0.5 genera 1, 1.5 genera 2, -0.5 genera 0, -1.5 genera -1).

Purtroppo, sui processori Pentium e compatibili, tale espressione viene compilata in un codice molto lento. Usando l’istruzione fistp, si ottiene del codice molto più veloce, anche se non esattamente equivalente:

#if defined(__unix__) || defined(__GNUC__)
    // Per a Linux 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 (0.5 genera 0, 1.5 genera 2, -0.5 genera 0, -1.5 genera -2). Se questo risultato è tollerabile o addirittura desiderato, allora questo codice è consigliabile. Ovviamente non è portabile su altre famiglie di processori.

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

Una raccolta di trucchi di questo tipo si trova in http://www-graphics.stanford.edu/~seander/bithacks.html. Alcuni di questi trucchi sono in realtà già utilizzati da alcuni compilatori, altri servono per risolvere problemi particolari, altri sono utili solo su alcune piattaforme.

5.7.4. 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 non si sono vantaggi, ma alcune operazioni particolari possono risultare più veloci. Una di tali operazioni è la moltiplicazione o la divisione per una potenza di due. A tale scopo, basta aggiungere l’esponente di tale potenza all’esponente del numero a virgola mobile. Per esempio, data una variabile “f” di tipo float conforme al formato IEEE 754, e un’espressione intera positiva “n”, invece della seguente istruzione:

    f *= pow(2, n);

si può usare la seguente:

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

5.7.5. Assicurati che la dimensione (sizeof) delle celle piccole o medie degli array sia una potenza di due, e che la dimensione delle celle grandi degli array 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 è una potenza di due, tale moltiplicazione è molto più rapida, in quanto si realizza con 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. Per esempio, se ogni cella è una terna di valori float, si aggiunga a ogni cella un quarto valore float “dummy”.

Tuttavia, nell’accedere alle celle di un array multidimensionale in cui l’ultima dimensione è una potenza di 2 abbastanza grande, si può cadere nel fenomeno della contesa per la cache dei dati (data cache contention), che può rallentare l’elaborazione fino a più di 10 volte. Il fenomeno si verifica solo quando le righe dell’array superano una certa dimensione, che dipende dal sistema, ma che orientativamente è dai 1024 ai 8192 byte. Pertanto, nel caso in cui un algoritmo deve elaborare un array la cui dimensione è o potrebbe essere una potenza di 2 maggiore o uguale a 256, in primo luogo si deve scoprire se si ha la contesa per la cache, e in caso affermativo evitare tale fenomeno.

Per scoprire l’esistenza della contesa per la cache, basta aggiungere una cella a ogni riga dell’array, 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:

5.7.6. Se non usi le opzioni di ottimizzazione dell’intero programma e di espansione inline di qualunque funzione che il compilatore ritenga opportuno, prova a spostare nelle intestazioni e dichiarare inline le funzioni chiamate dai colli di bottiglia.

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

Prova a mettere inline un paio di funzioni per volta, fin tanto che si ottengono miglioramenti significativi della velocità.

5.7.7. 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.

5.7.8. 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, sia quando c è una potenza di due, sia 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 è solo una reinterpretazione degli stessi bit. Pertanto, se  s è un intero signed che sai che è sicuramente positivo o nullo, ne velocizzi la divisione se usi le seguenti espressioni equivalenti: unsigned(s) / c e unsigned(s) % c.


© Carlo Milanesi - Ultimo aggiornamento: 11 maggio 2008