Implementazione LRU nel codice di produzione

Question

Ho un codice C++ dove devo implementare la sostituzione della cache usando la tecnica LRU.
Finora so due metodi per implementare LRU sostituzione della cache:

1. Utilizzando timestamp per ogni volta che i dati memorizzati nella cache si accede e, infine, confrontando i timestamp al momento della sostituzione.
2. Utilizzando una pila di elementi memorizzati nella cache e spostandoli verso l'alto se sono accessibili di recente, così alla fine il fondo conterrà la candidata LRU.

Quindi, quale di questi è meglio utilizzare nel codice di produzione?
I loro altri metodi migliori?

Answer 1

Recentemente ho implementato una cache LRU utilizzando un elenco collegato su una mappa hash.

/// Typedef for URL/Entry pair 
    typedef std::pair< std::string, Entry > EntryPair; 

    /// Typedef for Cache list 
    typedef std::list<EntryPair> CacheList; 

    /// Typedef for URL-indexed map into the CacheList 
    typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap; 

    /// Cache LRU list 
    CacheList mCacheList; 

    /// Cache map into the list 
    CacheMap mCacheMap; 

Ha il vantaggio di essere O (1) per tutte le operazioni importanti.

L'algoritmo di inserimento:

// create new entry 
Entry iEntry(...); 

// push it to the front; 
mCacheList.push_front(std::make_pair(aURL, iEntry)); 

// add it to the cache map 
mCacheMap[ aURL ] = mCacheList.begin(); 

// increase count of entries 
mEntries++; 

// check if it's time to remove the last element 
if (mEntries > mMaxEntries) 
{ 
    // erease from the map the last cache list element 
    mCacheMap.erase(mCacheList.back().first); 

    // erase it from the list 
    mCacheList.pop_back(); 

    // decrease count 
    mEntries--; 
} 

Answer 2

Nel nostro ambiente di produzione usiamo C++ elenco doppia linked che è simile al Linux kernel linked list. Il bello è che puoi aggiungere un oggetto a tutti gli elenchi collegati che desideri e l'operazione di elenco è veloce e semplice.

Answer 3

Per semplicità, forse dovresti prendere in considerazione l'utilizzo della mappa MultiIndex di Boost. Se separiamo la chiave dai dati, supportiamo più set di chiavi sugli stessi dati.

Da [http://old.nabble.com/realization-of-Last-Recently-Used-cache-with-boost%3A%3Amulti_index-td22326432.html]:

" ... usare due indici: 1) per la ricerca di hashing valore tasto 2) per il monitoraggio sequenziale articoli ultima usati di recente (ottenere funzione di mettere elemento come ultimo elemento in sequesnce Se. dobbiamo rimuovere alcuni elementi dalla cache, potremmo eliminarli dall'inizio della sequenza). "

Si noti che l'operatore "progetto" "consente al programmatore di spostarsi tra diversi indici dello stesso multi_index_container" in modo efficiente.

Answer 4

Questo article descrive l'implementazione utilizzando una coppia di contenitori STL (una mappa valore-chiave più un elenco per la cronologia di accesso chiave) o un singolo boost::bimap.

Answer 5

Ecco una semplice implementazione di cache di LRU

https://github.com/lamerman/cpp-lru-cache.

È facile da usare e capire come funziona. La dimensione totale del codice è di circa 50 righe.