¿Cómo puedo hacer que mi caché. LRU simple sea más rápido?

Question

ACTUALIZACIÓN: Hola chicos gracias por las respuestas. Anoche y esta noche probé algunos enfoques diferentes y obtuve uno similar al que presenta Jeff (ya había hecho lo que sugería en su actualización, y armé mi propia implementación de LL para obtener ganancias adicionales). Aquí está el código, en este punto ya no se ve particularmente limpio, pero he pasado por esto muchas veces cambiando todo lo que pude para mejorar el rendimiento.

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

Hay algunas partes que se ven/sienten poco firme - como la reutilización del nodo de edad cuando se hace un add - pero yo era capaz de conseguir un impulso apreciable en porformance fuera de ellos. También me sorprendió un poco la diferencia que suponía cambiar de propiedades reales en el nodo a solo variables públicas, pero supongo que así es como funciona esto. En este punto, el código anterior está limitado casi por completo por las operaciones del diccionario, por lo que no estoy seguro de que pueda obtener mucho más de lo necesario. Continuaré pensando en ello y veré algunas de las respuestas.

Explicación del mensaje original: Hola a todos. Así que he escrito una implementación de LRU liviana simple para usar en una biblioteca de compresión (la estoy usando para encontrar cadenas de bytes coincidentes en la entrada basada en un hash, estilo LZW), y estoy buscando formas de hazlo mas rapido.

Answer 1

ACTUALIZACIÓN # 2

Esto reduce la necesidad de recorrido de lista en la lista Quitar vinculado. Introduce un LruCacheNode que tiene tanto la clave como el valor. La clave solo se usa cuando recorta la caché. Podría obtener un mejor rendimiento si escribiera su propia implementación de lista enlazada, donde cada nodo es esencialmente un LruCacheNode junto con una referencia Siguiente y Atrás. Esto es más o menos lo que hace LinkedHashMap (consulte thesetwo preguntas).

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

Tendrás que hacer un perfil para ver si esto mejora tu entorno.

Actualización menor: Actualicé BumpToFront para verificar si el nodo ya está en la parte frontal por comentario de Tim Stewart.

Answer 2

Con cachés de hardware, en lugar de tener 128 elementos y mantener el orden de los elementos 1-128, puede tenerlos como 32 x 4, por lo que 32 filas de 4 elementos cada uno. Los primeros 5 bits de una dirección determinarían a cuál de las 32 filas se asignaría la dirección, luego buscaría solo los 4 elementos, y si no se encuentra, reemplazará el más antiguo de los 4.

Esto es mucho más rápido y es IIRC dentro del 10% de la tasa de aciertos de un caché de 1 x 128.

Para traducir, en lugar de una lista vinculada, tendría varias, por lo que atravesarlas era mucho más rápido. Tendría que tener una forma de determinar a qué lista se asigna un elemento en particular.

El punto es que, a medida que su lista aumenta de tamaño, obtiene rendimientos decrecientes al tratar de mantener con precisión perfecta el orden exacto de cada elemento en la lista. Incluso podría estar mejor con una lista desordenada y reemplazar aleatoriamente cualquier elemento cuando se pierda un caché. Depende del tamaño de tu lista, y de la penalización por una falla frente al costo de mantener la lista.

Answer 3

¿No es el objetivo de una memoria caché LRU para permitirle recortar la memoria caché y tirar las cosas usadas recientemente? :-) No veo ningún código para recortar el caché.Como lo más probable es que desee un alto rendimiento para el caso de uso de recuperación, y el caso de uso de recorte es menos importante, ¿por qué no descargar el mantenimiento de la lista al proceso de recorte?

IOW, simplemente arroje las entradas a la caché, pero márquelas en la fecha de recuperación. No reordene las entradas, solo márquelas cada vez que las use. Podría ser una marca de tiempo DateTime verdadera, o podría ser un contador simple en la clase, el número más alto se utilizó más recientemente. Luego, en el proceso de recorte, recorra todo el árbol y elimine las entradas con los sellos más antiguos.