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

Question

ACTUALIZACIÓN: Oigan chicos, gracias por las respuestas. La noche anterior y esta noche probé algunos enfoques diferentes y encontré uno similar al descrito a continuación por Jeff (incluso ya había hecho lo que sugería en su actualización, y armé mi propia implementación simple de LL para obtener ganancias adicionales). Aquí está el código, en este punto ya no se ve particularmente limpio, pero he revisado esto varias veces 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 o se sienten borrosas, como la reutilización del nodo anterior al hacer un agregado, pero pude obtener un aumento apreciable en el rendimiento de ellas. También me sorprendió un poco la diferencia que marcó el hecho de cambiar de propiedades reales en el nodo a solo variables públicas, pero supongo que así es como va todo esto. En este punto, el código anterior está casi totalmente limitado por el rendimiento de las operaciones del diccionario, por lo que no estoy seguro de que pueda obtener mucho más de él. Seguiré pensando en ello y analizaré algunas de las respuestas.

Explicación de la publicación original: Hola a todos.      Así que escribí una implementación LRU liviana y simple para usar en una biblioteca de compresión (la estoy usando para encontrar cadenas de bytes en la entrada basada en un hash, estilo LZW), y estoy buscando formas de hacer más rápido.

Answer 1

ACTUALIZACIÓN # 2

Esto reduce la necesidad de recorrer la lista en una lista vinculada Eliminar. Introduce un LruCacheNode que tiene tanto la clave como el valor. La clave solo se usa cuando recortas el caché. Podría obtener un mejor rendimiento si escribió su propia implementación de lista vinculada donde cada nodo es esencialmente un LruCacheNode junto con una referencia Siguiente y Atrás. Esto es algo de lo que hace un LinkedHashMap (vea estas dos 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á que hacer un perfil de las cosas para ver si se trata de una mejora en su entorno.

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

Answer 2

¿El punto de un caché LRU no le permite recortar el caché y tirar las cosas menos usadas recientemente? :-) No veo ningún código para recortar el caché. Dado que 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 introduzca las entradas en el caché, pero marque la fecha en la recuperación. No reordene las entradas, simplemente márquelas cada vez que se usen. 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 usó más recientemente. Luego, en el proceso de recorte, simplemente recorra todo el árbol y elimine las entradas con los sellos más antiguos.

Answer 3

Con cachés de hardware, en lugar de tener 128 elementos, y manteniendo el orden de los elementos 1-128, es posible que tenga 32 x 4, por lo que 32 filas de 4 elementos cada una. Los primeros 5 bits de una dirección determinarán a cuál de las 32 filas a las que se asignaría la dirección, luego buscará 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 recorrerlas fue mucho más rápido. Tendría que tener una forma de determinar a qué lista se asignó 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 perfecta precisión el orden exacto de cada elemento en la lista. Incluso podría estar mejor con una lista desordenada, y reemplazar cualquier elemento aleatoriamente cuando falte un caché. Depende del tamaño de su lista y de la penalización por fallar el costo de mantener la lista.