generic non-invasive cache wrapper

Question

I'm trying create a class which adds functionality to a generic class, without directly interfacing with the wrapped class. A good example of this would be a smart pointer. Specifically, I'd like to create a wrapper which caches all the i/o for one (or any?) method invoked through the wrapper. Ideally, the cache wrapper have the following properties:

• it would not require the wrapping class to be changed in any way (i.e. generic)
• it would not require the wrapped class to be changed in any way (i.e. generic)
• it would not change the interface or syntax for using the object significantly

For example, it would be really nice to use it like this:

CacheWrapper<NumberCruncher> crunchy;
...
// do some long and ugly calculation, caching method input/output
result = crunchy->calculate(input); 
...
// no calculation, use cached result
result = crunchy->calculate(input); 

although something goofy like this would be ok:

result = crunchy.dispatch (&NumberCruncher::calculate, input);

I feel like this should be possible in C++, although possibly with some syntactic gymnastics somewhere along the line.

Any ideas?

Answer 1

I think I have the answer you are seeking, or, at least, I almost do. It uses the dispatch style you suggested was goofy, but I think it meets the first two criteria you set forth, and more or less meets the third.

1. The wrapping class does not have to be modified at all.
2. It doesn't modify the wrapped class at all.
3. It only changes the syntax by introducing a dispatch function.

The basic idea is to create a template class, whose parameter is the class of the object to be wrapped, with a template dispatch method, whose parameters are the argument and return types of a member function. The dispatch method looks up the passed in member function pointer to see if it has been called before. If so, it retrieves the record of previous method arguments and calculated results to return the previously calculated value for the argument given to dispatch, or to calculate it if it is new.

Since what this wrapping class does is also called memoization, I've elected to call the template Memo because that is shorter to type than CacheWrapper and I'm starting to prefer shorter names in my old age.

#include <algorithm>
#include <map>
#include <utility>
#include <vector>

// An anonymous namespace to hold a search predicate definition. Users of
// Memo don't need to know this implementation detail, so I keep it
// anonymous. I use a predicate to search a vector of pairs instead of a
// simple map because a map requires that operator< be defined for its key
// type, and operator< isn't defined for member function pointers, but
// operator== is.
namespace {
    template <typename Type1, typename Type2>
    class FirstEq {
        FirstType value;

    public:
        typedef std::pair<Type1, Type2> ArgType;

        FirstEq(Type1 t) : value(t) {}

        bool operator()(const ArgType& rhs) const { 
            return value == rhs.first;
        }
    };
};

template <typename T>
class Memo {
    // Typedef for a member function of T. The C++ standard allows casting a
    // member function of a class with one signature to a type of another
    // member function of the class with a possibly different signature. You
    // aren't guaranteed to be able to call the member function after
    // casting, but you can use the pointer for comparisons, which is all we
    // need to do.
    typedef void (T::*TMemFun)(void);

    typedef std::vector< std::pair<TMemFun, void*> > FuncRecords;

    T           memoized;
    FuncRecords funcCalls;

public:
    Memo(T t) : memoized(t) {}

    template <typename ReturnType, typename ArgType>
    ReturnType dispatch(ReturnType (T::* memFun)(ArgType), ArgType arg) {

        typedef std::map<ArgType, ReturnType> Record;

        // Look up memFun in the record of previously invoked member
        // functions. If this is the first invocation, create a new record.
        typename FuncRecords::iterator recIter = 
            find_if(funcCalls.begin(),
                    funcCalls.end(),
                    FirstEq<TMemFun, void*>(
                        reinterpret_cast<TMemFun>(memFun)));

        if (recIter == funcCalls.end()) {
            funcCalls.push_back(
                std::make_pair(reinterpret_cast<TMemFun>(memFun),
                               static_cast<void*>(new Record)));
            recIter = --funcCalls.end();
        }

        // Get the record of previous arguments and return values.
        // Find the previously calculated value, or calculate it if
        // necessary.
        Record*                   rec      = static_cast<Record*>(
                                                 recIter->second);
        typename Record::iterator callIter = rec->lower_bound(arg);

        if (callIter == rec->end() || callIter->first != arg) {
            callIter = rec->insert(callIter,
                                   std::make_pair(arg,
                                                  (memoized.*memFun)(arg)));
        }
        return callIter->second;
    }
};

Here is a simple test showing its use:

#include <iostream>
#include <sstream>
#include "Memo.h"

using namespace std;

struct C {
    int three(int x) { 
        cout << "Called three(" << x << ")" << endl;
        return 3;
    }

    double square(float x) {
        cout << "Called square(" << x << ")" << endl;
        return x * x;
    }
};

