Algoritmo di sostituzione della cache più efficiente [chiuso]

Credo che la risposta migliore sia che dipende. Nella mia esperienza ci sono molti fattori che vanno nella scelta degli algoritmi di cache.

Fattori da considerare

1. Bilancio di lettura / scrittura. (Quale percentuale di accessi sono letti rispetto alle scritture)
2. Quantità di cache.
3. Tipo di supporto dietro la cache. (Sono unità SATA lente o unità SSD veloci?)
4. Hits vs Misses. (Quanto spesso le cose vengono riscritte o rilette?)
5. Dimensioni di accesso medie (Questo va a scegliere la dimensione della pagina)
6. Quanto costose sono le letture e le scritture.

Dopo aver considerato tutti i diversi fattori, è necessario trovare un algoritmo di cache che gestisca al meglio. Ad esempio, diciamo che hai un'applicazione in cui ci sono molte scritture, alcune riscritture, letture di dati scritti di recente e qualche tipo di media girevole. In questo caso vorresti una sorta di algoritmo di caching ibrido. Per gestire i dati di scrittura potresti volere qualcosa come Wise order of Writes (WOW) e un algoritmo LRU per i dati letti dal disco. La ragione di ciò è che gli accessi al disco sono molto costosi e l'algoritmo WOW renderà più efficiente scrivere i dati e l'LRU manterrà i dati frequentemente utilizzati sempre nella cache.

Supponiamo che tu disponga di dischi SSD, che hanno un tempo di accesso molto veloce, potresti decidere di orientare la tua scelta verso l'algoritmo LRU dato che gli accessi al disco sono relativamente poco costosi.

Quindi davvero quello che voglio dire è che non esiste una risposta "migliore". La risposta migliore è conoscere i fattori che si applicano a te e scegliere un algoritmo che li gestisca al meglio.

Come trovare l'algoritmo per te

Verifica il tuo sistema. Questo di solito comporta l'aggiunta di codice per mantenere le statistiche per gli accessi alla memoria. Con il profiling puoi vedere quali fattori sono più importanti per te.

In passato ho aggiunto del codice per tenere traccia di tutti gli accessi alla memoria per un periodo di tempo. Poi più tardi cerco modelli. Cerco rilette, ri-scrive, accesso sequenziale, accesso casuale, ecc.

Una volta identificate le cose importanti, è necessario esaminare tutti i diversi tipi di algoritmi di caching per vedere quale gestire quali sono le cose migliori.

Supponendo che tu non sappia quasi nulla sull'applicazione che svilupperai, dovresti saperne di più a riguardo prima di scegliere e implementare un sistema di cache. In altre parole, non ci sono implementazioni predefinite: alcune sono buone per alcuni scopi e sono totalmente negative per gli altri .

Ad esempio, prendi solo due implementazioni: Least Used Used e Least Frequently Used. Come decidere quale usare prima di un altro?

• LRU è buono quando sei abbastanza sicuro che l'utente accederà più spesso agli elementi più recenti e non ritorni mai o quasi mai ai vecchi. Un esempio: un uso generale di un client di posta elettronica. Nella maggior parte dei casi, gli utenti accedono costantemente alle e-mail più recenti. Li legge, li posticipa, ritorna in pochi minuti, ore o giorni, ecc. Possono ritrovarsi a cercare una mail ricevuta due anni fa, ma succede meno frequentemente dell'accesso alle mail ricevute nelle ultime due ore.

• D'altra parte, LRU non ha senso nel contesto in cui l'utente accederà ad alcuni elementi molto più frequentemente di altri. Un esempio: ascolto spesso la musica che mi piace, e può capitare che su 400 canzoni, ascolto gli stessi cinque almeno una volta alla settimana, mentre ascolterò al più una volta all'anno 100 canzoni che non mi piacciono troppo tanto. In questo caso, LFU è molto più appropriato.

Prendendo solo due delle implementazioni, vedi che non esiste un algoritmo "predefinito" che puoi usare quando non vuoi pensare a quale è meglio o non hai abbastanza informazioni sull'applicazione. È, beh, come chiedere se per impostazione predefinita, devi aggiungere, sottrarre, moltiplicare o dividere due numeri per trovare un risultato di un calcolo quando non ne sai nulla.

Perché limitare le tue scelte solo a Wikipedia? Se hai accesso a un database di ricerca come ACM Digital Library troverai ancora più algoritmi. Anche essere consapevoli di scherzare con i brevetti. Ad esempio ARC è un buon algoritmo ma sfortunatamente è brevettato.

Potresti passare molto tempo ad agonizzare il "migliore" algoritmo, oppure potresti semplicemente implementare un semplice algoritmo e OTTENERE CON IL RESTO DEL SISTEMA. Quando hai qualcosa di testabile, preoccupati dell'algoritmo.

Ottimizzazione prematura ...

Non esiste un algoritmo di cache perfetto: puoi sempre trovare un caso che si comporta molto male.

Pertanto è importante conoscere il problema di essere memorizzati nella cache al fine di determinare quello che si comporterà meno male.

Inoltre, dovresti considerare quanto tempo hai bisogno di memorizzare nella cache le cose e per quanto tempo puoi memorizzare nella cache le cose ...