title: How can I make my simple .NET LRU cache faster?
body: <p>Last night and tonight I tried a few different approaches and came up with one similar to the one laid out below by Jeff (I had even already done what he suggested in his update, and put together my own simple LL implementation for additional gains).  Here is the code, at this point it doesn't look particularily clean anymore, but I have been over this numerous times changing anything I could to beef up performance.</p>
  <pre><code>public class NewLRU2&lt;K, V&gt; where V : class
  {
      int m_iMaxItems;
      Dictionary&lt;K, LRUNode&lt;K, V&gt;&gt; m_oMainDict;
  
      private LRUNode&lt;K,V&gt; m_oHead;
      private LRUNode&lt;K,V&gt; m_oTail;
      private LRUNode&lt;K,V&gt; m_oCurrent;
  
      public NewLRU2(int iSize)
      {
          m_iMaxItems = iSize;
          m_oMainDict = new Dictionary&lt;K, LRUNode&lt;K,V&gt;&gt;();
  
          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 &gt;= m_iMaxItems)
          {   
              //remove old
              m_oMainDict.Remove(m_oTail.Key);
  
              //reuse old
              LRUNode&lt;K, V&gt; 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&lt;K, V&gt; oNewNode = new LRUNode&lt;K, V&gt;(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&lt;K,V&gt;
  {
      public LRUNode(K key, V val)
      {
          Key = key;
          Value = val;
      }
  
      public K Key;
      public V Value;
      public LRUNode&lt;K, V&gt; Next;
      public LRUNode&lt;K, V&gt; Prev;
  }
  </code></pre>
  <p>There are a few parts that look/feel wonky -- like reusing the old node when doing an add -- but I was able to get an appreciable boost in porformance out of them. I was also slightly surprised at the difference it made to switch from actual properties on the node to just public variables, but I guess that's how it goes with this stuff.  At this point the code above is almost entirely performance-limited by the dictionary operations, so I'm not sure I'd get a lot more out of mashing it around.  I'll continue to think on it and look into some of the responses.</p>
  <p>Explanation From Original Post:
  Hello all.
  So I've written a simple lightweight LRU implementation for use in a compression library (I'm using it to find matching byte-strings in the input based on a hash, LZW-style), and I'm looking for ways to make it faster.</p>