Effetto del caching sulle prestazioni del programma

Cache ti permette di "ingannare" un algoritmo nella sua forma pura e basta cercare un valore invece di calcolarlo. Ci sono meno istruzioni da eseguire e quindi il caching accelera le prestazioni.

link

Il caching è un argomento molto ampio, ma alla fine l'obiettivo è lo stesso: migliorare le prestazioni e ridurre il carico di operazioni di I / O, CPU o memoria intensiva. Se puoi approfondire su quale tipo di 'cache algoritmica' ti riferisci, possiamo rispondere in modo più specifico.

Esempi di tipi di memorizzazione nella cache:

In un'applicazione:

• Memorizzazione nella cache dei dati - ad es. valori di cache, entità, grafici ecc. senza dover tornare al database, disco per recuperare i dati.
• Caching della pagina (app Web): la memorizzazione nella cache di tutto o solo parte di una pagina Web significa che il server non ha bisogno di eseguire nuovamente il rendering della pagina.

Specifici per il Web, cache del browser e dispositivi di caching della rete come proxy, salva il carico su un server interamente, con file statici come .js, .css, immagini, ecc.

E a livello hardware:

• I compilatori possono usare i registri per memorizzare la memoria
• Le CPU hanno cache per risparmiare tempo recuperando dati dalla RAM (ad esempio cache L1 e L2)

Il caching è una tecnica che sfrutta i dati della distanza lontano dal richiedente. In una moderna architettura del sistema informatico ci sono diversi livelli di livelli di dati. Tutti questi livelli appaiono a distanze diverse dal richiedente (la CPU).

Solitamente accade che i livelli di dati più vicini abbiano un costo maggiore per gigabyte. Un costo per gigabyte più alto significa che c'è quasi sempre meno spazio disponibile in un livello dati più vicino rispetto a un ulteriore livello dati. Questa differenza nello spazio è il motivo per cui impieghiamo tecniche di memorizzazione nella cache nei nostri sistemi informatici e nel nostro software. Tecniche che tentano di avvicinare gli elementi richiesti più probabilmente al richiedente e di rimuovere gli elementi obsoleti in modo che la memoria cache non sia esaurita.

Per sfruttare le cache, devi essere a conoscenza di due termini: località spaziale e località temporale .

Località spaziale è un termine usato con sistemi di indirizzamento come la memoria del computer. Le moderne cache dei processori trascinano i dati in blocchi di memoria adiacente (memoria "vicina" a un'altra). Gli algoritmi possono trarre vantaggio da ciò accedendo alla memoria in modo sequenziale in indirizzi che differiscono per unità piccole (1 è ottimale). Un esempio di buona localizzazione spaziale è il seguente:

int sum = 0;
int[] array = { /* Some massive array with data */ };

for (int i = 0; i < ARRAY_SIZE; i++) {
    sum += array[i]; // Access elements with an address difference of 1.
}

Località temporale è un termine usato per descrivere l'utilizzo di qualcosa nella cache di frequente. L'uso di un elemento della cache (ad esempio una variabile) genera sempre meno recuperi da un livello dati più lontano. Gli algoritmi possono sfruttare la località temporale riutilizzando frequentemente le variabili. Un esempio di buona localizzazione temporale è il seguente:

int sum = 0;

for (int i = 0; i < 32; i++) {
    sum += i; // Frequent access of variables sum and i.
}

Vale la pena di controllare questo link per vedere le differenze in tempo di luoghi comuni in cui i dati vengono memorizzati nel calcolo.

Esistono davvero due diverse definizioni di memorizzazione nella cache. Il primo è ciò che fa il sistema operativo, spostando blocchi di memoria che sono lenti ad accedere a blocchi che sono molto più veloci da accedere. Se scrivi il tuo algoritmo per sfruttare questo tipo di memorizzazione nella cache, il tuo programma funzionerà più velocemente, a volte molto più velocemente, ma la complessità algoritmica rimane O (n ³ ).

A volte quando la gente dice di fare il caching, significa memoization . Ciò significa che esegui il calcolo nel modo più difficile la prima volta, ma lo memorizzi in memoria per la seconda e le successive volte che ne hai bisogno. Effettivamente, la prima volta che lo esegui per dati dati, il tuo algoritmo è O (n ³ ), ma dopo questo è O (1).

Il caching è un semplice compromesso. Si risparmia il tempo necessario per calcolare un risultato a spese di dover allocare memoria per una tabella di ricerca che contiene tutti i risultati di cui si ha probabilmente bisogno. Se il trade off vale o meno dipende da quanto sia costoso il calcolo del risultato e dalla quantità di memoria consumata da una tabella di ricerca con tutti i risultati di cui si ha probabilmente bisogno.

EDIT: Ovviamente stavo parlando di tabelle di ricerca piuttosto che di caching puro, mentre sono concetti strettamente correlati che non sono esattamente la stessa cosa. Calcola che il caffè del mattino non sia ancora in pieno effetto.

Il caching non sta solo calcolando un risultato, ma lo sta anche archiviando in una tabella di ricerca per uso futuro, quindi una richiesta successiva per lo stesso valore restituisce la versione cache invece di eseguire nuovamente il calcolo. Le tabelle di ricerca precomputerano una vasta raccolta di valori o li carica da un file di dati e li inserisce in una tabella di ricerca prima che vengano mai effettuate chiamate al metodo. il primo si tradurrà in metodi che sono più lenti da eseguire la prima volta, ma che sono più veloci nelle chiamate successive, ma che causano un aumento costante dell'utilizzo della memoria. Quest'ultimo significa pagare un grosso costo nel calcolare tutti i valori in anticipo e allocare una grande porzione di memoria per la tabella di ricerca, ma paga sempre ottenendo risultati sempre veloci quando il metodo viene effettivamente chiamato e l'uso costante della memoria.

I processori moderni hanno molte funzionalità di caching che hanno lo scopo di migliorare le prestazioni di programmi "normali" come questo. Se vuoi studiare l'effetto di questa memorizzazione nella cache, puoi impostare la creazione di un programma anomalo che calcoli lo stesso risultato.

Ad esempio, invece di passare in rassegna gli indici degli array in serie, analizzarli in ordine pseudo-casuale. (ci vorrà un po 'di tempo per farlo senza un sacco di spese generali, ma il modo semplice è di allocare una tabella di permutazione delle stesse dimensioni dell'array).

Un altro esempio che può fornire un momento "aha" è di srotolare il ciclo interno. A un certo livello, srotolando il ciclo inizieremo a produrre risultati peggiori .

Quando è attivo qualsiasi tipo di memorizzazione nella cache, c'è una performance "best case" con risultati del 100% e prestazioni "worst case" con risultati dello 0%. Uno schema ben progettato con un programma adatto si avvicina alle migliori prestazioni del caso. La differenza tra i casi migliori e i peggiori può essere enorme, 10x, anche 100x.

Sfortunatamente, non esiste una garanzia o una formula semplice che garantisca l'efficacia delle cache. Un piccolo cambiamento nelle dimensioni di un programma, o la dimensione del suo set di dati, può portare a cambiamenti enormi e in gran parte misteriosi nelle prestazioni.