Как реализовать поточное вытеснение LRU-кэша?

Question

Как реализовать поточное вытеснение LRU-кэша?

Я реализовал LRU кеш (код), который я хотел бы использовать для многопоточной задачи сопоставления с N элементами и полным N ^ 2 (все пары) сопоставления. В идеале я бы просто получал ссылку на каждый элемент прямо из кеша для экономии памяти.

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

Простое решение состоит в том, чтобы просто не использовать ссылки, но мне интересно, есть ли лучший способ гарантировать, что элементы не будут выселены, если они «используются в настоящее время» или имеют ссылку на них?

0

c++caching lru multithreading

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Чтобы избежать выселения используемых объектов, можно использовать функцию подсчета ссылок std::shared_ptr, Рассмотрим следующую реализацию:

#include <iostream>
#include <string>
#include <memory>
#include <map>
#include <algorithm>

template <typename K, typename V> class cache
{
public:
cache() {}

static const constexpr int max_cache_size = 2;

std::shared_ptr<V> getValue(const K& k)
{
auto iter = cached_values.find(k);
if (iter == cached_values.end()) {

if (cached_values.size() == max_cache_size) {
auto evictIter =
std::find_if(cached_values.begin(), cached_values.end(),
[](const auto& kv) { return kv.second.second.unique(); });

if (evictIter == cached_values.end()) {
std::cout << "Nothing to evict\n";
return nullptr;
}

cached_values.erase(evictIter);
}

static V next;

iter = cached_values.insert(std::make_pair(k, std::make_pair(++next, nullptr))).first;
iter->second.second = std::shared_ptr<V>(&iter->second.first, [](const auto&) {});
}

return iter->second.second;
}

std::map<K, std::pair<V, std::shared_ptr<V>>> cached_values;
};

int main()
{
cache<int, int> c;

std::cout << *c.getValue(10) << "\n";
std::cout << *c.getValue(20) << "\n";
std::cout << *c.getValue(30) << "\n";

auto useOne = c.getValue(10);
auto useTwo = c.getValue(20);
std::cout << *c.getValue(20) << "\n"; // We can use stuff that is still in cache
std::cout << c.getValue(30);          // Cache is full, also note no dereferencing
}

В основном, пока кто-либо вне кэша использует возвращаемое значение, std::shared_ptr::unique вернет false, делая запись в кэше неисчерпаемой.

Живой пример

1