Общий кеш объектов
Кто-нибудь знает какую-либо реализацию шаблонного кеша объектов?
- Вы используете ключ для поиска объекта (как в std :: map <>)
- Вы указываете максимальное количество объектов, которые могут находиться в кеше одновременно
- Есть средства для создания объекта, которого нет в кеше.
- Есть средства узнать, когда объект удаляется из кеша.
Например :
typedef cache<int, MyObj*> MyCache;
MyCache oCache;
oCache.SetSize(1);
oCache.Insert(make_pair(1, new MyObj());
oCache.Touch(1);
MyObj* oldObj = oCache.Delete(1);
...
Это может быть кеш LRU или MRU.
Любые предложения приветствуются!
Ник
Ответы 3
В приложении я с трудом могу себе представить, что это ускорит / повысит производительность для хранения объектов, которые, по-видимому, можно воссоздать (бедро: поскольку они могут быть автоматически отброшены, когда кеш достигает максимума). Кэш sw потребует выборки из памяти с помощью кода ассоциативности, что, безусловно, медленнее, чем выделение памяти и запуск конструктора (в основном инициализация памяти).
За исключением ручной настройки пользователя, чтобы избежать механизма подкачки (именно для повышения производительности, кстати), большинство ОС «кэшируют» память для вас на диске ... это «подкачка», форма «дорогостоящего кэширования», потому что ничего не выбрасывается, и это делается конкретным HW, вспомогательным процессором, называемым Memory Management Unit ...
Кэширующий код, по большому счету, будет замедлять процессы, будучи избыточным.
Я понимаю, почему голос против: я не отвечаю. Итак, я пытаюсь получить один: в настоящее время MMU будет помечать память, содержащую не недавно использованные кэшированные объекты, как малоиспользуемые, следовательно, кандидат для отправки в файл подкачки на жестком диске ... при условии, что есть жесткий диск. Таким образом, повторная выборка отсутствующего кэшированного объекта с жесткого диска, исполняемый код iso для воссоздания объекта, будет «правильным» только в очень обременительном наборе обстоятельств. @Nicolas: каковы ваши конкретные обстоятельства?
Я думаю, вы смешиваете кеш процессора и другой тип кеша данных. OP искал кеш данных, а не CPU.
Я собрал относительно простой кеш LRU, построенный из карты и связанного списка:
template<typename K, typename V, typename Map = std::unordered_map<K, typename std::list<K>::iterator>>
class LRUCache
{
size_t maxSize;
Map data;
std::list<K> usageOrder;
std::function<void(std::pair<K, V>)> onEject = [](std::pair<K, V> x){};
void moveToFront(typename std::list<K>::iterator itr)
{
if (itr != usageOrder.begin())
usageOrder.splice(usageOrder.begin(), usageOrder, itr);
}
void trimToSize()
{
while(data.size() > maxSize)
{
auto itr = data.find(usageOrder.back());
onEject(std::pair<K, V>(itr->first, *(itr->second)));
data.erase(usageOrder.back());
usageOrder.erase(--usageOrder.end());
}
}
public:
typedef std::pair<const K, V> value_type;
typedef K key_type;
typedef V mapped_type;
LRUCache(size_t maxEntries) : maxSize(maxEntries)
{
data.reserve(maxEntries);
}
size_t size() const
{
return data.size();
}
void insert(const value_type& v)
{
usageOrder.push_front(v.first);
data.insert(typename Map::value_type(v.first, usageOrder.begin()));
trimToSize();
}
bool contains(const K& k) const
{
return data.count(k) != 0;
}
V& at(const K& k)
{
auto itr = data.at(k);
moveToFront(itr);
return *itr;
}
void setMaxEntries(size_t maxEntries)
{
maxSize = maxEntries;
trimToSize();
}
void touch(const K& k)
{
at(k);
}
template<typename Compute>
V& getOrCompute(const K& k)
{
if (!data.contains(k)) insert(value_type(k, Compute()));
return(at(k));
}
void setOnEject(decltype(onEject) f)
{
onEject = f;
}
};
Что, я считаю, соответствует вашим критериям. Что-то нужно добавить или изменить?
Производительность карты может легко ухудшиться. Я бы посоветовал вам использовать хеш-таблицу. Сделайте фиксированный размер времени компиляции, если можете. Вместо того, чтобы добавлять список, просканируйте его.
@BitWhistler Это действительно использует хеш-таблицу - по умолчанию std :: unordered_map, которая является хеш-таблицей. Я не думаю, что фиксированный размер во время компиляции - это вообще хорошая идея - очень низкие накладные расходы на сохранение размера, и это позволяет изменять размер по мере необходимости. Что вы имеете в виду, говоря, что вместо того, чтобы вести список, отсканируйте его? Список отслеживает порядок вставки, так что запись LRU может быть удалена.
извините, вы правы. Я думал, что видел std :: map. Тем не менее, предварительное распределение всего имеет то преимущество, что не перераспределяется. Перераспределение - самая большая стоимость здесь. Та же идея в списке. У вас были бы все эти узлы, плавающие вокруг ... лучше иметь возраст в записях или иметь односвязный список, навязчивый в записях.
Вы можете использовать библиотеку Boost.MultiIndex. Реализовать Кэш MRU легко.
Что, если (повторное) создание объекта происходит намного медленнее, чем поиск ключ-> значение? Не каждый конструктор «в основном инициализирует память».