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.
Lo sviluppo di un’applicazione efficiente procede nel seguente modo:
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”).
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 bool, double, 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.
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.
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.
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.
Un enumerato è implementato come un intero. Tipicamente, rispetto ad un intero, una stringa occupa più spazio, ed è più lenta da copiare e da confrontare.
I compilatori possono sfruttare la regolarità di tale istruzione per applicare alcune ottimizzazioni, in particolare se viene applicata la linea-guida 3.1.11.
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.
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.
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.
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.
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.
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:
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.
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.
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);
}
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.
Se è stata creata una tale funzione membro, è solo perché è più efficiente dell'algoritmo STL generico.
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.
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.
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.
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.
In altre parole, dichiara static tutte le funzioni membro che puoi.
In questo modo, non viene passato l’argomento implicito this.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Gli algoritmi di STL passano tali oggetti per valore. Pertanto, se la loro copia non è estremamente efficiente, gli algoritmi STL diventano lenti.
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.
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.
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.
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.
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;
}
}
}
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.
In tal modo, il codice macchina prodotto compilando tali routine e i dati statici a cui accederà avranno indirizzi vicini tra loro.
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.
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.
Le tecniche per rendere thread-safe una libreria possono dover usare memoria e tempo. Se non usi i thread, evita di pagarne il costo.
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.
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.
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.
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.
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.
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à.
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.
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];
}
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.
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".
Il confronto tra stringhe case-insensitive costa di più del confronto case-sensitive.
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.
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.
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.
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.
In STL c'è l'algoritmo partition, che è più veloce dell'algoritmo sort, in quanto ha complessità O(N).
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.
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).
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.
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.
È 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.
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.
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.
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.
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;
Tale operatore può richiedere un tempo superiore a quello richiesto da una semplice chiamata a funzione.
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”.
Alcuni compilatori utilizzano tale informazione per ottimizzare la contabilità necessaria per gestire le eventuali eccezioni.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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:
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.
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;
}
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.
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.
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];
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
}
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:
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à.
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.
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.