Как ускорить мой простой кеш .NET LRU?

Question

ОБНОВЛЕНИЕ: Эй, ребята, спасибо за ответы. Прошлой ночью и сегодня я попробовал несколько разных подходов и придумал один, похожий на тот, который был приведен ниже Джеффом (я даже уже сделал то, что он предложил в его обновлении, и собрал мою собственную простую реализацию 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

UPDATE # 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 в пределах 10% от скорости атаки в кеше 1 x 128.

Чтобы перевести, вы должны вместо одного связанного списка иметь несколько, поэтому пересечение их было намного быстрее. Вам нужно будет определить, к какому списку относится определенный элемент.

Суть в том, что, поскольку ваш список растет в размерах, вы получаете уменьшающуюся отдачу от попыток поддерживать с полной точностью точный порядок каждого элемента в списке. Вам может быть даже лучше с неупорядоченным списком и случайным образом заменять любой элемент, когда у вас есть пропущенный кеш. Зависит от размера вашего списка и штрафа за промах и стоимости содержания списка.

Answer 3

Разве не кеш LRU, чтобы вы могли обрезать кеш и выбросить наименее недавно использованный материал? :-) Я не вижу никакого кода для обрезки кеша.Поскольку вы, скорее всего, хотите получить высокую производительность для извлечения прецедента, а практичный вариант обрезки менее важен, почему бы не разгрузить обслуживание списка до процесса обрезки?

IOW, просто вставьте записи в кеш, но отметьте их при поиске. Не меняйте порядок записей, просто отмечайте их, когда они используются. Может быть истинной меткой даты DateTime, или может быть простым счетчиком в классе, самое последнее число было самым последним. Затем в процессе обрезки просто пройдите по всему дереву и удалите записи со старейшими марками.