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

Tengo un código C++ en el que necesito implementar el reemplazo de caché mediante la técnica LRU.
Hasta ahora sé dos métodos para implementar LRU reemplazo de caché:Implementación de LRU en el código de producción

El 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 la sustitución.
Usando una pila de elementos almacenados en la memoria caché y moviéndolos a la parte superior si se accede recientemente, finalmente la parte inferior contendrá el LRU Candidato.

Entonces, ¿cuál de estos es mejor usar en el código de producción?
¿Hay algún otro método mejor?

Fuente

2010-01-13 sud03r

Qué quiere decir con "mejor" - tiene que especificar cuáles son sus criterios. Además, eche un vistazo a esta pregunta http://stackoverflow.com/questions/1935777/c-design-how-to-cache-most-recent-used –

En lugar de timestamp, puede usar enteros para realizar un seguimiento. Cuando se accede a un elemento, hazlo 0 e incrementa otras pistas – user

@usuario que sería un diseño deficiente porque haría que el costo de acceso sea 'O (n)' – Alnitak

Recientemente implementé una memoria caché LRU utilizando una lista vinculada distribuida en 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--; 
}

Fuente

2010-01-13 14:50:47

También he implementado el almacenamiento en memoria caché de LRU y utilizo una técnica similar. Una búsqueda ya no es constante, por supuesto, ya que cambia el estado, por lo que en un entorno de múltiples subprocesos se necesitan bloqueos exclusivos para cada acceso, incluso para varios lectores. – CashCow

¿por qué es esta una respuesta válida? considere, usted el tamaño de la memoria caché es de 5 elementos. Y la corriente de entradas es 1,2,3,4,5. en este punto, la lista enlazada tendría este orden 5-> 4-> 3-> 2-> 1. Ahora cuando se inserta un nuevo elemento que ya existe, diga '1', luego la lista se convierte en 1 -> 5-> 4-> 3-> 2-> 1. Y el Hash (clave = 1) se sobrescribe y los puntos al comienzo de la lista. Como la memoria caché tiene un límite superior, eliminará el elemento Hash (clave = 1) y saldrá de la lista. Por lo tanto, la lista será 1 -> 5 -> 4-> 3-> 2 pero el Hash contendrá solo 4 elementos – blueskin

Lo que este código falta es, al insertar, si se inserta un elemento existente, entonces la aparición previa de ese debería se eliminará de la lista y del hash antes de insertar – blueskin

En nuestro entorno de producción utilizamos un C++ lista doblemente enlazada que es similar a la Linux kernel linked list. La belleza de esto es que puede agregar un objeto a tantas listas enlazadas como desee y la operación de lista es rápida y simple.

Fuente

2010-01-13 17:49:02 grokus

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

Desde [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é, podemos eliminarlos desde el comienzo de la secuencia). "

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

Fuente

2010-07-20 02:36:39

Vea también un ejemplo en la documentación de boost :: multi_index: http://www.boost.org/doc/libs/1_45_0/libs/multi_index/doc/examples.html#example9 –

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

Fuente

2010-11-26 14:27:55 timday

Gracias; arreglado. – timday

link is dead? – Gregory

@Gregory: bitbucket parece haber cambiado algo sobre el alojamiento estático de un repositorio. Puede encontrar el documento en https://bitbucket.org/timday/timday.bitbucket.org/src/, pero deberá descargarlo (y el css que lo acompaña) o el pdf. Veremos si se puede hacer algo ... – timday

Aquí es una aplicación muy sencilla de caché LRU

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

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

Fuente

2013-06-21 06:45:42

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

Respuesta

Cuestiones relacionadas