C ++ простой дизайн кэша для вывода функций

Question

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

Постановка задачи

Рассмотрим следующую настройку:

class A; // some class

const A f(const A&); // an _expensive_ function

void do_stuff()
{
    A a;

    a.modify(...);

    do_stuff1(f(a));  // compute f(a)
    do_stuff2(f(a));  // use cached value of f(a)

    a.modify(...);

    do_stuff3(f(a));  // recompute f(a)
}

Я бы хотел, чтобы возвращаемое значение f(a) было кэшировано междупервый и второй вызовы, но должны быть отброшены после второго вызова на a.modify(). РЕДАКТИРОВАТЬ: На практике вызовы f(a) будут осуществляться в разных областях.

Вот примеры решений, которые я исследовал, для чего они стоят.

Решение 1: Центральный кэш

Использование отметок времени

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

const A& f(const A&);

Проблема 1: с центральным кешем, нам нужен механизм для уничтожения кэшированного результата f(a)когда a уничтожено.

Использование хеш-кодов

Помимо проблемы 1, это кажется достаточно простым.Но это становится сложным, когда A означает std::vector<...>.Я думаю, что динамический полиморфизм должен быть исключен здесь.Поэтому мы забываем о добавлении метки времени к подклассу std::vector<...> и обо всех переопределениях, которые это может означать.Однако мы могли бы вычислить некоторый хэш-код или UUID на основе содержимого a --- при условии, что это намного дешевле, чем вычисление f(a) ---, и основывать центральный кеш на этих хэш-кодах.Но мы снова сталкиваемся с проблемой 1.

Решение 2. Связанные объекты

Я до сих пор не нашел, как это реализовать, но идея состоит в том, чтобы a уведомлял кэш дляf(a) когда a записано или уничтожено, но не тогда, когда оно просто прочитано.Я не могу понять, как это сделать без динамического полиморфизма и без замедления одноэлементного доступа с использованием operator[] или итераторов, отправляя уведомления в кэш для каждого измененного элемента.

Проблема 2: найти механизм разграничения наборов изменений для a, чтобы сделать недействительным кэш-память только один раз для каждого набора изменений.

Я думал о прокси-серверах, чтобы разрешить доступ для записи на a (вдохновленоконцепция мьютекса), но не смог придумать никакого рабочего кода.

Есть идеи?

Answer 1

Я делал подобные вещи с такими интерфейсами, как это:

class F
{
public:
 virtual int f(int a)=0;
};

class Cache : public F
{
public:
   Cache(F &f) : f(f) { }
   int f(int a) { /*caching logic here, calls f.f() if not found from cache */ }
   F &f;
};

class Impl : public F
{
   int f(int a) { /* real implementation here */ }
};

Тогда просто решаю, где использовать логику кэширования:

   Impl i; 
   Cache c(i);
   c.f(10); // put to cache with key 10
   c.f(10); // found from cache
   c.f(11); // put to cache with key 11

Answer 2

делает fa членом A. Затем в случае A вы можете решить, можете ли вы повторно использовать кэшированный результат.

Answer 3

Я, вероятно, упускаю здесь некоторые важные детали, но вы не можете просто использовать LRU кеш для этой цели?

Answer 4

Не могли бы вы просто сделать это:

const A &cacheA = f(a);
do_stuff1(cacheA);  // compute f(a)
do_stuff2(cacheA);  // use cached value of f(a)