我怎样才能让我的简单.NET LRU缓存更快？

更新：嘿家伙谢谢你的回复。 昨晚和今晚我尝试了几种不同的方法，并提出了一个类似于下面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风格的输入中查找匹配的字节串），并且我正在寻找方法它更快。

---

更新＃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的每条评论的前面。

---

LRU缓存的重点不在于允许您修剪缓存并丢弃最近最少使用的内容吗？ :-)我看不到任何代码来修剪缓存。 由于您很可能希望获得高性能的检索用例，并且修剪用例不那么重要，为什么不将清单维护卸载到修剪过程？

IOW，只需将条目放入缓存中，但是会在检索时戳这些条目。 不要重新排序条目，只要使用它们即可标记它们。 可能是一个真正的DateTime时间戳，或者可能是一个简单的计数器，最高的数字是最近使用的。 然后在修剪过程中，只需走遍整棵树，并删除旧邮票的条目。

---

使用硬件缓存，而不是拥有128个元素，并且保持项目1-128的顺序，您可能会将其设置为32 x 4，因此每行包含32行，每行4个元素。 地址的前5位将确定地址的32行中的哪一个将映射到哪个行，然后您只搜索4个项目，如果未找到，则替换4个中最早的那个。

这要快得多，并且IIRC在1 x 128缓存命中率的10％以内。

要翻译，你会代替一个链表，有多个，所以遍历它们要快得多。 你将不得不有一种方法来确定一个特定项目映射到哪个列表。

问题的关键在于，随着列表的规模不断扩大，试图以完美的准确度维护列表中每个元素的确切顺序，您的回报将会减少。 你甚至可以用无序列表更好，并且在有缓存未命中时随机替换任何元素。 取决于你的名单的大小，以及错过的罚款与维护名单的成本。

链接地址: http://www.djcxy.com/p/42381.html

上一篇: How can I make my simple .NET LRU cache faster?

下一篇: Dynamically created DropDownList loses ListItems on Postback