Como posso fazer minha simples cache do .NET LRU mais rápido?

Question

UPDATE: Ei, obrigado pelas respostas. Ontem à noite e hoje à noite eu tentei algumas abordagens diferentes e veio com um semelhante ao estabelecido abaixo por Jeff (eu mesmo já tinha feito o que ele sugeriu em sua atualização, e montar minha própria implementação simples LL para ganhos adicionais). Aqui está o código, neste momento não parece particularily limpa mais, mas eu tenho sido sobre isso várias vezes mudando tudo o que podia para reforçar o desempenho.

public class NewLRU2<K, V> where V : class
{
    int m_iMaxItems;
    Dictionary<K, LRUNode<K, V>> m_oMainDict;

    private LRUNode<K,V> m_oHead;
    private LRUNode<K,V> m_oTail;
    private LRUNode<K,V> m_oCurrent;

    public NewLRU2(int iSize)
    {
        m_iMaxItems = iSize;
        m_oMainDict = new Dictionary<K, LRUNode<K,V>>();

        m_oHead = null;
        m_oTail = null;
    }

    public V this[K key]
    {
        get
        {
            m_oCurrent = m_oMainDict[key];

            if (m_oCurrent == m_oHead)
            {
                //do nothing
            }
            else if (m_oCurrent == m_oTail)
            {
                m_oTail = m_oCurrent.Next;
                m_oTail.Prev = null;

                m_oHead.Next = m_oCurrent;
                m_oCurrent.Prev = m_oHead;
                m_oCurrent.Next = null;
                m_oHead = m_oCurrent;
            }
            else
            {
                m_oCurrent.Prev.Next = m_oCurrent.Next;
                m_oCurrent.Next.Prev = m_oCurrent.Prev;

                m_oHead.Next = m_oCurrent;
                m_oCurrent.Prev = m_oHead;
                m_oCurrent.Next = null;
                m_oHead = m_oCurrent;
            }

            return m_oCurrent.Value;
        }
    }

    public void Add(K key, V value)
    {
        if (m_oMainDict.Count >= m_iMaxItems)
        {   
            //remove old
            m_oMainDict.Remove(m_oTail.Key);

            //reuse old
            LRUNode<K, V> oNewNode = m_oTail;
            oNewNode.Key = key;
            oNewNode.Value = value;

            m_oTail = m_oTail.Next;
            m_oTail.Prev = null;

            //add new
            m_oHead.Next = oNewNode;
            oNewNode.Prev = m_oHead;
            oNewNode.Next = null;
            m_oHead = oNewNode;
            m_oMainDict.Add(key, oNewNode);
        }
        else
        {
            LRUNode<K, V> oNewNode = new LRUNode<K, V>(key, value);
            if (m_oHead == null)
            {
                m_oHead = oNewNode;
                m_oTail = oNewNode;
            }
            else
            {
                m_oHead.Next = oNewNode;
                oNewNode.Prev = m_oHead;
                m_oHead = oNewNode;
            }
            m_oMainDict.Add(key, oNewNode);
        }
    }

    public bool Contains(K key)
    {
        return m_oMainDict.ContainsKey(key);
    }
}


internal class LRUNode<K,V>
{
    public LRUNode(K key, V val)
    {
        Key = key;
        Value = val;
    }

    public K Key;
    public V Value;
    public LRUNode<K, V> Next;
    public LRUNode<K, V> Prev;
}

Há algumas partes que olhar / sentir vacilante - como reutilizar o nó antigo ao fazer um add - mas eu era capaz de obter um impulso apreciável em porformance fora delas. Eu também estava um pouco surpreso com a diferença que fez para mudar de propriedades reais no nó de variáveis ??apenas públicos, mas acho que é assim que se passa com este material. Neste ponto, o código acima é quase inteiramente pelas operações de dicionário limita-performance, então eu não tenho certeza se eu ia ficar muito mais fora de triturar-lo ao redor. Eu vou continuar a pensar sobre isso e olhar para algumas das respostas.

Explicação Do Original Post: Olá a todos. Então eu escrevi uma implementação LRU leve simples para uso em uma biblioteca de compressão (estou usando-o para encontrar correspondência byte-strings na entrada com base em um hash, LZW-style), e eu estou procurando maneiras de fazer -lo mais rápido.

Answer 1

update # 2

