Come posso rendere la mia semplice cache LRU .NET più veloce?

Question

UPDATE: Hey ragazzi, grazie per le risposte. Ieri sera e stasera ho provato alcuni approcci diversi e ne ho trovato uno simile a quello presentato di seguito da Jeff (avevo già fatto ciò che mi aveva suggerito nel suo aggiornamento, e ho messo insieme la mia semplice implementazione LL per ulteriori guadagni). Ecco il codice, a questo punto non sembra più particolarmente pulito, ma sono stato oltre questo molte volte cambiando tutto ciò che potevo per rafforzare 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 appaiono/sentono traballante - come riutilizzare il vecchio nodo quando si fa un add - ma ero in grado di ottenere una spinta notevole in porformance fuori di essi. Sono stato anche un po 'sorpreso dalla differenza che ha fatto passare da proprietà reali sul nodo a solo variabili pubbliche, ma credo che sia così che va con questa roba. A questo punto il codice di cui sopra è quasi interamente limitato dalle prestazioni delle operazioni del dizionario, quindi non sono sicuro che ne ricaveremo molto di più. Continuerò a pensarci su e ad esaminare alcune delle risposte.

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

Answer 1

UPDATE # 2

Questo riduce la necessità per la lista attraversamento in una lista collegata Rimuovi. Introduce un LruCacheNode che ha sia la chiave che il valore. La chiave viene utilizzata solo quando si ritaglia la cache. È possibile ottenere prestazioni migliori se si è scritta la propria implementazione dell'elenco collegato in cui ogni nodo è essenzialmente un LruCacheNode insieme a un riferimento Avanti e Indietro. Questo è un po 'come fa LinkedHashMap (vedi domande thesetwo).

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 questo è un miglioramento nel tuo ambiente.

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

Answer 2

Con cache hardware, invece di dire 128 elementi, e mantenendo l'ordine degli articoli 1-128, si può avere come 32 x 4, quindi 32 righe di 4 elementi ciascuna. I primi 5 bit di un indirizzo determinano quale delle 32 righe a cui indirizza l'indirizzo, quindi si cercano solo i 4 elementi e se non trovato si sostituisce il più vecchio dei 4.

Questo è molto più veloce, e è IIRC entro il 10% della velocità di trasmissione di una cache di 1 x 128.

Per tradurre, anziché una lista collegata, ne hai di più, quindi attraversarli era molto più veloce. Dovresti avere un modo per determinare a quale elenco è associato un particolare oggetto.

Il punto è che, man mano che la lista cresce di dimensioni, si ottengono rendimenti decrescenti dal tentativo di mantenere con precisione perfetta l'ordine esatto di ciascun elemento nell'elenco. Potresti anche stare meglio con una lista non ordinata e sostituire a caso qualsiasi elemento quando manchi una cache. Dipende dalla dimensione della tua lista, e la penalità per un mancato rispetto del costo di mantenimento della lista.

Answer 3

Non è il punto di una cache LRU per consentire di tagliare la cache e buttare fuori la roba usata da poco? :-) Non vedo alcun codice per tagliare la cache.Dal momento che molto probabilmente desideri prestazioni elevate per il caso di utilizzo del recupero e il caso di utilizzo dell'assetto è meno importante perché non scaricare la manutenzione degli elenchi sul processo di ritaglio?

IOW, è sufficiente lanciare le voci nella cache, ma sovrastamparle per il recupero. Non riordinare le voci, basta contrassegnarle quando vengono utilizzate. Potrebbe essere un vero timestamp DateTime, o potrebbe essere un semplice contatore nella classe, il più alto numero è stato utilizzato più di recente. Quindi nel processo di ritaglio basta camminare sull'intero albero e rimuovere le voci con i timbri più vecchi.