Wie kann ich meinen einfachen .NET-LRU-Cache schneller machen?

Question

UPDATE: Hey Leute, danke für die Antworten. Letzte Nacht und heute Abend habe ich ein paar verschiedene Ansätze ausprobiert und eine ähnliche wie die von Jeff (ich hatte sogar schon gemacht, was er in seinem Update vorgeschlagen hatte) entwickelt und meine eigene einfache LL-Implementierung für zusätzliche Gewinne zusammengestellt. Hier ist der Code, an diesem Punkt sieht es nicht mehr besonders sauber aus, aber ich habe unzählige Male daran gearbeitet, alles zu ändern, was ich konnte, um die Leistung zu steigern.

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 etwas überrascht über den Unterschied, den es gemacht hat, von den tatsächlichen Eigenschaften auf dem Knoten zu nur öffentlichen Variablen zu wechseln, aber ich denke, so geht es mit diesem Zeug. An dieser Stelle ist der obige Code fast ausschließlich durch die Wörterbuchoperationen performancebegrenzt, so dass ich nicht sicher bin, ob ich viel mehr davon rausholen könnte. Ich werde weiter darüber nachdenken und mir einige der Antworten ansehen.

Erklärung Vom ursprünglichen Beitrag: Hallo alle. Also habe ich eine einfache leichte LRU-Implementierung für den Einsatz in einer Komprimierungsbibliothek geschrieben (ich benutze es, um passende Byte-Strings in der Eingabe basierend auf einem Hash, LZW-Stil zu finden), und ich suche nach Möglichkeiten mach es schneller.

Answer 1

UPDATE # 2

Dies reduziert die Notwendigkeit Liste Traversal auf einer verknüpften Liste zu entfernen. Es führt einen LruCacheNode ein, der sowohl den Schlüssel als auch den Wert enthält. Der Schlüssel wird nur verwendet, wenn Sie den Cache trimmen. Sie könnten eine bessere Leistung erzielen, wenn Sie Ihre eigene Implementierung einer verknüpften Liste schreiben, bei der jeder Knoten im Wesentlichen ein LruCacheNode ist, zusammen mit einer Referenz für "Weiter" und "Zurück". Dies ist eine Art von was eine LinkedHashMap tut (siehe thesetwo 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 profilieren, um zu sehen, ob dies eine Verbesserung in Ihrer Umgebung ist.

Minor Update: Ich habe BumpToFront aktualisiert, um zu überprüfen, ob der Knoten bereits an der Front ist, und zwar per Kommentar von Tim Stewart.

Answer 2

Mit Hardware-Caches, statt 128 Elemente zu sagen, und die Reihenfolge der Elemente 1-128 beibehalten, können Sie es als 32 x 4, also 32 Zeilen mit je 4 Elementen haben. Die ersten 5 Bits einer Adresse würden bestimmen, auf welche der 32 Zeilen diese Adresse abgebildet würde, dann würden Sie nur die 4 Elemente suchen, und wenn nicht gefunden, ersetzen Sie das älteste der 4.

Dies ist viel schneller und ist IIRC innerhalb von 10% der Trefferrate eines 1 x 128-Caches.

Um zu übersetzen, würden Sie statt einer verknüpften Liste mehrere haben, so dass sie viel schneller durchlaufen. Sie müssten eine Möglichkeit haben, zu bestimmen, welcher Liste ein bestimmter Eintrag zugeordnet wird.

Der Punkt ist, wenn Ihre Liste in der Größe wächst, erhalten Sie abnehmende Erträge von versuchen, mit perfekter Genauigkeit die genaue Reihenfolge jedes Elements in der Liste zu erhalten. Sie könnten sogar mit einer ungeordneten Liste besser dran sein und zufällig jedes Element ersetzen, wenn Sie einen Cache-Fehler haben. Abhängig von der Größe Ihrer Liste und der Strafe für einen Fehlschlag gegen die Kosten der Aufrechterhaltung der Liste.

Answer 3

Ist es nicht der Zweck eines LRU-Caches, den Cache zu trimmen und das am wenigsten genutzte Zeug zu entfernen? :-) Ich sehe keinen Code, um den Cache zu trimmen.Da Sie höchstwahrscheinlich eine hohe Leistung für den Anwendungsfall abrufen möchten und der Anwendungsfall der Trimmung weniger wichtig ist, warum sollten Sie die Listenwartung nicht auf den Trimmprozess verlagern?

IOW, werfen Sie einfach die Einträge in den Cache, aber Zeitstempel sie beim Abruf. Ordnen Sie die Einträge nicht neu an, markieren Sie sie nur, wenn sie verwendet werden. Es könnte sich um einen echten DateTime-Zeitstempel oder um einen einfachen Zähler in der Klasse handeln. Die höchste Nummer wurde zuletzt verwendet. Dann im Trimmprozess einfach den ganzen Baum gehen und die Einträge mit den ältesten Stempeln entfernen.