c++ - aviation - lru cache

Implementación de LRU en código de producción.

Question

Tengo algún código C ++ donde necesito implementar el reemplazo de caché usando la técnica LRU.
Hasta ahora conozco dos métodos para implementar el reemplazo de caché LRU:

1. Utilizando timeStamp para cada vez que se accede a los datos almacenados en caché y finalmente comparando los timeStamps en el momento del reemplazo.
2. Usar una pila de elementos almacenados en caché y moverlos a la parte superior si se accede recientemente, por lo que finalmente la parte inferior contendrá el Candidato LRU.

Entonces, ¿cuál de estos es mejor usar en el código de producción?
¿Hay otros métodos mejores?

Answer 1

Aquí está una implementación muy simple de caché LRU

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

Es fácil de usar y entender cómo funciona. El tamaño total del código es de aproximadamente 50 líneas.

Answer 2

En nuestro entorno de producción, utilizamos una lista de enlaces dobles de C ++ que es similar a la lista de enlaces del kernel de Linux . La belleza de esto es que puede agregar un objeto a tantas listas vinculadas como desee y la operación de la lista es rápida y simple.

Answer 3

Este article describe la implementación utilizando un par de contenedores STL (un mapa clave-valor más una lista para el historial de acceso clave), o un solo boost::bimap .

Answer 4

Para simplificar, tal vez debería considerar el uso del mapa MultiIndex de Boost. Si separamos la clave de los datos, admitimos varios conjuntos de claves en los mismos datos.

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

"... use dos índices: 1) hash para buscar el valor por clave 2) secuencial para rastrear los últimos elementos utilizados recientemente (obtener el elemento de función get como último elemento en secuencia). Si necesitamos eliminar algunos elementos del caché, podemos eliminarlos desde el comienzo de la secuencia).

Tenga en cuenta que el "operador" del proyecto "permite al programador moverse entre diferentes índices del mismo multi_index_container" de manera eficiente.

Answer 5

Recientemente implementé un caché LRU utilizando una lista enlazada extendida sobre un mapa 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;

Tiene la ventaja de ser O (1) para todas las operaciones importantes.

El algoritmo de inserción:

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