Как я могу ускорить свой простой кеш .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;
}

Есть несколько частей, которые выглядят/ощущаются шатко - например, повторное использование старого узла при добавлении - но мне удалось добиться от них заметного повышения производительности.Я также был немного удивлен той разницей, которую имело значение при переключении с реальных свойств узла на просто общедоступные переменные, но я думаю, что именно так и происходит с этими вещами.На данный момент производительность приведенного выше кода почти полностью ограничена операциями со словарями, поэтому я не уверен, что смогу получить от него гораздо больше пользы.Я буду продолжать думать над этим и изучать некоторые ответы.

Объяснение из исходного сообщения:Всем здравствуйте.Итак, я написал простую облегченную реализацию LRU для использования в библиотеке сжатия (я использую ее для поиска совпадающих байтовых строк во входных данных на основе хеша в стиле LZW) и ищу способы сделать это быстрее.

Answer 1

ОБНОВЛЕНИЕ № 2

Это уменьшает необходимость обхода связанного списка. Удалить.Он представляет LruCacheNode, который имеет как ключ, так и значение.Ключ используется только при обрезке кеша.Вы могли бы повысить производительность, если бы написали свою собственную реализацию связанного списка, где каждый узел по сути является LruCacheNode вместе со ссылками «Далее» и «Назад».Это что-то вроде того, что делает 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.

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

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