Ottimizzare C++/Tecniche generali di ottimizzazione/Caching

Copertina Ottimizzare C++/Copertina

Le tecniche di caching (chiamate anche tecniche di memoizzazione) si basano sul principio che se una funzione pura ossia una funzione referenzialmente trasparente (cioè una 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 calcola, e recuperando il valore salvato le volte successive.

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 dell'applicazione) tutti i valori della funzione per ogni valore del dominio, e ponili in un array statico, detto lookup-table. Quando devi calcolare il valore della funzione per un dato valore del dominio, preleva l'elemento corrispondente di tale array.

Per esempio, dovendo calcolare la radice quadrata di un numero intero compreso tra 0 e 9, conviene 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];
}

L'accesso a un array è molto veloce, soprattutto se la cella a cui si accede si trova nella cache dei dati del processore. Pertanto, se la look-up table non è grande, quasi sicuramente il suo accesso è più veloce della funzione che si deve calcolare.

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 è molto lenta, è chiamata molte volte, e le si può dedicare molta memoria, può essere opportuno usare una look-up table grande decine o centinaia di KB. Tuttavia, raramente è opportuno superare un megabyte.

Caching a un posto

Se devi chiamare spesso una funzione pura con gli stessi argomenti, la prima volta che tale funzione viene chiamata salva gli argomenti e il risultato in variabili statiche; quando la funzione viene chiamata ancora, confronta i nuovi argomenti con quelli vecchi; se coincidono, rendi il risultato memorizzato, altrimenti calcola il risultato e memorizza i nuovi argomenti e il nuovo risultato.

Per esempio, invece della seguente funzione:

double f(double x, double y) {
    return sqrt(x * x + y * y);
}

puoi scrivere la seguente funzione:

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;
}

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 quando gli argomenti cambiano.

Ovviamente, invece di migliorare le prestazioni, questa soluzione le peggiora nel caso in cui la funzione è chiamata con argomenti variabili quasi sempre, oppure se il confronto tra gli argomenti nuovi e quelli vecchi richiede più tempo del calcolo della funzione stessa.

Nota che a causa dell'uso di variabili statiche la routine non è più thread-safe, e non può essere ricorsiva. Se questa routine deve poter essere chiamata contemporaneamente da più thread, è necessario sostituire le variabili statiche con variabili 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 saranno mai passati come argomenti.
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 chiamare molte volte una funzione pura passando argomenti che nella maggior parte dei casi appartengono a un piccolo dominio, usa una mappa (detta anche dizionario) statica, inizialmente vuota. Quando la funzione viene chiamata, cerca l'argomento nella mappa. Se lo trovi, rendi il valore associato, altrimenti calcola il risultato e inserisci nella mappa la coppia argomento-risultato.

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:

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 = 0;
    static int last_written_i = 0;
    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;
}

Alcune funzioni, pur avendo un dominio teoricamente grande, sono chiamate frequentemente con pochi valori distinti.

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 nella linea-guida "Caching a un posto" in questa sezione.

Per cache piccole (come quella di soli 8 posti dell'esempio), 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.

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. 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.