LRU implementação em código de produção

Question

Eu tenho algumas código C++ que eu preciso para implementar cache de substituição usando LRU técnica.
Tão longe eu sei que dois métodos para implementar cache LRU substituição:

1. Utilizando o carimbo de data / hora por cada vez que o cache de dados é acessado e, finalmente, comparando os carimbos de data / hora no momento da substituição.
2. Usando uma pilha de itens armazenados em cache e movendo-os para cima, se eles são acessados recentemente, então, finalmente, o fundo irá conter o LRU Candidato.

Então, qual desses é melhor para ser usado na produção de código?
São de sua quaisquer outros métodos mais?

Answer 1

Recentemente implementei uma cache LRU usando uma lista ligada distribuídos ao longo de uma hash do mapa.

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

Ele tem a vantagem de ser O(1) para todas as operações importantes.

O algoritmo de inserção:

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

Aqui é muito simples implementação de cache LRU

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

É fácil de usar e entender como funciona.O tamanho total do código é de cerca de 50 linhas.

Answer 3

Para manter a simplicidade, talvez você deve considerar usando o Impulso do MultiIndex mapa.Se estamos separados a chave de dados, suporte a vários conjuntos de chaves na mesma data.

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

"...o uso de dois índices:1) hash para pesquisa de valor de chave 2) seqüencial para o rastreamento de última itens usados recentemente (obter a função de colocar o item como último item em sequesnce.Se for necessário remover alguns itens do cache, podemos excluir que a partir do início da sequência)."

Observe que o "projeto" operador "permite que o programador para mover-se entre diferentes índices do mesmo multi_index_container" de forma eficiente.

Answer 4

Este artigo descreve a implementação usando um par de contentores STL (um valor-chave do mapa, além de uma lista para a chave de acesso história), ou um único boost::bimap.

Answer 5

Em nosso ambiente de produção podemos usar um C++ duplo lista ligada que é semelhante ao Linux kernel da lista ligada.A beleza da coisa é que você pode adicionar um objeto como muitas listas ligadas como você deseja e lista operação é rápida e simples.