int main(void) {
    C       c;
    Memo<C> m(c);

    cout << m.dispatch(&C::three, 1) << endl;
    cout << m.dispatch(&C::three, 2) << endl;
    cout << m.dispatch(&C::three, 1) << endl;
    cout << m.dispatch(&C::three, 2) << endl;

    cout << m.dispatch(&C::square, 2.3f) << endl;
    cout << m.dispatch(&C::square, 2.3f) << endl;

    return 0;
}

Which produces the following output on my system (MacOS 10.4.11 using g++ 4.0.1):

Called three(1)
3
Called three(2)
3
3
3
Called square(2.3)
5.29
5.29

---

NOTES

• This only works for methods which take 1 argument and return a result. It doesn't work for methods which take 0 arguments, or 2, or 3, or more arguments. This shouldn't be a big problem, though. You can implement overloaded versions of dispatch which take different numbers of arguments up to some reasonable max. This is what the Boost Tuple library does. They implement tuples of up to 10 elements and assume most programmers don't need more than that.
• The possibility of implementing multiple overloads for dispatch is why I used the FirstEq predicate template with the find_if algorithm instead of a simple for loop search. It is a little more code for a single use, but if you are going to do a similar search multiple times, it ends up being less code overall and less chance to get one of the loops subtlely wrong.
• It doesn't work for methods returning nothing, i.e. void, but if the method doesn't return anything, then you don't need to cache the result!
• It doesn't work for template member functions of the wrapped class because you need to pass an actual member function pointer to dispatch, and an un-instantiated template function doesn't have a pointer (yet). There may be a way around this, but I haven't tried much yet.
• I haven't done much testing of this yet, so it may have some subtle (or not-so-subtle) problems.
• I don't think a completely seamless solution which satisfies all your requirements with no change in syntax at all is possible in C++. (though I'd love to be proven wrong!) Hopefully this is close enough.
• When I researched this answer, I got a lot of help from this very extensive write up on implementing member function delegates in C++. Anyone who wants to learn way more than they realized was possible to know about member function pointers should give that article a good read.

Answer 2

I haven't figured out the case for handling object methods, but I think I've got a good fix for regular functions

template <typename input_t, typename output_t>
class CacheWrapper
{
public:
  CacheWrapper (boost::function<output_t (input_t)> f)
    : _func(f)
  {}

  output_t operator() (const input_t& in)
  {
    if (in != input_)
      {
        input_ = in;
        output_ = _func(in);
      }
    return output_;
  }

private:
  boost::function<output_t (input_t)> _func;
  input_t input_;
  output_t output_;
};

Which would be used as follows:

#include <iostream>
#include "CacheWrapper.h"

double squareit(double x) 
{ 
  std::cout << "computing" << std::endl;
  return x*x;
}

int main (int argc, char** argv)
{
  CacheWrapper<double,double> cached_squareit(squareit);

  for (int i=0; i<10; i++)
    {
      std::cout << cached_squareit (10) << std::endl;
    }
}

Any tips on how to get this to work for objects?

Answer 3

It looks like a simple task, assuming the "NumberCruncher" has a known interface, let's say int operator(int). Note that you'll need to make it more complicated to support other interfaces. In order to do so, i'm adding another template parameter, an Adaptor. Adaptor should convert some interface to a known interface. Here's simple and dumb implementation with static method, which is one way to do it. Also look what Functor is.

struct Adaptor1 {
     static int invoke(Cached1 & c, int input)  {
         return(c.foo1(input));
     }
};

struct Adaptor2 {
     static int invoke(Cached2 & c, int input)  {
         return(c.foo2(input));
     }
};

template class CacheWrapper<typename T, typeneame Adaptor>
{
private:
  T m_cachedObj;
  std::map<int, int> m_cache;

public:
   // add c'tor here

   int calculate(int input) {
      std::map<int, int>::const_iterator it = m_cache.find(input);
      if (it != m_cache.end()) {
         return(it->second);
      }
      int res = Adaptor::invoke(m_cachedObj, input);
      m_cache[input] = res;
      return(res);
   }
};

Answer 4

I think what you need is something like a proxy / decorator (design patterns). You can use templates if you don't need the dynamic part of those patterns. The point is that you need to well define the interface that you will need.

Answer 5

I don't think this can be easily done using just a wrapper as you'll have to intercept the IO calls, so wrapping a class would put the code at the wrong layer. In essence, you want to substitute the IO code underneath the object, but you're trying to do it from the top layer. If you're thinking of the code as an onion, you're trying to modify the outer skin in order to affect something two or three layers in; IMHO that suggests the design might need a rethink.

If the class that you're trying to wrap/modify this way does allow you to pass in the stream (or whatever IO mechanism you use), then substituting that one for a caching one would be the right thing to do; in essence that would be what you'd be trying to achieve with your wrapper as well.