Шаблон кэша LRU


Недавно я реализовал кэш для проекта побаловаться. Основными задачами за этой реализации были:

  1. Поддержка двигаться-только типы значений: в C++11 здесь, и некоторые объекты, которые будут использоваться с этим шаблоном подвижны, но не копировать. Ключи тонкие с требованием копировать, потому что двигаться-только ключи не имеют большого смысла на мой взгляд.

  2. Быстрое ключ поиска.

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

    lru_cache<int,int> c;
    c.get_or_add(17, [&blah]{ return long_calculation(blah); });
    
  4. Простой синтаксис для ленивой оценки не нужны: иногда, если экземпляр доступен, или его создание "свободных", используя лямбда-выражение может быть громоздким. Я бы предпочел просто передать его напрямую:

    c.get_or_add(17, 42); // int literals are "free", no need for laziness
    

Пункты 1 и 2 достигаются при использовании хэш-карта узлов в связанном списке. Хэш-карта дает быстрый поиск, и связанный список треков порядка пользования. Я попытался использовать импульс.Интрузивный список внутренних связаны, но крючки пока нет семантику перемещения, поэтому мне пришлось свернуть свой собственный :)

Пункты 3 и 4 выполняются посредством мета::ленивое::функция eval функция. Он один решает, является ли аргумент функции, которая вызывается или просто значение, которое будет возвращено.

Вот код:

// for wheels::meta::lazy
#include "../meta/traits.hpp"

#include <functional>
#include <cstddef>
#include <type_traits>
#include <unordered_map>
#include <utility>

namespace wheels {
    //! A cache that evicts the least recently used item.
    template <typename Key,
              typename T,
              typename Hash = std::hash<Key>,
              typename Pred = std::equal_to<Key>>
    class lru_cache {
    public:
        //! Initializes an LRU cache with the given capacity.
        lru_cache(std::size_t capacity) : front(), back(), map(), capacity(capacity) {}

        //! Fetches an item from the cache, or adds one if it doesn't exist.
        /*! The value parameter can be passed directly, or lazily (i.e. as a factory function). */
        template <typename Lazy>
        T& get_or_add(Key const& key, Lazy value) {
            auto it = map.find(key);
            if(it != map.end()) {
                touch(it);
                return it->second.value;
            } else {
                return add(key, meta::lazy<T>::eval(value));
            }
        }

        //! Flushes the cache evicting all entries.
        void flush() {
            front = back = nullptr;
            map.clear();
        }

    private:
        //! Moves a recently used entry to the front.
        template <typename Iterator>
        void touch(Iterator it) noexcept {
            auto& entry = it->second;
            unplug(entry);
            push_front(entry);
        }
        //! Adds a new entry.
        template <typename Tf>
        T& add(Key const& key, Tf&& value) {
            cache_entry entry(key, std::forward<Tf>(value));
            auto item = std::make_pair(key, std::move(entry));
            auto it = map.insert(std::move(item)).first;
            push_front(it->second);
            if(map.size() > capacity) evict();
            return it->second.value;
        }
        //! Evicts the least recently used entry.
        void evict() {
            map.erase(back->key);
            unplug(*back);
        }

        //! An entry in the cache. Maintains a linked list to track the LRU.
        struct cache_entry {
            template <typename Tf>
            cache_entry(Key const& key, Tf&& value)
            : key(key), value(std::forward<Tf>(value)), next(), prev() {}

            cache_entry(cache_entry&& that)
            : key(std::move(that.key)), value(std::move(that.value)) {}

            Key key;
            T value;
            cache_entry* next;
            cache_entry* prev;
        };

        //! Unplugs an entry from the linked list.
        void unplug(cache_entry& entry) {
            if(entry.prev) {
                entry.prev->next = entry.next;
            } else {
                front = entry.next;
            }
            if(entry.next) {
                entry.next->prev = entry.prev;
            } else {
                back = entry.prev;
            }
        }
        //! Pushes an entry to the front of the linked list.
        void push_front(cache_entry& entry) {
            entry.prev = nullptr;
            entry.next = front;
            if(front) {
                front->prev = &entry;
            } else {
                back = &entry;
            }
            front = &entry;
        }

        cache_entry* front; //! Front of the internal linked list.
        cache_entry* back; //! Back of the internal linked list.

        //! Hash table for quick lookup by key.
        std::unordered_map<Key,cache_entry, Hash> map;
        //! Maximum capacity.
        std::size_t capacity;
    };
}

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



5945
4
задан 14 сентября 2011 в 01:09 Источник Поделиться
Комментарии
1 ответ

Я думаю, что вы можете сделать содержание списка намного проще, если бы список бумаг.
С круговой списке нет проверки на null при вставке или удалении элементов (нужно просто муляж головного узла, так что пустой список точек на самого себя).

Также вы не используете достаточно инкапсуляции, это делает ваши методы немного более сложными, чем они должны быть. Например, cache_entry должна быть возможность добавлять и перемещать вокруг себя в списке.

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

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

#include <map>

class simple_cache
{
// The node(s) used to maintain the circular list.
struct Link
{
// Links are created into a list.
Link(Link* n, Link* p)
: next(n)
, prev(p)
{}

// Remove a `this` from the list.
void unlink()
{
// Unlink this from the chain
prev->next = next;
next->prev = prev;
}

// Move a link to `head` of the list.
// But we do need to pass the head of the list.
void move(Link& head)
{
unlink();

// Put this node back into the chain at the head node
this->next = &head;
this->prev = head.prev;

head.prev->next = this;
head.prev = this;
}

Link* next;
Link* prev;
};
// A cache_entry is a link
// So we can add it to the circular list.
struct cache_entry: public Link
{
// Create a link AND add it to the head of the list.
cache_entry(int key, int value, Link& head)
: Link(&head, head.prev)
, key(key)
, value(value)
{
head.prev->next = this;
head.prev = this;
}

int key;
int value;
};
typedef std::map<int, cache_entry> Data;
Link head; // Circular linked list
// If there are zero elements it points at itself
Data data;
public:
simple_cache()
: head(&head, &head)
{}

void add(int key, int value)
{
Data::iterator find = data.find(key);
if (find != data.end())
{
find->second.value = value;
find->second.move(head);
}
else
{
data.insert(std::make_pair(key,cache_entry(key, value,head)));
if (data.size() > 5)
{
evict();
}
}
}
private:
void evict()
{
/* This function will explode if called when the list is empty
* i.e. if the only link in the chain is the fake node.
* Thus it is important to make sure that you only call this
* when their is a real node in the list.
*
* Maybe a check and exception may be worth it (though if done
* correctly it should be possible to make sure it does not happen)
*/

// Get and remove the last element from the list
Link* lastElement = head.prev;
lastElement->unlink();

// Now remove it from the map.
data.erase(static_cast<cache_entry*>(lastElement)->key);
}

};

5
ответ дан 14 сентября 2011 в 07:09 Источник Поделиться