Caching of expression evaluations for repeated input data

Question

I have a couple of simple "expression" classes derived from

namespace Expression {
class Virtual {
  public:
  Virtual();
  ~Virtual();

  virtual
  double eval(double x, double y, double z) const = 0; 
}
}

For example

class MyFun: public Virtual {
  public:
  MyFun();
  ~MyFun();

  virtual
  double eval(double x, double y, double z) const
  {
      return sin(x*x) + exp(z)*y + 3.0; // some expensive expression
  } 
}

These expressions are evaled in many, but very specific xyzs, namely the nodes of a mesh

class MyMesh {
  MyMesh();
  ~MyMesh();

  virtual
  std::vector<std::vector<double> > getNodes() const
  {
      return allMyNodes_;
  } 
}

The callee would instantiate a mesh, instantiate an Expression, and then go ahead with some numerical procedure in which theExpression is evaluated in the mesh nodes potentially many times.

MyMesh myMesh();
MyFun myExpr();

Result result = numericalProcedure(myMesh, myExpr);
// [...]

Since eval is expensive, I thought about how to speed this up a little. What comes to mind is caching.

One idea is to store all eval results in all mesh nodes in a vector with some indexing, and I'm wondering how this would be best implemented. I wouldn't want to stick any mesh data in the Expressions (to keep the cache there) nor would I want to make the interface any more complex for the callee.

Are there design patterns for caching matching this use case? What are approaches that isolate the caching logic from the rest of the code?

Answer 1

I would implement a new Expression::Virtual subclass that will do only caching, while keeping an instance of another expression to delegate actual calculations to it:

class CachedExpression: public Expression::Virtual {
    private:
       // for simplicity I assume a separate Point class
       mutable std::map<Point, double> cache_; 
       const Expression::Virtual* expr_; // or better auto_ptr or friends
    public: 
       explicit CachedExpression(const Expression::Virtual* expr): cache_(), expr_(expr) {}
       virtual double eval(const Point& point) const {
           if (cache_.find(point) == cache_.end())
               cache_[point] = expr_.eval(point);
           return cache_[point];
       }
};

...
MyMesh myMesh;
MyFun myExpr;
CachedExpression myCached(&myExpr);
// or even CachedExpression myCached(new myFun());

Result result = numericalProcedure(myMesh, myCached);

This way you can always switch off caching by using just myExpr instead of myCached, or implement different caching strategies (say keeping only N last queries to save memory) in different CachedExpression-like classes and use whichever you need.

Answer 2

What are approaches that isolate the caching logic from the rest of the code?

You could separate the cache into another class with the same interface, which can cache the results of any expression:

class Cache : public Virtual {
public:
    explicit Cache(Virtual const & target) : target(target) {}

    double eval(double x, double y, double z) const override {
       std::array<double,3> key {x,y,z};
       auto cached = cache.find(key);
       if (cached == cache.end()) {
           double result = target(x,y,z);
           cache[key] = result;
           return result;
       } else {
           return cached->second;
       }
    }

private:
    Virtual const & target;
    std::map<std::array<double,3>, double> cache;
};

which can be used thusly

Result result = numericalProcedure(myMesh, Cache(myExpr));

to wrap a temporary cache around an existing expression.

(If you want to use a more permanent cache, then it should have an invalidation policy to stop it growing too large. My simple example only releases memory on destruction, so could become a memory leak if it's never destroyed.)

Are there design patterns for caching matching this use case?

If you want to name it, that's an example of the Proxy pattern.

Answer 3

You could store a map from an array of the arguments to the result in your functor:

class MyFun {
public:
    virtual
    double eval(double x, double y, double z) const
    {
        std::array<double,3> arr {x,y,z};

        //is the answer cached?
        if (cache_.count(arr))
        {
            return cache_[arr];
        }

        double ret = sin(x*x) + exp(z)*y + 3.0;
        //cache the result
        cache_[arr] = ret;
        return ret;
    } 

private:
    //need mutable so it can be modified by a const function
    mutable std::map<std::array<double,3>, double> cache_;
};

You could even do the caching in the base class, then forward the evaluation to a virtual function:

class BaseFun {
public:
    double eval(double x, double y, double z) const
    {
        std::array<double,3> arr {x,y,z};
        if (cache_.count(arr))
        {
            return cache_[arr];
        }

        double ret = doEval(x,y,z);
        cache_[arr] = ret;
        return ret;
    }   

protected:
    virtual double doEval (double x, double y, double z) const = 0;
private:
    mutable std::map<std::array<double,3>, double> cache_;
};

class MyFun : public BaseFun {
private:
    virtual double doEval (double x, double y, double z) const override
    {
        return sin(x*x) + exp(z)*y + 3.0;
    }
};