C'è una teoria unificata di caching? Cioè, collezioni di teoremi e algoritmi per la costruzione di cache e/o ottimizzazione per loro?Teoria di caching
La domanda è volutamente ampia, perché i risultati che sto cercando sono anche ampia. Formule per la massima velocità raggiungibile, metriche per gli algoritmi di caching, cose del genere. Un libro di testo universitario sarebbe probabilmente l'ideale.
Se si può supporre che un colpo di cache sia molto più veloce di un errore di cache, si scoprirà che il lavoro straordinario, anche se si hanno solo errori di cache, l'uso di una cache sarà altrettanto veloce o più veloce di non usare una cache.
Vedi di seguito per la matematica:
Number of hits = NumRequests - #CacheMisses
AverageTime = ((NumRequests-#CacheMisses) * TimePerHit + #CacheMisses * TimePerMiss)/NumRequests
Se poi assumiamo che NumRequests è infinito (questo è un problema limite, non temono il calcolo), possiamo vedere questo:
AverageTime = Infinity*TimePerHit/Infinity - #CacheMisses*TimePerHit/Infinity + #CacheMisses*TimePerMiss/Infinity
Entrambi i termini con i #CacheMisses va a zero, ma l'intera equazione risolve a:
AverageTime = TimePerHit
concesso tale è per quando il numero di richieste è infinito, ma puoi vedere come questo acceleri facilmente il tuo sistema usando una cache.
La stragrande maggioranza di caching del mondo reale coinvolge sfruttando il "80-20 regola" o Pareto distribution. Vedi sotto per come appare
Ciò si manifesta in applicazioni come:
Quindi, direi che la "teoria del caching" è quello di utilizzare fino a pochi risorse aggiuntive che sono generalmente "raro", ma "veloce" per compensare le cose ripetute più attivi si farai.
Il motivo per fare questo è quello di cercare di "livellare" il numero di volte in cui si fa l'operazione "lento", basato sul grafico altamente distorta sopra.
Ho parlato con uno dei professori della mia scuola, che mi ha indicato verso online algorithms, che sembra essere l'argomento che sto cercando.
C'è una grande quantità di sovrapposizione tra algoritmi di caching e algoritmi di sostituzione delle pagine. Probabilmente modificherò le pagine di WikiPedia per questi argomenti per chiarire la connessione, una volta che ho ho imparato di più sull'argomento.
Il tuo calcolo sembra molto buono. Sfortunatamente implica il presupposto che il numero di errori di cache sia costante, il che sembra altamente improbabile. Il numero corretto sarebbe: HitProbability * TimePerHit + (1 - HitProbability) * TimePerMiss –
So che la matematica è un po 'incerta; questa è una prova che ho dovuto imparare per una lezione che ho fatto lo scorso autunno e ho cercato di richiamarla da lì. Affrontare il tuo punto però, dal momento che ho CacheHits vs CacheMisses, questo è un rapporto, quindi non sarebbe la stessa cosa di usare una probabilità di successo? – samoz
Non proprio. Supponendo che ci sia una probabilità costante e non zero di errori di cache, ci saranno infiniti errori se si eseguono prove infinite. La tua formula sarebbe corretta se la cache fosse abbastanza grande da contenere tutti i dati che verranno mai richiesti. Poi c'è un limite superiore costante al numero di miss. –