Ottimizzare C++/Tecniche generali di ottimizzazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Ampliata notevolmente la tecnica dei memory-mapped-files |
|||
Riga 144:
== Caching ==
Le tecniche di ''caching'' (in inglese chiamate anche tecniche di ''memoization'') si basano sul principio che se una funzione pura (
=== ''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. ===▼
▲
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) {
Line 159 ⟶ 164:
}
</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 ===
▲
Per esempio, invece di scrivere:
Line 167 ⟶ 177:
}
</source>
<source lang=cpp>
double f(double x, double y) {
Line 182 ⟶ 194:
}
</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
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,
Nota che
=== 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 ===
▲
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
▲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) {
Line 197 ⟶ 218:
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 {
Line 213 ⟶ 234:
}
</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.
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,
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.▼
▲
== Altre tecniche ==
|