General-purpose Automatic Memoization for Recursive Functions in C++11

Memoization is a widely known optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. Repeated calculations are avoided by reusing previously computed results, which must be cached such that look-up is faster than recomputing.

Consider a simple fibonacci program

unsigned long fibonacci(unsigned n)
{
  return (n < 2) ? n :  fibonacci(n - 1) + fibonacci(n - 2);
}

This algorithm is a frustratingly slow way of computing the Nth fibonacci number (N starting at 0). It does a lot of redundant recomputations. But the beauty of this program is that it is really simple. To speed it up without changing its logic significantly, we could use memoization.

Using some clever C++11 techniques, it is possible to memoize this function, which looks like below.

unsigned long fibonacci(unsigned n)
{
  return (n < 2) ? n :
       memoized_recursion(fibonacci)(n - 1) +
       memoized_recursion(fibonacci)(n - 2);
} 

To solve this problem, I took inspiration from this post on automatic memoization. I'll go in lot more detail here including recursive functions and memory management. Here we go!

The memoize function I'm using is slightly different than that of the post above.

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(ReturnType (*func) (Args...))
{
  auto cache = std::make_shared<std::map<std::tuple<Args...>, ReturnType>>();
  return ([=](Args... args) mutable  {
          std::tuple<Args...> t(args...);
          if (cache->find(t) == cache->end())
              (*cache)[t] = func(args...);
          return (*cache)[t];
  });
}

Function memoize accepts a pointer to a free function, wraps it in a lambda, and turns the lambda into a std::function. Returning a a std::function is a common C++11 idiom of returning a lambda from a function that creates it. The implementation of the lambda is pretty straight forward if you are familiar with C++11 variadic templates. It creates a tuple of arguments and checks if it exists in the cache. In that case, the stored result is returned instead of recomputing it. The cache used for mapping arguments to the return value, is allocated dynamically. A std::shared_ptr manages the memory. The lambda copies the std::shared_ptr by value. As long as there is at least one std::function alive, the cache will remain intact.

Memoized functions may be called from different places. It is quite cumbersome to pass the memoized function everywhere it is called. There should be a way to look up a memoized version of the function without loosing the state. So our next step is to make the same memoized function available from anywhere in the program. We need a map of function pointer to a memorized std::function. Specifically, we need a std::unordered_map for fast lookup.

template <typename F_ret, typename...  F_args>
std::function<F_ret (F_args...)>
memoized_recursion(F_ret (*func)(F_args...))
{
  typedef std::function<F_ret (F_args...)> FunctionType;
  static std::unordered_map<decltype(func), FunctionType> functor_map;

  if(functor_map.find(func) == functor_map.end())
    functor_map[func] = memoize(func);

  return functor_map[func];
}

Here I introduce "memoized_recursion" function that our recursive fibonacci function is calling. It has a static std::unordered_map. It simply looks up the memorized std::function based on the function pointer value. If it does not find one, it creates it and stores it for subsequent access. Function pointers are unique; so there are no collisions possible. Here is how to call it.

memorized_recursion(fibonacci)(10);

The solution is not finished yet though. Memoization obviously builds up state very fast. If many functions are memoized with a large number of parameters, the state grows explosively. There must be some way to reclaim the memory.

Remember that the memoized state grows in the lambda. The dynamically allocated map stores the cache for corresponding function. We need to access the object that is hidden inside a lambda. Lambda has a compiler-defined type and only thing you can do with it is call it. So how would we clear the cache it is building up?

The answer is surprisingly simple! Just assign the memoizer (the lambda) with another default initialized memoizer.

We already have memoize function, which returns a default initialized memoizer. We simply assign the new one in place of the old one. Here’s how the new memoized_recursion looks like

enum class Cache : unsigned int { NO_RECLAIM, RECLAIM };

template <typename F_ret, typename... F_args>
std::function<F_ret (F_args...)>
memoized_recursion(F_ret (*func)(F_args...), Cache c = Cache::NO_RECLAIM)
{
  typedef std::function<F_ret (F_args...)> FunctionType;
  static std::unordered_map<decltype(func), FunctionType> functor_map;

  if(Cache::RECLAIM == c)
    return functor_map[func] = memoize(func);

  if(functor_map.find(func) == functor_map.end())
    functor_map[func] = memoize(func);

  return functor_map[func];
}

I’m using strongly typed enums to pass programmer’s intent to clear the cache. Here is how you call it.

memoized_recursion(fibonacci, Cache::RECLAIM);

Purely Static Memoizer

Strictly speaking, using an std::unordered_map in memoized_recursion function is not necessary. It is an O(1) mapping of function pointers to their corresponding memoized function objects (lambda wrapped in a std::function). An alternative way of achieving the same mapping is using purely static memoizer. I call it pure because there is no dynamic allocation like in std::unordered_map. The functors are stored as static objects only. This is possible only if memoized_recursion can be specialized individually for all possible free functions! Note that each free function is guaranteed to have a unique pointer value and pointer values can be used as template parameters. So here is how to combine all these things in a static_memoizer.

template <typename Sig, Sig funcptr>
struct static_memoizer;

template <typename F_ret, typename... F_args, F_ret (*func)(F_args...)>
struct static_memoizer<F_ret (*)(F_args...), func>
{
  static 
  std::function<F_ret (F_args...)> & 
  get(Cache c = Cache::NO_RECLAIM)
  {
    static std::function<F_ret (F_args...)> mfunc (memoize(func));

    if(Cache::RECLAIM == c)
      mfunc = memoize(func);

    return mfunc;
  }
};

#define STATIC_MEMOIZER(func) static_memoizer<decltype(&func), &func>

The STATIC_MEMOIZER macro simplifies the use of the static_memoizer. It extracts the type of the function pointer using decltype and passes it (the type) as the first parameter of the template. The second parameter is the actual function pointer. Passing the function pointer as a template parameter is important because many functions potentially share the same signature but never the same pointer.

The static objects used by the static_memoizer are different from that of memoized_recursion. So we've to rewrite the fibonacci function to use the static_memoizer.

unsigned long fibonacci(unsigned n)
{
  return (n < 2) ? n :
       STATIC_MEMOIZER(fibonacci)::get()(n - 1) +
       STATIC_MEMOIZER(fibonacci)::get()(n - 2);
} 

That's all for now. I hope you enjoyed it.