Come posso velocizzare la mia cache LRU .NET?

Question

UPDATE: Ehi ragazzi grazie per le risposte. Ieri sera e stasera ho provato alcuni approcci diversi e ne ho escogitato uno simile a quello indicato di seguito da Jeff (avevo già fatto quello che mi aveva suggerito nel suo aggiornamento e messo insieme la mia semplice implementazione LL per ulteriori guadagni). Ecco il codice, a questo punto non sembra più particolarmente pulito, ma ci sono stato molte volte cambiando tutto ciò che potevo per migliorare le prestazioni.

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

Ci sono alcune parti che sembrano / si sentono traballanti - come riutilizzare il vecchio nodo quando si fa un'aggiunta - ma sono stato in grado di ottenere una spinta apprezzabile dalla loro performance. Sono stato anche leggermente sorpreso dalla differenza che ha fatto per passare dalle proprietà effettive sul nodo a solo variabili pubbliche, ma immagino che sia così con questa roba. A questo punto il codice sopra è quasi interamente limitato dalle prestazioni del dizionario, quindi non sono sicuro che otterrò molto di più da schiacciarlo. Continuerò a pensarci e ad esaminare alcune delle risposte.

Spiegazione dal post originale: Ciao a tutti.      Quindi ho scritto una semplice implementazione LRU leggera da utilizzare in una libreria di compressione (la sto usando per trovare stringhe di byte corrispondenti nell'input basato su un hash, in stile LZW) e sto cercando modi per creare più veloce.

Answer 1

AGGIORNAMENTO # 2

Ciò riduce la necessità di attraversare un elenco su un elenco collegato Rimuovi. Introduce un LruCacheNode che ha sia la chiave che il valore. La chiave viene utilizzata solo quando si taglia la cache. È possibile ottenere prestazioni migliori se si scrive l'implementazione dell'elenco collegato in cui ciascun nodo è essenzialmente un LruCacheNode insieme a un riferimento Next e Back. Questo è un po 'quello che fa una LinkedHashMap (vedi queste due domande) .

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

Dovrai profilare le cose per vedere se si tratta di un miglioramento nel tuo ambiente.

Aggiornamento secondario: ho aggiornato BumpToFront per verificare se il nodo è già in primo piano per commento da Tim Stewart.

Answer 2

Il punto di una cache LRU non ti consente di tagliare la cache e buttare via le cose usate meno di recente? :-) Non vedo alcun codice per tagliare la cache. Dato che molto probabilmente desideri prestazioni elevate per il caso d'uso di recupero e il caso d'uso del trim è meno importante perché non scaricare la manutenzione dell'elenco nel processo di trim?

IOW, lancia semplicemente le voci nella cache, ma timestamp al momento del recupero. Non riordinare le voci, basta contrassegnarle ogni volta che vengono utilizzate. Potrebbe essere un vero timestamp DateTime o potrebbe essere un semplice contatore nella classe, il numero più alto è stato utilizzato più di recente. Quindi, nel processo di taglio, basta percorrere l'intero albero e rimuovere le voci con i timbri più vecchi.

Answer 3

Con le cache hardware, invece di dire 128 elementi e mantenendo l'ordine degli articoli 1-128, potresti averlo come 32 x 4, quindi 32 righe di 4 elementi ciascuno. I primi 5 bit di un indirizzo determinerebbero a quale delle 32 righe mapperebbe quell'indirizzo, quindi cercherai solo i 4 elementi e, se non lo trovi, sostituirai il più vecchio dei 4.

Questo è molto più veloce ed è IIRC entro il 10% della frequenza di hit di una cache 1 x 128.

Per tradurre, invece di un elenco collegato, ne avresti più di uno, quindi attraversarli era molto più veloce. Dovresti avere un modo per determinare a quale elenco mappare un particolare elemento.

Il punto è che, man mano che la tua lista cresce di dimensioni, ottieni rendimenti decrescenti provando a mantenere con perfetta precisione l'ordine esatto di ciascun elemento nella lista. Potresti anche stare meglio con un elenco non ordinato e sostituire casualmente qualsiasi elemento in caso di mancanza della cache. Dipende dalla dimensione della tua lista e dalla penalità per mancata contro il costo di mantenimento della lista.