63

Looking for a way to implement a universal generic memoization function which will take a function and return the memoized version of the same?

Looking for something like @memo (from Norving's site)decorator in python.

def memo(f):
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo

Going more general, is there a way to express generic and reusable decorators in C++, possibly using the new features of C++11?

3
  • 9
    Maybe this answer is of interest to you.
    – Kerrek SB
    Jul 23, 2013 at 9:15
  • 2
    I think Sumanth Tambe comprehensively treated this topic in his blog post: cpptruths.blogspot.nl/2012/01/…
    – sehe
    Jul 24, 2013 at 12:36
  • If this question is really a duplicate, shouldn't answers for this one be migrated to the other one it refers to?
    – ascobol
    May 5, 2014 at 21:00

5 Answers 5

45

A compact one returning a lambda:

template <typename R, typename... Args>
std::function<R (Args...)> memo(R (*fn)(Args...)) {
    std::map<std::tuple<Args...>, R> table;
    return [fn, table](Args... args) mutable -> R {
        auto argt = std::make_tuple(args...);
        auto memoized = table.find(argt);
        if(memoized == table.end()) {
            auto result = fn(args...);
            table[argt] = result;
            return result;
        } else {
            return memoized->second;
        }
    };
}

In C++14, one can use generalized return type deduction to avoid the extra indirection imposed by returning std::function.

Making this fully general, permitting passing arbitrary function objects without wrapping them in std::function first is left as an exercise for the reader.

11
  • 13
    Could you also post an example usage for this?
    – akrohit
    Jul 23, 2013 at 11:26
  • 6
    I have no idea if the original Python does so, but a sad thing about this is that, in case the function passed in is recursive, its recursive invocations won't use memoized results. Jul 24, 2013 at 12:36
  • 2
    @soandos: not sure what threading has to do with it; the problem is that a recursive function will directly call itself and not any wrapper like the one provided here, so only the result of the "outer-most" call of the recursive function will be memoized. If that's the case, where you store the table is immaterial. Jul 24, 2013 at 18:22
  • 4
    @R.MartinhoFernandes The Python variant doesn't have this problem, as the function name is looked up at runtime. Since @memo\n def f(): is basically the same as def f():\n f = memo(f), when f is called it sees the memoized version of itself and uses this in recursive calls.
    – filmor
    Jul 24, 2013 at 20:43
  • 2
    For usage, you can let C++ figure everything out and use auto result = memo(f)(args);. If you want to memoize an overloaded function, you'll have to specify the parameter types explicitly, int r = memo<int, const char*>(atoi)("42")
    – Joe
    Sep 6, 2014 at 17:14
26

The right way to do memoization in C++ is to mix the Y-combinator in.

Your base function needs a modification. Instead of calling itself directly, it takes a templateized reference to itself as its first argument (or, a std::function<Same_Signature> recursion as its first argument).

We start with a Y-combinator. Then we add in a cache on the operator() and rename it to memoizer, and give it a fixed signature (for the table).

The only thing left is to write a tuple_hash<template<class...>class Hash> that does a hash on a tuple.

The type of the function that can be memoized is (((Args...)->R), Args...) -> R, which makes the memoizer of type ( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R). Having a Y-combinator around to produce a 'traditional' recursive implementation can also be useful.

Note that if the function memoized modifies its args during a call, the memoizer will cache the results in the wrong spot.

struct wrap {};

template<class Sig, class F, template<class...>class Hash=std::hash>
struct memoizer;
template<class R, class...Args, class F, template<class...>class Hash>
struct memoizer<R(Args...), F, Hash> {
  using base_type = F;
private:
  F base;
  mutable std::unordered_map< std::tuple<std::decay_t<Args>...>, R, tuple_hash<Hash> > cache;
public:
  
  template<class... Ts>
  R operator()(Ts&&... ts) const
  {
    auto args = std::make_tuple(ts...);
    auto it = cache.find( args );
    if (it != cache.end())
      return it->second;

    auto&& retval = base(*this, std::forward<Ts>(ts)...);

    cache.emplace( std::move(args), retval );

    return decltype(retval)(retval);
  }
  template<class... Ts>
  R operator()(Ts&&... ts)
  {
    auto args = std::tie(ts...);
    auto it = cache.find( args );
    if (it != cache.end())
      return it->second;

    auto&& retval = base(*this, std::forward<Ts>(ts)...);

    cache.emplace( std::move(args), retval );

    return decltype(retval)(retval);
  }

  memoizer(memoizer const&)=default;
  memoizer(memoizer&&)=default;
  memoizer& operator=(memoizer const&)=default;
  memoizer& operator=(memoizer&&)=default;
  memoizer() = delete;
  template<typename L>
  memoizer( wrap, L&& f ):
    base( std::forward<L>(f) )
  {}
};

template<class Sig, class F>
memoizer<Sig, std::decay_t<F>> memoize( F&& f ) { return {wrap{}, std::forward<F>(f)}; }

live example with a hard-coded hash function based off this SO post.

auto fib = memoize<size_t(size_t)>(
  [](auto&& fib, size_t i)->size_t{
    if (i<=1) return 1;
    return fib(i-1)+fib(i-2);
  }
);
3
  • @Yakk Great, looks good! One small question. It is probably the only way to achieve memoization for recursive functions, but what about regular functions? How do you make it work with a non-recursive function?
    – Călin
    Aug 5, 2015 at 12:53
  • I would use a different approach. Or I'd write a wrapper that discards the first argument. Aug 5, 2015 at 18:59
  • Let us continue this discussion in chat.
    – Călin
    Aug 5, 2015 at 20:22
6

I struggled with the same problem. I created macro that also support (with small modification in recursive code) recursion. Here it is:

#include <map>
#include <tuple>
#define MEMOIZATOR(N, R, ...)                               \
R _ ## N (__VA_ARGS__);                                     \
std::map<std::tuple<__VA_ARGS__>, R> _memo_ ## N;           \
template <typename ... Args>                                \
R N (Args ... args) {                                       \
    auto& _memo = _memo_ ## N;                              \
    auto result = _memo.find(std::make_tuple(args...));     \
    if (result != _memo.end()) {                            \
        return result->second;                              \
    }                                                       \
    else {                                                  \
        auto result = _ ## N  (args...);                    \
        _memo[std::make_tuple(args...)] = result;           \
        return result;                                      \
    }                                                       \
}                                                           

The usage is really simple:

MEMOIZATOR(fibonacci, long int, int);

long int _fibonacci(int n) { // note the leading underscore 
                             // this makes recursive function to go through wrapper
    if (n == 1 or n == 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(40) // uses memoizator so it works in linear time 
              // (try it with and without memoizator)

See it in action: http://ideone.com/C3JEUT :)

5

Although @KerrekSB posted a link to another answer, I though I'd throw my answer in the ring as well (it's probably slightly less complicated than the linked answer, although in essence it's very similar):

#include <functional>
#include <map>
#include <tuple>
#include <utility>

/*! \brief A template functor class that can be utilized to memoize any 
*          given function taking any number of arguments. 
*/
template <typename R, typename... Args>
struct memoize_wrapper
{
private:

    std::map<std::tuple<Args...>, R> memo_;
    std::function<R(Args...)> func_;

public:

    /*! \brief Auto memoization constructor.
     *  
     *  \param func an the std::function to be memoized.
    */
    memoize_wrapper(std::function<R(Args...)> func)
      : func_(func)
    { }

    /*! \brief Memoization functor implementation.
     *  
     *  \param a Argument values that match the argument types for the 
     *           (previously) supplied function. 
     *  \return A value of return type R equivalent to calling func(a...).
     *          If this function has been called with these parameters
     *          previously, this will take O(log n) time.
    */
    R operator()(Args&&... a)
    {
        auto tup = std::make_tuple(std::forward<Args>(a)...);
        auto it = memo_.find(tup);
        if(it != memo_.end()) {
            return it->second;
        }
        R val = func_(a...);
        memo_.insert(std::make_pair(std::move(tup), val));
        return val;
    }

}; //end struct memoize_wrapper

Edit: Example usage:

Edit2: As pointed out, this doesn't work with recursive functions.

#include "utility/memoize_wrapper.hpp"
#include <memory>
#include <vector>
#include <algorithm>
#include <iostream>

long factorial(long i)
{
    long result = 1;
    long current = 2;
    while(current <= i) {
        result *= current;
        ++current;
    }
    return result;
}

int main()
{
    std::vector<int> arg {10, 9, 8, 7, 6, 10, 9, 8, 7, 6};
    std::transform(arg.begin(), arg.end(), arg.begin(), memoize_wrapper<long, long>(factorial));
    for(long i : arg) {
        std::cout << i << "\n";
    }
}
6
  • Can you give an example usage of the above?
    – akrohit
    Jul 23, 2013 at 9:37
  • I think this is buggy. You forward the arguments 2 times. (look at stackoverflow.com/a/7257307/1918154) Jul 23, 2013 at 9:55
  • @akrohit Added an example.
    – Yuushi
    Jul 23, 2013 at 10:36
  • 8
    Funny that you use recursive factorial as the example. It perfectly shows that the recursive invocations don't use memoized results, which means that, since the vector is in decreasing order, no memoized result is ever used in this example program (see coliru.stacked-crooked.com/…). Jul 24, 2013 at 12:42
  • @R.MartinhoFernandes You're 100% right. Don't know why I didn't think about that when I wrote it.
    – Yuushi
    Jul 26, 2013 at 2:40
2

Below is a (thread safe) C++17 function template that acts like std::invoke but memoizes the result:

/**
 * @brief      Drop-in replacement for std::invoke which memoizes the return
 *             result.
 *
 * @param[in]  function  The function whose result needs to be cached
 * @param[in]  args      The function arguments
 *
 * @tparam     Function  The function type
 * @tparam     Args      The argument types
 *
 * @return     A value obtained either by evaluating the function, or by
 *             recalling it from a cache.
 *
 * @note       The function provided must not be a type-erase function object
 *             like a raw function pointer or std::function, because this
 *             function depends on the uniqueness of the Function template
 *             parameter. If you were to call invoke_memoized(f, a) and
 *             invoke_memoized(g, b) in the same translation unit, where f and g
 *             were function pointers of the same type, and a and b were
 *             arguments of the same type, you'd end up using the same cache for
 *             both functions f and g. A reasonable attempt is made to detect
 *             these misuse cases via static_assert.
 */
template<typename Function, typename... Args>
auto invoke_memoized(Function function, Args... args)
{
    using key_type   = std::tuple<Args...>;
    using value_type = std::invoke_result_t<Function, Args...>;

    static_assert(! std::is_same_v<Function, std::function<value_type(Args...)>>,
        "cannot memoize on std::function (use a lambda instead)");

    static_assert(! std::is_same_v<Function, value_type(*)(Args...)>,
        "cannot memoize on function pointer (use a lambda instead)");

    static std::mutex mutex;
    static std::map<key_type, value_type> cache;

    auto key  = std::tuple(args...);
    auto lock = std::lock_guard<std::mutex>(mutex);

    if (cache.count(key))
    {
        return cache[key];
    }
    return cache[key] = std::apply(function, key);
}

You can use it like this:

auto c = invoke_memoized(std::plus<>(), 1, 2.3);

A static cache is maintained for each combination of the function object and argument types. As noted std::function and raw function pointers are rejected, as type-erased functions would get their caches mixed up. You can easily modify this function to impose limits on the cache size.

1
  • Probably an unordered_map instead of the regular std map would be more efficient ( although requires hashing)
    – Llopeth
    Oct 28, 2020 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.