Ottimizzare C++/Tecniche generali di ottimizzazione/Caching: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Aggiungo: en:Optimizing C++/General optimization techniques/Memoization |
Revisionato |
||
Riga 1:
{{Ottimizzare C++}}
Le tecniche di ''caching'' (chiamate anche tecniche di [[w:Memoizzazione|''memoizzazione'']]) si basano sul principio che se una funzione pura ossia una funzione [[w:Trasparenza referenziale|''referenzialmente trasparente'']] (cioè una [[w:Funzione (matematica)|funzione matematica]]) deve essere calcolata più volte per lo stesso argomento, e se tale calcolo richiede parecchio tempo, si risparmia tempo salvando il risultato la prima volta che lo si
=== ''Look-up table'' ===
'''Se devi calcolare spesso una funzione pura avente come dominio un piccolo intervallo di numeri interi, pre-calcola (in fase di sviluppo del software o in fase di inizializzazione
L'accesso a un array, soprattutto se si trova nella cache dei dati del processore, è molto veloce. Pertanto, se la look-up table non è grande, quasi sicuramente è più veloce della funzione che si deve calcolare.▼
Per esempio, dovendo calcolare la radice quadrata di un numero intero compreso tra 0 e 9, conviene usare la seguente funzione:
Line 22 ⟶ 20:
</source>
▲L'accesso a un array è molto veloce, soprattutto se la cella a cui si accede si trova nella cache dei dati del processore
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.▼
Se la ''look-up table'' risulta piuttosto grande, può non essere più conveniente, sia per l'impiego di memoria, sia per il tempo necessario a pre-calcolare tutti i valori, ma soprattutto per il fatto che non può essere contenuta nella cache dei dati del processore.
▲Se però la funzione da calcolare è
=== Caching a un posto ===
'''Se devi
▲Per esempio, invece di scrivere:
<source lang=cpp>
double f(double x, double y) {
Line 35 ⟶ 38:
</source>
<source lang=cpp>
Line 52 ⟶ 55:
</source>
Nota che, per avere un vantaggio prestazionale, non è necessario che la funzione sia chiamata con gli stessi argomenti per tutta l'esecuzione del programma.
È invece sufficiente che sia chiamata alcune volte con gli stessi argomenti, poi altre volte con altri argomenti, e così via. In tale caso, il calcolo viene effettuato solo Ovviamente, invece di migliorare le prestazioni, questa soluzione le peggiora nel caso in cui la funzione è chiamata con argomenti variabili
Nota che
Se questa routine deve poter essere chiamata contemporaneamente da più thread, è necessario sostituire le variabili statiche con variabili [[w:en:Thread-local_storage|distinte per ogni thread]]. 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 che non
* Aggiungere un flag statico che indica se le variabili statiche hanno valori validi, e controllare tale flag ad ogni chiamata.
=== Caching a N posti ===
'''Se devi
Ecco un esempio, in cui la mappa è implementata con un array, riferito alla stessa funzione della linea-guida "Caching a un posto" in questa sezione:
<source lang=cpp>
Line 92 ⟶ 99:
</source>
Alcune funzioni, pur avendo un dominio teoricamente grande, sono chiamate frequentemente con pochi valori distinti.
Anche per questo caso valgono le considerazioni riguardanti le variabili statiche, fatte al punto precedente ("Caching a un posto").▼
Per esempio, un word processor può avere installato un grande numero di tipi di caratteri (detti anche ''font''), ma in un tipico documento vengono usati solo pochissimi font.
Una funzione che deve manipolare il font di ogni carattere del documento verrà chiamata tipicamente con pochissimi valori diversi.
In tali casi, invece di una cache a un solo posto, risulta preferibile una cache a più posti, come quella dell'esempio.
▲Anche per questo caso valgono le considerazioni riguardanti le variabili statiche, fatte
Per cache piccole (come quella di soli 8 posti dell'esempio), l'algoritmo più efficiente è la scansione sequenziale su un array.
Inoltre, nell'esempio la cache ha dimensione fissa, ma potrebbe essere opportuno avere invece una cache di dimensioni variabili.
Solitamente, l'ultimo elemento letto è il più probabile per la chiamata successiva. Quindi, come nell'esempio, può essere opportuno salvare la sua posizione e far partire la ricerca da tale posizione.
Se la cache non si espande indefinitamente, c'è il problema di quale elemento rimpiazzare.
Ovviamente è meglio rimpiazzare l'elemento che è meno probabile che sia richiesto dalla chiamata successiva.
Nell'esempio si assume che tra gli elementi presenti nella cache, l'elemento inserito per primo sia il meno probabile.
▲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, un albero di ricerca o una hashtable sarebbero più efficienti.
Pertanto, le scritture scorrono ciclicamente l'array.
Spesso un criterio migliore consiste nel sostituire l'elemento non letto da più tempo.
Per attuare questo criterio, si deve usare un algoritmo un po' più complesso.
[[Categoria:Ottimizzare C++|Caching]]
| |||