Comment rendre mon cache .NET LRU simple plus rapide?

Question

UPDATE: Hé les gars merci pour les réponses. Hier soir et ce soir, j’ai essayé différentes approches et en ai proposé une semblable à celle présentée ci-dessous par Jeff (j’avais déjà déjà fait ce qu’il avait suggéré dans sa mise à jour et mis en place ma propre implémentation simple de LL pour des gains supplémentaires). Voici le code, à ce stade, il ne semble plus particulièrement propre, mais je me suis souvent efforcé de changer tout ce que je pouvais pour améliorer mes performances.

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

Il y a quelques éléments qui semblent déréglés - comme la réutilisation de l'ancien nœud lors d'une opération d'ajout - mais j'ai pu en tirer un gain de performance appréciable. J'ai également été un peu surpris de la différence entre les propriétés réelles du nœud et les seules variables publiques, mais je suppose que c'est comme cela que les choses se passent. À ce stade, le code ci-dessus est presque entièrement limité en performances par les opérations du dictionnaire, je ne suis donc pas sûr que je pourrais en tirer beaucoup plus. Je vais continuer à réfléchir et à examiner certaines des réponses.

Explication du message original: Bonjour à tous.      J'ai donc écrit une implémentation LRU légère et simple à utiliser dans une bibliothèque de compression (je l'utilise pour trouver des chaînes d'octets correspondantes dans l'entrée en fonction d'un hachage, style LZW), et je cherche des moyens de créer plus vite.

Answer 1

UPDATE # 2

Cela réduit la nécessité de parcourir la liste sur une liste liée Supprimer. Il introduit un LruCacheNode qui a la clé et la valeur. La clé n'est utilisée que lorsque vous réduisez le cache. Vous pourriez obtenir de meilleures performances si vous écriviez votre propre implémentation de liste chaînée dans laquelle chaque nœud est essentiellement un LruCacheNode avec une référence Next et Back. C'est en quelque sorte ce que fait un LinkedHashMap (voir Ces deux questions) .

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

Vous devrez profiler les éléments pour voir s'il s'agit d'une amélioration de votre environnement.

Mise à jour mineure: , j'ai mis à jour BumpToFront pour vérifier si le nœud est déjà au premier plan à la suite des commentaires de Tim Stewart.

Answer 2

Le cache LRU n'a-t-il pas pour but de vous permettre de le rogner et de jeter les éléments les moins récemment utilisés? :-) Je ne vois pas de code pour supprimer le cache. Etant donné que vous souhaitez probablement des performances élevées pour le cas d'utilisation de récupération, et que le cas d'utilisation du découpage est moins important, pourquoi ne pas charger la maintenance de la liste du processus de découpage?

IOW, il suffit de jeter les entrées dans le cache, mais de les horodater lors de la récupération. Ne réorganisez pas les entrées, cochez-les chaque fois qu'elles sont utilisées. Peut-être un vrai horodatage DateTime ou un simple compteur dans la classe, le nombre le plus élevé ayant été utilisé le plus récemment. Ensuite, dans le processus de rognage, il suffit de parcourir tout l’arbre et de supprimer les entrées avec les tampons les plus anciens.

Answer 3

Avec les caches matériels, au lieu d’avoir 128 éléments et de conserver l’ordre des éléments 1 à 128, vous pouvez l’avoir au format 32 x 4, soit 32 lignes de 4 éléments. Les 5 premiers bits d’une adresse détermineraient les 32 rangées vers lesquelles l’adresse mapperait, puis ne rechercheraient que les 4 éléments et, s’ils ne se trouvaient pas, remplacent le plus ancien des 4.

C’est beaucoup plus rapide et l’IIRC est à moins de 10% du taux de réussite d’un cache de 1 x 128.

Pour traduire, vous auriez plusieurs listes à la place d'une seule liste chaînée, donc parcourir la liste était beaucoup plus rapide. Vous devez disposer d’un moyen de déterminer la liste à laquelle un élément particulier est associé.

En réalité, à mesure que votre liste grandit, vous obtenez des rendements décroissants si vous essayez de conserver avec une précision parfaite l’ordre exact de chaque élément de la liste. Vous pourriez même avoir intérêt à utiliser une liste non ordonnée et à remplacer n'importe quel élément de manière aléatoire en cas d'absence de mémoire cache. Dépend de la taille de votre liste et de la pénalité pour un manquement par rapport au coût de son entretien.