Как я могу сделать мой простой .NET LRU кеш быстрее?

Question

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

Answer 2

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

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

Answer 3

При использовании аппаратных кешей, вместо того, чтобы иметь, скажем, 128 элементов и поддерживать порядок элементов 1-128, вы можете иметь его как 32 x 4, то есть 32 строки по 4 элемента в каждой. Первые 5 битов адреса будут определять, с какой из 32 строк этот адрес будет отображаться, затем вы будете искать только 4 элемента и, если они не найдены, заменить самый старый из 4.

Это намного быстрее, и IIRC находится в пределах 10% от частоты попаданий в кэш 1 x 128.

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

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