Differenze tra le versioni di "Ottimizzare C++/Tecniche generali di ottimizzazione"

(Ampliata notevolmente la tecnica dei memory-mapped-files)
== Caching ==
 
Le tecniche di ''caching'' (in inglese chiamate anche tecniche di ''memoization'') si basano sul principio che se una funzione pura (ocioè una funzione matematica) deve essere calcolata più volte per unlo datostesso argomento, e se tale calcolo richiede parecchio tempo, si risparmia tempo salvando il risultato la prima volta che si esegue la funzione, e ritornandorecuperando il valore salvato le volte successive.
 
=== ''Look-up table'' ===
=== Se devi calcolare spesso una funzione avente come dominio un piccolo intervallo di numeri interi, pre-calcola (in fase di sviluppo del software o in fase di inizializzazione dell’applicazione) tutti i valori della funzione per ogni valore del dominio e ponili in un array statico, detto “lookup-table”. Quando dovrai calcolare il valore della funzione per un dato valore del dominio, preleva l’elemento corrispondente dell’array. ===
 
=== '''Se devi calcolare spesso una funzione avente come dominio un piccolo intervallo di numeri interi, pre-calcola (in fase di sviluppo del software o in fase di inizializzazione dell’applicazione) tutti i valori della funzione per ogni valore del dominio e ponili in un array statico, detto “lookup"lookup-table”table". Quando dovraidevi calcolare il valore della funzione per un dato valore del dominio, preleva l’elementol'elemento corrispondente dell’array.di ===tale array.'''
 
L’accessoL'accesso a un array, soprattutto se si trova nella cache dei dati del processore, è molto veloce. Per esempioPertanto, dovendo calcolarese la radicelook-up quadratatable dinon unè numerogrande, interoquasi compresosicuramente traè 0più eveloce 9,della sifunzione puòche usaresi ladeve seguente funzione:calcolare.
 
Per esempio, dovendo calcolare la radice quadrata di un numero intero compreso tra 0 e 9, conviene usare la seguente funzione:
 
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:
<source lang=cpp>
double sqrt10(int i) {
}
</source>
 
=== Se devi calcolare spesso una funzione con gli stessi argomenti, salva in variabili statiche gli argomenti e il risultato. Quando devi calcolare la funzione, confronta i nuovi argomenti con quelli vecchi. Se coincidono, rendi il risultato memorizzato, altrimenti calcola il risultato e memorizza nelle variabili statiche gli argomenti e il risultato. ===
Se la funzione da calcolare è piuttosto lenta, e si ha a disposizione molta memoria, può essere opportuno usare una look-up table anche se risulta piuttosto grande. Tuttavia, raramente è opportuno definire una look-up table più grande di un megabyte.
 
=== Caching a un posto ===
 
=== '''Se devi calcolare spesso una funzione con gli stessi argomenti, salva in variabili statiche gli argomenti e il risultato. Quando devi calcolare la funzione, confronta i nuovi argomenti con quelli vecchi. Se coincidono, rendi il risultato memorizzato, altrimenti calcola il risultato e memorizza nelle variabili statiche gli argomenti e il risultato. ==='''
 
Per esempio, invece di scrivere:
}
</source>
 
puoipuò convenire scrivere:
 
<source lang=cpp>
double f(double x, double y) {
}
</source>
Nota 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.
 
Nota che, per avere un vantaggio prestazionale, non è necessario che la funzione sia chiamata con gli stessi parametriargomenti per tutta l’esecuzionel'esecuzione del programma. È invece sufficiente che sia chiamata alcune volte con gli stessi parametriargomenti, poi altre volte con altri parametriargomenti, e così via. In tale caso, il calcolo viene effettuato solo al cambiamento deidegli parametriargomenti.
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.
 
Ovviamente, questainvece soluzionedi peggioramigliorare le prestazioni, invecequesta disoluzione migliorarle,le peggiora nel caso in cui la funzione è chiamata con parametriargomenti variabili molto spesso, ooppure se il confronto tra igli parametriargomenti nuovi e quelli vecchi richiede più tempo del calcolo della funzione stessa.
Questo algoritmo è detto anche "caching a un posto", in quanto si memorizza solo una coppia argomento-risultato.
 
Nota che l’usol'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.
=== Se devi calcolare spesso una funzione avente un dominio limitato, usa una mappa inizialmente vuota. Quando devi calcolare la funzione, cerca l’argomento nella mappa. Se lo trovi, rendi il valore associato, altrimenti calcola il risultato e inserisci nella mappa la coppia argomento-risultato. ===
 
Nota anche che nell'esempio si assume che la funzione valga zero quando gli argomenti sono entrambi zero. In caso contrario, si dovrebbe adottare un'altra soluzione, come una delle seguenti:
* Inizializzare la variabile ''result'' al valore corrispondente ad argomenti tutti a valore zero.
* Inizializzare le variabili ''prev_x'' e ''prev_y'' a valori non validi come argomenti.
* Aggiungere un flag che indica se le variabili statiche hanno valori validi, e controllare tale flag.
 
=== Caching a N posti ===
 
=== '''Se devi calcolare spesso una funzione avente un dominio limitato, usa una mappa (o dizionario) inizialmente vuota. Quando devi calcolare la funzione, cerca l’argomento nella mappa. Se lo trovi, rendi il valore associato, altrimenti calcola il risultato e inserisci nella mappa la coppia argomento-risultato. ==='''
 
In alcuni casi, la funzione viene chiamata con parametri variabili, ma appartenenti a un insieme molto limitato. In tale caso si può implementare una cache a più posti, invece di unadella cache a un singolo posto, come quella appena vista. Ecco un esempio, riferito alla stessa funzione di sopra:
 
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:
<source lang=cpp>
double f(double x, double y) {
double x; double y; double result;
} cache[n_buckets];
static int last_read_i = 0;
static int last_written_i = 0;
int i = last_read_i;
do {
}
</source>
Nota 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.
 
Anche per questo caso valgono le considerazioni riguardanti le variabili statiche, fatte al punto precedente ("Caching a un posto").
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.
 
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 sarebbero più efficienti.
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.
 
SiLa notiricerca infine,nella che la ricercacache parte sempre dall’ultimodall'ultimo elemento letto, chein quanto solitamente è il più probabile,. e laLa scrittura innella cache di un elemento non presente sovrascrive l’elementol'elemento successivo all’ultimoall'ultimo elemento scritto, cioè si sostituisce l’elementol'elemento meno recentemente ''scritto'. UnSi avrebbe un algoritmo migliore sarebbesostituendo sostituire l’elementol'elemento meno recentemente ''letto'', ma ciò richiederebbe che si prendaprendesse nota dei tempidell'ordine di accesso.
Questo algoritmo è detto anche "caching a N posti".
 
== Altre tecniche ==
323

contributi