Simple C ++ cache design for function output

Question

I assume this is a fairly common problem with known solutions that I have not been able to find. Therefore, I am looking for advice here.

Problem Statement

Consider the following setup:

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) } 

I would like the return value of f(a) be cached between the first and second calls, but discarded after the second call of a.modify() . EDIT: In practice, f(a) calls will be in different areas.

Here are the pieces of the solutions I studied for what it's worth.

Solution 1: Central Cache

Using time stamps

I can imagine a simple solution, including adding a timestamp to class A , which the function f can check and decide whether to update its cached result, is stored somewhere in the central cache. I assume this also implies a change in the signature f :

 const A& f(const A&); 

Problem 1: with a central cache, we need a mechanism to destroy the cached result f(a) when A destroyed.

Using hash codes

Besides problem 1, this seems fairly straightforward. But this is complicated when A stands for std::vector<...> . I suggest that dynamic polymorphism should be excluded. Here. Therefore, we forget about adding a timestamp to the subclass std::vector<...> and all that it would imply. However, we could calculate some hash code or UUID based on the contents of A - provided that it is much cheaper than calculating f(a) --- and base the central cache on these hash codes. But we are facing Problem 1 again.

Solution 2: Related Objects

I still have not found how to implement this, but the idea is to A notify the cache for f(a) when A written or destroyed, but not when it is just read. I can’t figure out how to do this without dynamic polymorphism, and without slowing down singleton access using operator[] or iterators, sending notifications to the cache for each modified element.

Task 2: find a mechanism for splitting change sets by A so that the cache is not valid only once for each change set.

I was thinking of proxies to allow write access to A (inspired by the concept of the mutex), but could not find any working code.

Any ideas?

Answer 1

I made similar material with such interfaces:

 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 ff() if not found from cache */ } F &f; }; class Impl : public F { int f(int a) { /* real implementation here */ } }; 

Then it just decides where to use the caching logic:

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

Answer 2

Can't you do it:

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

Answer 3

I may be missing important information, but can you use the LRU cache for this purpose?

Answer 4

make f a member of A. Then you can decide in case A if you can reuse the cached result or not.