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?

Justin
  • 24,288
  • 12
  • 92
  • 142
akrohit
  • 1,023
  • 1
  • 10
  • 14
  • 9
    Maybe [this answer](http://stackoverflow.com/a/9729954/596781) is of interest to you. – Kerrek SB Jul 23 '13 at 09:15
  • 2
    I think Sumanth Tambe comprehensively treated this topic in his blog post: http://cpptruths.blogspot.nl/2012/01/general-purpose-automatic-memoization.html – sehe Jul 24 '13 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 05 '14 at 21:00

5 Answers5

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.

JohannesD
  • 13,802
  • 1
  • 38
  • 30
  • 13
    Could you also post an example usage for this? – akrohit Jul 23 '13 at 11:26
  • Will this for for recursive methods also? – akrohit Jul 23 '13 at 11:31
  • 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. – R. Martinho Fernandes Jul 24 '13 at 12:36
  • @R.MartinhoFernandes could this be fixed by making `table` a threadlocal, and then wrapping the whole thing in a create thread followed by a .join? – soandos Jul 24 '13 at 17:37
  • 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. – Peter Huene Jul 24 '13 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 '13 at 20:43
  • Maybe this can be fixed using the [Y-combinator](http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator) or some analogon from typed lambda calculus? I would be really interested in that – Niklas B. Mar 15 '14 at 19:01
  • 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(atoi)("42")` – Joe Sep 06 '14 at 17:14
  • @NiklasB. I implemented a y-combinator-esque based memoizer below, if you are curious. – Yakk - Adam Nevraumont Jun 18 '15 at 20:34
  • This seems to break if you pass in a reference to a std::unique_ptr. Make sure the template types are the return type and then the arg types to the callback you pass in. – TankorSmash Apr 20 '19 at 23:48
  • I think an improvement over this answer would be have only one return statement, in order to make use of return value optimization. In order to do that instead of using operator[] , do memoized=table.insert(...).first and return memoized unconditionally – Llopeth Mar 11 '21 at 08:30
24

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);
  }
);
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • 1
    Seems very nice. Could you maybe add a short example of a memoized function? – Niklas B. Jun 19 '15 at 10:18
  • How is the Sig type inferred in the memoize function template? I tried it and it fails right there. Can you show a working example of your code, maybe sharing the code on coliru or some other online compiler? That would be really useful. Thank you! – Călin Aug 05 '15 at 07:55
  • @CălinCruceru The answer is simple: `Sig` is not inferred. You have to pass it. `Sig` both tells the memoizer what things to store as a key in the key-value pair for the unordered map, and the return value. You could deduce the return value, but I didn't see why I'd do that. – Yakk - Adam Nevraumont Aug 05 '15 at 11:21
  • @Yakk then your above example doesn't work. It should be memoize(fib_base). – Călin Aug 05 '15 at 11:34
  • @CălinCruceru Good point. Deleted example, added example with more correct syntax, live example added. – Yakk - Adam Nevraumont Aug 05 '15 at 11:36
  • @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 05 '15 at 12:53
  • I would use a different approach. Or I'd write a wrapper that discards the first argument. – Yakk - Adam Nevraumont Aug 05 '15 at 18:59
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/85239/discussion-between-clin-cruceru-and-yakk). – Călin Aug 05 '15 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 :)

jendas
  • 138
  • 1
  • 10
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";
    }
}
Yuushi
  • 25,132
  • 7
  • 63
  • 81
  • Can you give an example usage of the above? – akrohit Jul 23 '13 at 09:37
  • I think this is buggy. You forward the arguments 2 times. (look at http://stackoverflow.com/a/7257307/1918154) – Jan Herrmann Jul 23 '13 at 09:55
  • @akrohit Added an example. – Yuushi Jul 23 '13 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 http://coliru.stacked-crooked.com/view?id=3c6ec65d5df3b4d1a24d007afbb5fcbf-80c199070668c72f0a5e12e38239d72b). – R. Martinho Fernandes Jul 24 '13 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 '13 at 02:40
  • A couple of points: 1) At least in vs2017 binding lvalue to rvalue ref causes compile error at R operator()(Args&&... a). Removing && fixes it. 2)memoization in this code sample is working as intended. Being recursive is not relevant to this issue. To use memoization at factorial() level, it should be done inside the factorial() – rezeli Dec 14 '18 at 08:36
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.

Jonathan Zrake
  • 603
  • 6
  • 9
  • Probably an unordered_map instead of the regular std map would be more efficient ( although requires hashing) – Llopeth Oct 28 '20 at 14:36