如何讓我的簡單.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; 
} 

有看起來/感覺靠不住的幾個部分 - 喜歡做的加載時重用舊節點 - 但我能得到在porformance有明顯提升了出來。我對它從節點上的實際屬性切換到公共變量所帶來的差異也有些驚訝，但我想這就是它與這些東西的關係。在這一點上面的代碼幾乎完全受到字典操作的性能限制，所以我不確定我會在混合它的時候得到更多的東西。我會繼續考慮並研究一些答案。

說明原帖： 大家好。 所以我寫了一個簡單的輕量級LRU實現用於壓縮庫（我使用它在輸入中找到匹配的字節串，基於散列，LZW風格），並且我正在尋找使其更快。

Answer 1

更新＃2

這減少了對鏈接的列表中刪除列表遍歷的需要。它引入了一個具有鍵和值的LruCacheNode。只有在修剪緩存時纔會使用該密鑰。如果您編寫自己的鏈接列表實現，其中每個節點實質上是LruCacheNode以及Next和Back引用，則可以獲得更好的性能。這就是LinkedHashMap的功能（請參閱thesetwo問題）。

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

有了硬件緩存，而不是擁有128個元素，並且維護了項目1-128的順序，您可能會將其作爲32 x 4，因此32行每行4個元素。地址的前5位將決定地址的32行中的哪一個將映射到哪個地址，然後您只搜索4個項目，如果找不到，則替換4中最早的一個。是IIRC在1 x 128緩存命中率的10％以內。

要翻譯，你會代替一個鏈表，有多個，所以遍歷它們要快得多。你將不得不有一種方法來確定一個特定項目映射到哪個列表。

問題是，隨着列表的大小不斷增加，您將嘗試以完美的精度維護列表中每個元素的確切順序，從而獲得遞減收益。你甚至可以用無序列表更好，並且在有緩存未命中時隨機替換任何元素。取決於你的名單的大小，以及錯過的罰款與維護名單的成本。

Answer 3

LRU緩存的重點不在於允許您修剪緩存並丟棄最近最少使用的內容嗎？ :-)我看不到任何代碼來修剪緩存。由於您很可能希望獲得高性能的檢索用例，並且修剪用例不那麼重要，爲什麼不將清單維護卸載到修剪過程？

IOW，只是將條目放入緩存中，但在檢索時將它們時間戳。不要重新排序條目，只要使用它們即可標記它們。可能是一個真正的DateTime時間戳，或者可能是一個簡單的計數器，最高的數字是最近使用的。然後在修剪過程中，只需走遍整棵樹，並刪除舊郵票的條目。