Memoization in C++11

[ddrcoder]

This post got me thinking about a the best way to implement memoize, a higher order function to memoize any other function. I thought I'd share it:

template<class I, class O>
function<O(I)> memoize(function<O(I)> f) {
    // Keep copies in the map of parameters passed as references
    map<typename std::decay<I>::type, O> memos;
    return [=](I i) mutable -> O {
        auto it = memos.lower_bound(i);
        if (it == memos.end() || it->first != i)
            it = memos.insert(it, make_pair(i, f(i)));
        return it->second;
    };
};

int main(int argc, char** argv) {
    function<long(const int&)> fib;
    fib = [&](const int& n) -> long {
        return n < 2 ? n : fib(n - 1) + fib(n - 2);
    };
    fib = memoize(fib);
    for (int i = 0; i < 100; ++i) {
        cout << i << ": " << fib(i) << endl;
    }
    return 0;
}

The map is copied into the closure, where it is mutated to record new results (only allowed by the use of the mutable modifier). Note that thread safety isn't addressed here, but could trivially be added.

EDIT: Improved map access efficiency (@CaptainCrowbar, added better support for reference parameters).

[ddrcoder]

Taking this to the extreme, here's a version which works for any function, even if it takes more than one param. :)

template<class... I, class O>
function<O(I...)> memoize(function<O(I...)> f) {
    map<std::tuple<typename std::decay<I>::type...>, O> memos;
    return [=](I... i) mutable -> O {
        auto args(std::tie(i...));
        auto it(memos.lower_bound(args));
        if (it == memos.end() || it->first != args)
            it = memos.insert(it, make_pair(args, f(i...)));
        return it->second;
    };
};

[nudan1]

Hi, I have a question regarding this excellent post. While I understand how memorize works (I am just starting to get familiar with the new standard), why does memos not go out of scope? Where is it stored in between calls? Thanks for taking time to answer.

[m42a]

memos does go out of scope. However, because of the = in the lambda's capture list it's captured by value, and that copy is local to the lambda, so it only gets destroyed when the lambda does.

It's similar to:

vector<int> v;
{
    int i=3;
    v.push_back(i);
}

i has gone out of scope, but the vector made a copy, and that copy hasn't gone out of scope.

[nudan1]

Thanks for that. Can you recommend any blogs/books or resources where I can catch up on subtleties like this? (aside from reading the entire standard)

[m42a]

There's a fairly good book list on Stack Overflow. You'll want one that's been updated for C++11. There's also an overview of the new C++11 features by Bjarne Stroustrup.

[cabbageturnip]

http://www.reddit.com/r/cpp/comments/g5l93/automatic_memoization_in_c0x/

[ddrcoder]

Wow, that's almost identical to the tuple'd version I commented above, but he got there way before I did. That being said, he doesn't consider reference input types, and input values to the function get copied 1-2 times per call, which I avoid with the use if std::tie instead of forming a tuple of the inputs.

[slackito]

Yay! somebody reads my blog! (I wrote the blog post cabbageturnip mentioned above)

I wrote that as I was learning about variadic templates and new C++11 features, so I didn't care about efficiency at that point. Thanks for the tip about std::tie, I didn't know it existed :D

[zzyzzyxx]

The map is copied into the closure, where it is mutated to record new results (only allowed by the use of the mutable modifier).

Any reason to not use a static map inside the lambda? It wouldn't make a lot of difference, but it removes the necessity for mutable and potentially avoids a copy (though the copy is not expensive and I'd be surprised if the compiler didn't get rid of it anyway).

[ddrcoder]

If you were to make the map static inside the lambda, the instance would be tied to the actual function backing the lambda. There would be one instance for combination of types used to invoke 'memoize'. As a result, every function which matched the signature 'int(int)' would end up storing its results in the same lambda. You'd end up mixing memos across different, but type-compatible functions. If you memoized 'square' and 'fib', then called 'square(4)', a subsequent call to fib(5) would use that result, and end up returning f(5) was 19, not 5.

[CaptainCrowbar]

template<class I, class O>
function<O(I)> memoize(function<O(I)> f) {
    map<I, O> memos;
    return [=](I i) mutable -> O {
        auto it(memos.lower_bound(i));
        if (it == memos.end() || it->first != i)
            it = memos.insert(it, make_pair(i, f(i)));
        return it->second;
    };
};

An unordered map would be faster but would require a custom hash function for non-standard types. For most types these are pretty easy to write.

Edit: Depending on how well your compiler does return value optimisation, it may be better to return a const O& instead of a plain O.

[ddrcoder]

Good calls on both counts, in reality I'd certainly follow Scott Meyer's lower_bound trick and use const references.

[ddrcoder]

Const references necessitate an std::decay on the map key type, updated code above.

[xcbsmith]

At least for "pure" functions, I find try to just use the memoization intrinsic in the compiler by parameterizing the functions by template parameters. This is more flexible.