Isso reduz a necessidade de lista de travessia em uma lista Remove ligados. Introduz um LruCacheNode que tem tanto a chave e o valor. A chave é usada apenas quando você aparar o cache. Você poderia obter um melhor desempenho se você escreveu sua própria implementação lista ligada onde cada nó é essencialmente um LruCacheNode juntamente com uma referência Avançar e Voltar. Esta é uma espécie do que um LinkedHashMap não (ver estes duas perguntas ) .

public class LruCache<K, V>
{
    private readonly int m_iMaxItems;
    private readonly Dictionary<K, LinkedListNode<LruCacheNode<K, V>>> m_oMainDict;
    private readonly LinkedList<LruCacheNode<K, V>> m_oMainList;

    public LruCache(int iSize)
    {
        m_iMaxItems = iSize;
        m_oMainDict = new Dictionary<K, LinkedListNode<LruCacheNode<K, V>>>();
        m_oMainList = new LinkedList<LruCacheNode<K, V>>();
    }

    public V this[K key]
    {
        get
        {
            return BumpToFront(key).Value;
        }
        set
        {
            BumpToFront(key).Value = value;
        }
    }

    public void Add(K key, V value)
    {
        LinkedListNode<LruCacheNode<K, V>> newNode = m_oMainList.AddFirst(new LruCacheNode<K, V>(key, value));
        m_oMainDict.Add(key, newNode);

        if (m_oMainList.Count > m_iMaxItems)
        {
            m_oMainDict.Remove(m_oMainList.Last.Value.Key);
            m_oMainList.RemoveLast();
        }
    }

    private LruCacheNode<K, V> BumpToFront(K key)
    {
        LinkedListNode<LruCacheNode<K, V>> node = m_oMainDict[key];
        if (m_oMainList.First != node)
        {
            m_oMainList.Remove(node);
            m_oMainList.AddFirst(node);
        }
        return node.Value;
    }

    public bool Contains(K key)
    {
        return m_oMainDict.ContainsKey(key);
    }
}

internal sealed class LruCacheNode<K, V>
{
    private readonly K m_Key;
    private V m_Value;

    public LruCacheNode(K key, V value)
    {
        m_Key = key;
        m_Value = value;
    }

    public K Key
    {
        get { return m_Key; }
    }

    public V Value
    {
        get { return m_Value; }
        set { m_Value = value; }
    }
}

Você vai ter ao perfil coisas para ver se esta é uma melhoria no seu ambiente.

Minor Update:. Eu atualizei BumpToFront para verificar para ver se o nó já está na frente por comentário de Tim Stewart

Answer 2

Não é o ponto de um cache LRU para permitir que você cortar o cache e jogar fora o material menos usados ??recentemente? :-) Eu não vejo qualquer código para aparar o cache. Desde que você provavelmente quer alto desempenho para a recuperação de caso de uso, e o caso de uso de guarnição é menos importante porque não descarregar a manutenção lista para o processo de aparar?

IOW, apenas jogar as entradas no cache, mas timestamp-los na recuperação. Não reordenar as entradas, basta marcá-los sempre que eles são usados. Poderia ser um verdadeiro timestamp DateTime, ou poderia ser um contador simples na classe, maior número foi utilizado mais recentemente. Em seguida, no processo de guarnição apenas andar a árvore inteira e remover as entradas com os selos mais antigos.

Answer 3

Com caches de hardware, em vez de ter digamos 128 elementos, e mantendo a ordem dos itens 1-128, você pode tê-lo como 32 x 4, portanto, 32 linhas de 4 elementos cada. Os primeiros 5 bits de um endereço iria determinar qual das 32 linhas que o endereço seria mapear para, em seguida, você iria procurar apenas os 4 itens, e se não for encontrado substituir o mais velho dos 4.

Este é muito mais rápido, e é IIRC dentro de 10% da taxa de acerto de um cache 1 x 128.

Para traduzir, você iria em vez de uma lista ligada, tem vários queridos, assim atravessando eles era muito mais rápido. Você teria que ter uma maneira de determinar qual lista de um determinado item mapeado.

O ponto é, como a sua lista cresce em tamanho, você obtém retornos decrescentes de tentar manter com precisão perfeita ordem exata de cada elemento na lista. Você pode até ser melhor fora com uma lista não ordenada, e substituindo aleatoriamente qualquer elemento quando você tem um erro de cache. Depende do tamanho da sua lista, e a penalidade por uma falta contra o custo de manutenção da lista.