LRU aplicación en código de producción

Question

Tengo algo de código C ++ donde tengo que poner en práctica la sustitución caché utilizando la técnica LRU.
Hasta ahora Sé dos métodos para implementar el reemplazo de caché LRU:

1. Uso de marca de tiempo para cada vez que se accede a los datos en caché y, finalmente, la comparación de las marcas de tiempo en el momento de reemplazo.
2. Uso de una pila de artículos almacenados en caché y moverlos a la parte superior si se accede a ellos recientemente, por lo que finalmente la parte inferior contendrá el Candidato LRU.

Así que, ¿cuál de ellos es mejor para ser utilizado en el código de producción?
Son sus otros métodos mejores?

Answer 1

Recientemente he implementado un caché LRU utilizando una lista de difusión vinculados 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--;
}

Answer 2

Aquí es una aplicación muy sencilla 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 3

Para simplificar, tal vez usted debería considerar el uso de un mapa MultiIndex de Boost. Si separamos la clave de los datos, apoyamos varios conjuntos de teclas en los mismos datos.

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

" ... el uso de dos índices: 1) algoritmo hash para buscar valor) secuencial tecla 2 para el seguimiento de los elementos menos utilizados recientemente (función Get elemento puesto como último elemento de sequesnce Si tenemos que eliminar algunos elementos de la memoria caché, nosotros también. puede eliminar que comenzará a partir de la secuencia) ".

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

Answer 4

Esta artículo describe la implementación usando un par de contenedores STL (un mapa clave-valor plus una lista para la historia clave de acceso), o una sola boost::bimap.

Answer 5

En nuestro entorno de producción se utiliza un C ++ lista doblemente enlazada, que es similar a la Linux kernel vinculado lista . La belleza de esto es que se puede añadir un objeto a la mayor cantidad de listas enlazadas como desee y operación de la lista es rápido y sencillo.