如何更快地创建简单的.NET LRU缓存？

Question

更新： 嘿伙计们感谢你们的回复。昨晚和今晚我尝试了几种不同的方法，并提出了类似于Jeff下面列出的方法（我甚至已经完成了他在更新中建议的内容，并将我自己的简单LL实现放在一起以获得额外收益）。这是代码，此时它看起来并不特别干净，但是我已经多次改变这一切，以改善我的表现。

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

有一些部件看起来/感觉不稳定 - 比如在进行添加时重复使用旧节点 - 但是我能够从中获得明显的性能提升。我对从节点上的实际属性切换到公共变量所产生的差异感到有些惊讶，但我想这就是它与这些东西的关系。在这一点上，上面的代码几乎完全受到字典操作的性能限制，所以我不确定我是否会从混搭中获得更多。我将继续思考并研究一些回应。

来自原帖的解释： 大家好。      所以我编写了一个简单的轻量级LRU实现用于压缩库（我用它来根据散列，LZW样式在输入中查找匹配的字节串），我正在寻找制作方法它更快。

Answer 1

更新＃2

这减少了链表清单上的列表遍历的需要。它引入了一个同时具有键和值的LruCacheNode。该键仅在您修剪缓存时使用。如果您编写自己的链接列表实现，其中每个节点本质上是LruCacheNode以及Next和Back引用，则可以获得更好的性能。这是LinkedHashMap的作用（参见这些 两个问题）

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

您必须对事情进行分析，看看这是否会改善您的环境。

次要更新：我更新了BumpToFront以检查节点是否已经位于Tim Stewart的每条评论的前面。

Answer 2

LRU缓存是不是允许你修剪缓存并丢弃最近最少使用的东西？ :-)我没有看到任何代码来修剪缓存。由于您很可能希望检索用例具有高性能，并且修剪用例不太重要，为什么不将列表维护卸载到修剪过程？

IOW，只是将条目放入缓存中，但在检索时加上时间戳。不要对条目重新排序，只需在使用时标记它们。可以是真正的DateTime时间戳，也可以是类中的简单计数器，最近使用的最高数字。然后在修剪过程中，只需走完整棵树，然后删除带有最旧邮票的条目。

Answer 3

使用硬件缓存，而不是说128个元素，并维护项目1-128的顺序，您可能将其设置为32 x 4，因此32行，每行4个元素。地址的前5位将确定地址中的32行中的哪一行将映射到，然后您将仅搜索4个项目，如果未找到，则替换4中最旧的项目。

速度更快，IIRC在1 x 128缓存命中率的10％范围内。

要进行翻译，您将使用多个链接列表而不是一个链接列表，因此遍历它们要快得多。您必须有一种方法来确定特定项目映射到哪个列表。

关键是，随着列表大小的增加，您尝试以完美的准确度维护列表中每个元素的确切顺序，从而获得的收益递减。使用无序列表可能会更好，并且当您有缓存未命中时随机替换任何元素。取决于列表的大小，以及未命中的罚款与维护列表的成本。