|
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.
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.
== Come ridurre le operazioni di allocazione e deallocazione ==
* [[Ottimizzare C++/Ottimizzazione del codice C++/Allocazione e deallocazione|Allocazione e deallocazione]]
=== La funzione <code>alloca</code> ===
* [[Ottimizzare C++/Ottimizzazione del codice C++/Supporto run-time|Supporto run-time]]
* [[Ottimizzare C++/Ottimizzazione del codice C++/Numero di istruzioni|Numero di istruzioni]]
'''In funzioni non-ricorsive, per allocare spazio di dimensione variabile ma non grande, usa la funzione <code>alloca</code>.'''
* [[Ottimizzare C++/Ottimizzazione del codice C++/Costruzioni e distruzioni|Costruzioni e distruzioni]]
* [[Ottimizzare C++/Ottimizzazione del codice C++/Pipeline|Pipeline]]
È molto efficiente, in quanto alloca spazio sullo stack.
* [[Ottimizzare C++/Ottimizzazione del codice C++/Accesso alla memoria|Accesso alla memoria]]
* [[Ottimizzare C++/Ottimizzazione del codice C++/Operazioni veloci|Operazioni veloci]]
È 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.
Tuttavia, è 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 resource leak.
=== Spostare le allocazioni e le deallocazioni ===
'''Sposta prima dei colli di bottiglia le allocazioni di memoria, e dopo i colli di bottiglia le corrispondenti deallocazioni.'''
La gestione di memoria dinamica di dimensione variabile è molto più lenta della gestione della memoria sullo stack.
Analoga ottimizzazione va fatta per le operazioni che provocano allocazioni indirettamente, come la copia di oggetti che, direttamente o indirettamente, possiedono memoria dinamica.
=== La funzione <code>reserve</code> ===
'''Prima di aggiungere elementi a oggetti <code>vector</code> o <code>string</code>, chiama <code>reserve</code> con una dimensione sufficiente per la maggior parte dei casi.'''
Se si aggiungono ripetutamente elementi a oggetti <code>vector</code> o <code>string</code>, ogni tanto viene eseguita una costosa operazione di riallocazione del contenuto.
Per evitare tali costose riallocazioni, basta allocare inizialmente lo spazio che probabilmente sarà sufficiente.
=== Mantenere la capacità dei <code>vector</code> ===
'''Per svuotare un oggetto <code>vector<T> x</code> senza deallocarne la memoria, usa l'istruzione <code>x.resize(0);</code>; per svuotarlo deallocandone la memoria, usa l'istruzione <code>vector<T>().swap(x);</code>.'''
Per svuotare un oggetto <code>vector</code>, esiste anche l'istruzione <code>clear()</code>; tuttavia lo standard non specifica se tale istruzione conserva la capacità (capacity) del <code>vector</code> oppure no.
Se questa istruzione deve essere eseguita spesso, e si vuole essere sicuri di evitare frequenti riallocazioni, si deve chiamare la funzione <code>resize</code>, 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' di tempo tale oggetto non verrà più usato, oppure verrà usato con un numero molto più piccolo di elementi, si deve chiamare la funzione <code>swap</code> su un nuovo oggetto temporaneo vuoto.
=== Ridefinire la funzione <code>swap</code> ===
'''Per ogni classe concreta <code>T</code> che, direttamente o indirettamente, possiede della memoria dinamica, ridefinisci le appropriate funzioni <code>swap</code>.'''
In particolare, aggiungi alla classe una funzione membro <code>public</code> con la seguente firma:
<source lang=cpp>void swap(T&) throw();</source>
e aggiungi la seguente funzione non-membro nello stesso namespace che contiene la classe <code>T</code>:
<source lang=cpp>void swap(T& lhs, T& rhs) { lhs.swap(rhs); }</source>
e, se la classe non è un template di classe, aggiungi la seguente funzione non-membro nello stesso file in cui è dichiarata la classe <code>T</code>:
<source lang=cpp>namespace std { template<> swap(T& lhs, T& rhs) { lhs.swap(rhs); } }</source>
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 <code>swap</code>, viene usata l'implementazione generica.
L'implementazione generica di <code>swap</code> 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 di memoria dinamica citato nella linea-guida può essere anche solo 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. Quindi anche in tali casi si devono ridefinire le funzioni <code>swap</code>.
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 devono ridefinire funzioni <code>swap</code>.
Se la classe è astratta, la funzione <code>swap</code> non dovrebbe mai essere chiamata sugli oggetti di tale tipo, e quindi anche in questo caso non si devono ridefinire funzioni <code>swap</code>.
Per velocizzare la funzione <code>swap</code>, 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 <code>std::swap</code>, la funzione deve iniziare con la seguente istruzione:
<source lang=cpp>using std::swap;</source>
== Come ridurre i costrutti che richiamano routine del supporto run-time ==
=== L'operatore <code>typeid</code> ===
'''Invece di usare l'operatore <code>typeid</code>, usa una funzione <code>virtual</code>.'''
Tale operatore può richiedere un tempo superiore a quello richiesto da una semplice chiamata a funzione.
=== L'operatore <code>dynamic_cast</code> ===
'''Invece dell'operatore <code>dynamic_cast</code>, usa l'operatore <code>typeid</code>, o, ancora meglio, una funzione <code>virtual</code>.'''
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 <code>typeid</code>.
=== La specifica di eccezioni vuota ===
'''Usa la specifica di eccezioni vuota (cioè aggiungi <code>throw()</code> 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.
=== Il costrutto <code>try/catch</code> ===
'''Sposta prima dei colli di bottiglia le istruzioni <code>try</code>, e dopo i colli di bottiglia le corrispondenti istruzioni <code>catch</code>.'''
L’esecuzione di un blocco <code>try/catch</code> talvolta ha costo zero, ma altre volte comporta un rallentamento. Evita di eseguire tale blocco all’interno dei colli di bottiglia.
=== Operazioni a virgola mobile ===
'''Se il processore target non contiene un'unità a virgola mobile, sostituisci funzioni, costanti e variabili a virgola mobile con le corrispondenti funzioni, costanti e variabili intere; mentre se contiene un'unità a virgola mobile a precisione solamente singola, sostituisci funzioni, costanti e variabili di tipo <code>double</code> con le corrispondenti di tipo <code>float</code>.'''
Gli odierni processori per sistemi desktop e server contengono hardware dedicato all'aritmetica a virgola mobile, sia a precisione singola che doppia, per cui tali operazioni, eccettuate somme e sottrazioni, che sono un po' più lente, 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, o contengono hardware in grado di gestire solo la precisione singola.
Pertanto, in tali sistemi, le operazioni non disponibili in hardware vengono solamente emulate con lentissime funzioni di libreria. In tal caso, risulta molto più veloce utilizzare l'aritmetica intera, oppure, se disponibile in hardware, l'aritmetica a precisione singola.
Per gestire numeri decimali usando l'aritmetica a intera si deve usare gli interi intendendoli moltiplicati per un fattore di scala.
Ogni numero viene moltiplicato per tale fattore in fase di input e viene diviso per lo stesso fattore in fase di output, o viceversa.
=== Conversioni da numero a stringa ===
'''Usa funzioni ottimizzate per convertire numeri in stringa.'''
Le funzioni standard di conversione da numero intero a stringa e da numero a virgola mobile a stringa sono poco efficienti.
Per svolgere velocemente tali operazioni, usa funzioni non-standard, eventualmente scritte da te.
== Come diminuire il numero di istruzioni eseguite ==
=== Verifica di intervallo ===
'''Per controllare se un numero intero <code>i</code> è compreso tra <code>min_i</code> e <code>max_i</code>, estremi inclusi, usa l'espressione <code>unsigned(i – min_i) <= unsigned(max_i – min_i)</code>.'''
La suddetta formula è equivalente alla seguente formula, più intuitiva:
<source lang=cpp>min_i <= i && i <= max_i</source>
Quest'ultima formula richiede due confronti, mentre quella suggerita ne richiede uno solo.
In particolare, per controllare che un numero <code>i</code> sia valido come indice per accedere a un array di <code>size</code> elementi, si può usare la seguente espressione:
<source lang=cpp>unsigned(i) < unsigned(size)</source>
Se le espressioni utilizzate sono già di un tipo <code>unsigned</code>, le conversioni non sono necessarie.
=== Ordine dei casi di istruzioni <code>switch</code> ===
'''Nelle istruzioni <code>switch</code>, 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.
=== Parametri interi di template ===
'''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 la seguente funzione di libreria, in cui sia x che y non hanno un valore definito in fase di sviluppo della libreria:
<source lang=cpp>int f1(int x, int y) { return x * y; }</source>
Tale funzione può essere chiamata dal seguente codice applicativo, nel quale x non ha un valore costante, ma y è la costante 4:
<source lang=cpp>int a = f1(b, 4);</source>
Se mentre scrivi la libreria sai che il chiamante ti passerà sicuramente una costante intera come argomento y, puoi trasformare la funzione nel seguente template di funzione:
<source lang=cpp>template <int Y> int f2(int x) { return x * Y; }</source>
Tale funzione può essere chiamata dal seguente codice applicativo:
<source lang=cpp>int a = f2<4>(b);</source>
Tale chiamata istanzia automaticamente la seguente funzione:
<source lang=cpp>int f2(int x) { return x * 4; }</source>
Questa funzione è più veloce della precedente istanza di ''f1'', per i seguenti motivi:
* Viene passato un solo parametro alla funzione (''x'') invece di due (''x'' e ''y'').
* La divisione per una costante intera (''4'') è più veloce della divisione per una variabile intera (''y'').
* Dato che il valore costante (''4'') è una potenza di due, il compilatore, invece di eseguire una moltiplicazione intera, esegue uno scorrimento di bit.
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.
Se invece di avere una funzione avevi già un template di funzione, basta aggiungere un ulteriore parametro a tale template.
=== Il ''Curiously Recurring Template Pattern'' ===
'''Se devi scrivere una classe base astratta di libreria tale che in ogni algoritmo nel codice 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:
<source lang=cpp>
class Base {
public:
virtual void f() = 0;
void g() { f(); }
};
</source>
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:
<source lang=cpp>
class Derivata1: public Base {
public:
virtual void f() { ... }
};
...
Base* p1 = new Derivata1;
p1->g();
</source>
In tal caso, è possibile convertire il precedente codice di libreria nel seguente:
<source lang=cpp>
template <class Derivata> class Base {
public:
void f() { static_cast<Derivata*>(this)->f(); }
void g() { f(); }
};
</source>
Il codice applicativo, di conseguenza, diventerà il seguente:
<source lang=cpp>
class Derivata1: public Base<Derivata1> {
public:
void f() { ... }
};
...
Derivata1* p1 = new Derivata1;
p1->g();
</source>
In tal modo, si ha binding statico della funzione membro <code>Derivata1::f</code> alla funzione membro <code>Base<Derivata1>::g</code>, cioè la chiamata a tale funzione non è di tipo <code>virtual</code>.
Tuttavia, con questa soluzione, se si volesse aggiungere la seguente definizione
<source lang=cpp>
class Derivata1: public Base<Derivata1> {
public:
void f() { ... }
};
</source>
non risulterebbe possibile definire un puntatore o riferimento a una classe base comune a <code>Derivata1</code> e <code>Derivata2</code>, in quanto tali classi risultano due tipi senza alcuna relazione; quindi questa soluzione non è adatta se si vuole permettere al codice applicativo di definire un contenitore di oggetti derivati da Base.
Altre limitazioni sono le seguenti:
* <code>Base</code> è necessariamente un tipo astratto;
* un oggetto di tipo </code>Derivata1</code> non può essere convertito in un oggetto di tipo <code>Derivata2</code> o viceversa;
* per ogni derivazione di <code>Base</code> tutto il codice di <code>Base</code> viene duplicato.
=== Il pattern ''Strategy'' ===
'''Se un oggetto che implementa il pattern ''Strategy'' (noto anche come ''Policy'') è una costante in ogni algoritmo nel codice applicativo, ma il codice di libreria deve poter gestire più strategie, elimina tale oggetto, rendi <code>static</code> tutti i suoi membri, e aggiungi tale classe come parametro di template.'''
Supponi che stai scrivendo il seguente codice di libreria, che implementa il design pattern ''Strategy'':
<source lang=cpp>
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_;
};
</source>
Questo codice di libreria ha lo scopo di consentire il seguente codice applicativo:
<source lang=cpp>
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.
</source>
In tal caso, è possibile convertire il precedente codice di libreria nel seguente:
<source lang=cpp>
template <class Strategy>
class C {
public:
void f() { if (Strategy::is_valid(*this)) Strategy::run(*this); }
};
</source>
Il codice applicativo, di conseguenza, diventerà il seguente:
<source lang=cpp>
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.
</source>
In tal modo, si evita l'oggetto-strategia, e si ha il binding statico delle funzioni membro <code>MyStrategy::is_valid</code> e <code>MyStrategy::run</code>, cioè si evitano chiamate a funzioni <code>virtual</code>.
Tuttavia, tale soluzione non consente di decidere la strategia in fase di esecuzione, e tanto meno di cambiarla durante la vita dell'oggetto, e, inoltre, duplica il codice della strategia per ogni istanziazione di tale classe.
=== Operatori bit-a-bit ===
'''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.
== 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.
=== Valore di ritorno di funzioni ===
'''Per le funzioni che non siano espanse ''inline'', cerca di dichiarare il tipo di ritorno <code>void</code> o <code>bool</code> 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 <code>return</code>.'''
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 del 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 <code>return</code>, 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:
* Rendi la funzione <code>void</code>, e aggiungile un argomento passato per riferimento, che funge da valore di ritorno.
* Trasforma la funzione in un costruttore del tipo ritornato, che riceve gli stessi parametri della funzione.
* Fai in modo che la funzione restituisca un oggetto di un tipo ausiliario che ruba le risorse e le cede all'oggetto destinazione, senza copiarle.
* Usa un ''rvalue reference'', introdotto dallo standard C++0x.
* Usa un ''expression template''.
=== Spostamento di variabili all'esterno di cicli ===
'''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.
=== Operatore di assegnamento ===
'''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:
<source lang=cpp>
C& C::operator=(C new_value) {
swap(new_value);
return *this;
}
</source>
=== Overload per evitare conversioni ===
'''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.
== 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++ <code>if-else</code>, <code>for</code>, <code>while</code>, <code>do-while</code>, <code>switch-case</code>, e dell'operatore di espressione condizionale (<code>?:</code>).
I moderni processori elaborano efficientemente i salti condizionati solo se riescono a prevederli.
In caso di errore di previsione, il lavoro che hanno già incominciato a fare, caricando nella pipeline le istruzioni successive, risulta inutile e devono ripartire dall'istruzione di destinazione del salto.
La predizione del salto si basa sulle iterazioni precedenti.
Se queste sono regolari, il salto viene predetto correttamente.
I casi migliori sono quelli in cui un'istruzione di salto 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 difficilmente predicibili.
Se un salto è predetto molto male, anche sostituendolo con una serie di istruzioni piuttosto lenta si può ottenere un incremento di velocità.
Ecco alcune tecniche per sostituire le istruzioni di salto con istruzioni equivalenti.
=== La ''look-up table'' binaria. ===
'''Invece di un'espressione condizionale con entrambi i casi costanti, usa una ''look-up table'' a due valori.'''
Ossia, se ha del codice come il seguente, in cui ''c'' e ''d'' rappresentano espressioni costanti e ''b'' rappresenta un'espressione booleana:
<source lang=cpp>
a = b ? c : d;
</source>
Sostituiscilo con il seguente codice:
<source lang=cpp>
static const tipo lookup_table[] = { d, c };
a = lookup_table[b];
</source>
L'espressione condizionale viene compilata in un salto condizionato.
Se tale salto non è predetto bene, costa di più della lookup-table.
Ovviamente questa tecnica può essere estesa a cascate di espressioni condizionali. Per esempio, invece del seguente codice:
<source lang=cpp>
a = b1 ? c : b2 ? d : b3 ? e : f;
</source>
puoi scrivere il seguente:
<source lang=cpp>
static const tipo lookup_table[] = { e, f, d, d, c, c, c, c };
a = lookup_table[b1 * 4 + b2 * 2 + b3];
</source>
=== Anticipazione del calcolo degli indirizzi ===
'''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:
<source lang=cpp>a = *++p;</source>
è meno efficiente della seguente:
<source lang=cpp>a = *p++;</source>
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.
== Come ottimizzare l’uso delle cache e della memoria virtuale ==
=== Avvicinare il codice ===
'''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.
Analogo effetto si ha per i dati statici dichiarati in tale codice.
=== Le <code>union</code> ===
'''In array medi o grandi, usa le <code>union</code>.'''
Le <code>union</code> 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'' ===
'''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 un bit e tre numeri che possono essere compresi tra 0 e 1000, puoi usare un campo <code>unsigned</code> di un bit e tre campi <code>unsigned</code> di 10 bit ciascuno (1 + 10 + 10 + 10 = 31, 31 <= 32), mentre per memorizzare cinque numeri che possono essere compresi tra -20 e +20, puoi usare cinque campi ''signed'' di 6 bit ciascuno.
=== Codice di template non dipendente dai parametri ===
'''Nei template di classe, evita funzioni membro non banali che non dipendano da nessun parametro del template.'''
Tutto il codice di una funzione di un template viene espanso ad ogni istanziazione distinta di tale funzione.
Se una porzione di codice non dipende dai parametri del template, ad ogni istanziazione del template verrà generato sempre lo stesso codice.
Tale replicazione di codice ingrandisce inutilmente il programma.
Per evitare tale replicazione di codice, definisci tali funzioni come non appartenenti al template, e richiamale dalle funzioni membro del template.
Una funzione di grande dimensione potrebbe avere una grande porzione che non dipende da nessun parametro del template di classe o del template di funzione.
In tal caso, in primo luogo scorpora tale porzione di codice come una funzione distinta, e poi applica questa linea-guida.
== 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.
=== Ordinamento dei campi di strutture ===
'''Disponi le variabili membro di classi e strutture in modo che le variabili più usate siano nei primi 128 byte, e 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, si deve usare un offset di almeno 400 byte per indirizzare i campi ''d'' e ''i'' usando un puntatore all'inizio della struttura:
<source lang=cpp>
struct {
char c[400];
double d;
int i;
};
</source>
Invece, usando la seguente struttura, contenente gli stessi campi in un altro ordine, 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:
<source lang=cpp>
struct {
double d;
int i;
char c[400];
};
</source>
Ordinando gli oggetti dal più lungo al più corto si minimizzano i buchi dovuti all’allineamento.
Per esempio, la seguente struttura tipicamente occupa 1 (bool) + 7 (padding) + 8 (double) + 2 (short) + 2 (padding) + 4 (int) = 24 byte:
<source lang=cpp>
struct {
bool b;
double d;
short s;
int i;
};
</source>
Invece, la seguente struttura, contenente gli stessi campi in un altro ordine, tipicamente occupa 8 (double) + 4 (int) + 2 (short) + 1 (bool) + 1 (padding) = 16 byte:
<source lang=cpp>
struct {
double d;
int i;
short s;
bool b;
};
</source>
=== Conversione da numero a virgola mobile a numero intero ===
'''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:
<source lang=cpp>
n = int(floor(x + 0.5f));
</source>
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:
<source lang=cpp>
#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
</source>
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.
=== Manipolazione dei bit di numeri interi ===
'''Manipola i bit dei numeri interi sfruttando la conoscenza del formato di rappresentazione.'''
Una raccolta di trucchi di questo tipo si trova 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.
=== Manipolazione dei bit di numeri a virgola mobile ===
'''Manipola i bit dei numeri a virgola mobile, dopo averli reinterpretati come numeri interi, sfruttando la conoscenza del formato di rappresentazione.'''
Per le operazioni più comuni 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:
<source lang=cpp>
f *= pow(2, n);
</source>
si può usare il seguente codice:
<source lang=cpp>
if (*(int*)&f & 0x7FFFFFFF) { // se f==0 non fare niente
*(int*)&f += n << 23; // aggiungi n all’esponente
}
</source>
=== Dimensione delle celle di array ===
'''Assicurati che la dimensione (sizeof) delle celle non grandi degli array e dei ''vector'' sia una potenza di due, e che la dimensione delle celle grandi degli array e dei ''vector'' non sia una potenza di due.'''
L'accesso diretto alla cella di un array viene fatto moltiplicando l'indice per la dimensione di ogni cella, che è una costante.
Se il secondo fattore è 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:
* Aggiungere una o alcune celle inutilizzate alla fine di ogni riga. Per esempio l’array ''double a[100][1024]'' potrebbe essere trasformato in ''double a[100][1026]'', anche se nel codice si terrà conto che la dimensione utile rimane 100x1024.
* Lasciare le dimensioni appropriate dell’array, ma suddividere le matrici in blocchi rettangolari, ed elaborare tutte le celle di ogni blocco prima di passare al blocco successivo.
=== Espansione ''inline'' ===
'''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à.
=== Operazioni con potenze di due ===
'''Se devi scegliere una costante intera per cui devi moltiplicare o dividere spesso, scegli una potenza di due.'''
Le operazioni di moltiplicazione, divisione e modulo tra numeri interi sono molto più veloci se il secondo operando è una potenza di due costante, in quanto in tal caso vengono implementate come scorrimenti di bit o mascherature di bit.
=== Divisione intera per costanti ===
'''Se un numero intero <code>signed</code> è sicuramente non-negativo, quando lo dividi per una costante, convertilo in <code>unsigned</code>.
Se <code>s</code> è un intero <code>signed</code>, <code>u</code> è un intero <code>unsigned</code>, e <code>c</code> è un'espressione costante intera (positiva o negativa), l'operazione <code>s / c</code> è più lenta di <code>u / c</code> e l'operazione <code>s % c</code> è più lenta di <code>u % c</code>, sia quando <code>c</code> è 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 <code>signed</code> a <code>unsigned</code> non costa niente, in quanto si tratta solo di una reinterpretazione degli stessi bit.
Pertanto, se <code>s</code> è un intero con segno, che sai essere sicuramente positivo o nullo, ne velocizzi la divisione se usi le seguenti espressioni equivalenti: <code>unsigned(s) / c</code> e <code>unsigned(s) % c</code>.
=== Processori con bus dati ridotto ===
'''Se il processore target ha il bus dati più piccolo dei registri interni, usa i tipi interi più piccoli possibili per tutte le variabili eccetto i parametri di funzione e le variabili locali.'''
I tipi <code>int</code> e <code>unsigned int</code> sono quelli più efficienti una volta caricati nei registri del processore.
Tuttavia, su alcune famiglie di processori, potrebbero non essere i più efficienti da accedere in memoria.
Per esempio, esistono processori che hanno registri da 16 bit, ma bus dati da 8 bit.
Per i processori che hanno il bus dati più piccolo dei registri interni, solitamente i tipi <code>int</code> e <code>unsigned int</code> corrispondono alla dimensione dei registri interni.
Per tali sistemi, la lettura e la scrittura in memoria di un oggetto di tipo <code>int</code> richiedono un tempo più grande di quello che sarebbe richiesto da un tipo intero più piccolo.
I parametri di funzione e le variabili locali sono solitamente allocate in registri, e quindi non richiedono accessi in memoria.
[[Categoria:Ottimizzare C++|Ottimizzazione]]
| 