Wie kann ich mein einfaches .NET-LRU-Cache schneller zu machen?

Question

UPDATE: Hey Jungs, danke für die Antworten. Gestern Abend und heute Nacht habe ich versucht, ein paar verschiedenen Ansätze und kamen mit einer ähnlich dem sie unten von Jeff angelegt (hatte ich auch schon getan, was er in seinem Update vorgeschlagen, und meine eigene einfache LL Implementierung zusammen für zusätzliche Gewinne). Hier ist der Code, an dieser Stelle ist es nicht particularily sauber aussehen mehr, aber ich habe über diese mehrmals etwas zu ändern, ich könnte die Leistung Rindfleisch.

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

Es gibt ein paar Teile, die aussehen / fühlen wackelig - wie der alte Knoten wiederverwendet, wenn ein Add tun - aber ich konnte eine spürbare Steigerung der porformance aus ihnen heraus bekommen. Ich war auch auf dem Unterschied etwas überrascht, dass es von den tatsächlichen Eigenschaften auf dem Knoten nur öffentliche Variablen wechseln gemacht, aber ich denke, das ist, wie es mit diesem Zeug geht. An dieser Stelle oberhalb der Code ist fast ausschließlich leistungs begrenzt durch die Wörterbuch-Operationen, also bin ich nicht sicher, ob ich viel mehr aus es von Maischen um bekommen würde. Ich werde weiter daran denken, und schauen Sie in einige der Antworten.

Erklärung von den ursprünglichen Beitrag: Hallo alle.      Also habe ich eine einfache leichte LRU-Implementierung für die Verwendung in einer Kompressions-Bibliothek geschrieben (ich bin mit Byte-Zeichenfolge in der Eingabe finden passenden basierend auf einem Hash, LZW-Stil), und ich bin auf der Suche nach Möglichkeiten zu machen es schneller.

Answer 1

UPDATE # 2

Dies reduziert die Notwendigkeit Liste Traversal auf einer verknüpften Liste zu entfernen. Sie führt eine LruCacheNode, die sowohl den Schlüssel und den Wert. Der Schlüssel wird nur verwendet, wenn Sie den Cache zu trimmen. Sie könnten eine bessere Leistung erhalten, wenn Sie Ihre eigene verknüpfte Liste Implementierung geschrieben, wobei jeder Knoten im Wesentlichen eine LruCacheNode zusammen mit einem Vor und Zurück Referenz. Dies ist eine Art, was ein LinkedHashMap ist (siehe diese zwei Fragen) .

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

Du musst die Dinge Profil zu sehen, ob dies eine Verbesserung in Ihrer Umgebung ist.

Minor Update:. Ich aktualisiere BumpToFront zu überprüfen, um zu sehen, ob die Knoten bereits an der Front pro Kommentar von Tim Stewart ist

Answer 2

Ist das nicht der Punkt eines LRU-Cache, damit Sie den Cache trimmen und die am wenigsten kürzlich verwendeten Sachen wegzuwerfen? :-) Ich sehe keinen Code, um den Cache zu trimmen. Da Sie wahrscheinlich hohe Leistung für den Anwendungsfall abgerufen werden sollen, und die Trimmung Use-Case ist weniger wichtig, warum nicht die Liste Wartung des Verkleidungsprozess auslagern?

IOW, wirft nur die Einträge in die Cache, aber sie auf Abruf Zeitstempel. Sie nicht die Einträge neu anordnen, markieren Sie sie nur, wenn sie verwendet werden. Könnte ein echter Datetime Zeitstempel sein, oder könnte ein einfacher Zähler in der Klasse sein, wurde höchste Zahl zuletzt verwendet hat. Dann in dem Trimmprozess nur den ganzen Baum gehen und die Einträge mit den ältesten Briefmarken entfernen.

Answer 3

Mit Hardware-Caches, anstelle von 128 Elementen zu sagen haben, und die Aufrechterhaltung der Reihenfolge der Elemente 1-128, vielleicht haben Sie es als 32 x 4, so 32 Reihen von 4 Elementen verfügt. Die ersten 5 Bits einer Adresse würde bestimmen, welche der 32 Zeilen, die Adresse zuzuordnen wäre, dann würden Sie nur die 4 Elemente suchen, und wenn nicht die älteste der 4 gefundenen ersetzen.

Das ist viel schneller und ist IIRC innerhalb von 10% der Trefferrate einer 1 x 128-Cache.

zu übersetzen, würden Sie statt einer verknüpften Liste, haben mehrere diejenigen, sie so viel schneller durchlaufen ist. Sie würden eine Möglichkeit zu bestimmen, welche ein bestimmtes Element zu kartiert Liste haben müssen.

Der Punkt ist, wie Sie Ihre Liste in der Größe wächst, erhalten verringern Sie kehren von dem Versuch, mit perfekter Genauigkeit der genaue Reihenfolge der einzelnen Elemente in der Liste zu halten. Man könnte sogar besser dran mit einer ungeordneten Liste sein, und das Ersetzen zufällig jedes Elements, wenn Sie eine Cache-Miss haben. Abhängig von der Größe Ihrer Liste, und die Strafe für einen Fehltreffer gegen die Kosten, die Liste der beibehalten wird.