Automatic memoization in C++0x
Memoization is a pretty well-known optimization technique which consists in “remembering” (i.e.: caching) the results of previous calls to a function, so that repeated calls with the same parameters are resolved without repeating the original computation.
Some days ago, while trying to show a colleague the benefits of a modern high-level language like Python over C++, I came up with the following snippet:
1 2 3 4 5 6 7 | def memoize(fn): cache = {} def memoized_fn(*args): if args not in cache: cache[args] = fn(*args) return cache[args] return memoized_fn |
It is a small function which takes a function as its only parameter, and returns a memoized version of that function. It is short, it shows some interesting Python features, like built-in dictionaries and tuples, or functions as first-class objects, and it should be pretty readable.
To make a fair comparison I needed to code a C++ version too. I was thinking about writing, just to prove my point, the classic boilerplate-filled template to create a function object, and using typelists and compile-time recursion to allow an arbitrary number of parameters. But it would have been quite boring. Also, it turns out that, with the upcoming C++ standard supporting lambda functions, tuples and variadic templates, it is possible to get rid of most of the boilerplate and use pretty much the same functional approach. Moreover, gcc 4.5 already supports these things, so I decided to give it a go:
1 2 3 4 5 6 7 8 9 10 11 | template <typename ReturnType, typename... Args> std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func) { std::map<std::tuple<Args...>, ReturnType> cache; return ([=](Args... args) mutable { std::tuple<Args...> t(args...); if (cache.find(t) == cache.end()) cache[t] = func(args...); return cache[t]; }); } |
Tricky things to note about the C++ version:
- The new lambda syntax: the equals sign in
[=]
means “capture local variables in the surrounding scope by value”, which is needed because we are returning the lambda function, and the local variable will disappear at that moment, so we can’t hold a reference to it. As we are capturing by value and we pretend to change this captured value, the function should be marked asmutable
(see “Appearing and disappearing consts in C++” by Scott Meyers) - Lambda functions are function objects of implementation-dependent type, so we need to use std::function as the return type from memoize() to wrap our lambda.
I still like the Python version better, as it looks cleaner to me, but I’m glad the new features can help us reduce the amount of boilerplate where switching to newer languages is not possible (sometimes you just NEED the extra speed). Kudos to the C++ standards committee for the improvements and the gcc team for keeping up with them.
EDIT (2011/03/21): Thanks everyone for the feedback, both in the comments here and in the reddit thread. Some additional notes:
- Here you have the complete sample file. I tested it under g++ 4.5.2 on MinGW, with -std=c++0x.
- This is a proof of concept, which I did to become familiar with the new language features. As some people pointed out, a map is not the best data structure to use as a cache (it has O(log n) lookups). You will probably do better if you use a hash map (like the new
std::unordered_map
in C++0x). I chose map just for the sake of clarity. Also, you will need to define anoperator<
for any type you would like to use (or a hash function for unordered_map). - There were also suggestions to use
lower_bound
orequal_range
to avoid the second map lookup and use the resulting iterator also as an insertion hint. I thought about saving the result in a local variable to avoid another lookup, but I wanted it to be as close as possible to the python version, just for clarity. I also didn’t know about these functions, so thanks for the tip! :D - Some people also pointed out that this example doesn’t work with recursive functions. That’s completely true. In this post on stackoverflow the user larsmans suggests that I’m leaving the implementation of a fixed-point combinator as an exercise to the reader. Maybe it would be a good exercise for the writer, too… if I’m able to write something like that it will surely deserve its own post ;D
Michal Mocny Said,
March 17, 2011 @ 02:41
Oh I am going to have a lot of fun with this tonight :)
Kudos to you for playing with the new C++ features. I will post back results if I run into issues with this code.
Michal Mocny Said,
March 17, 2011 @ 03:05
First test I tried was with Fibonacci, and it doesn’t work the way I naively expected, because of course the memoizing wrapper calls the original, unmemoized function internally.
The python version suffers the same fate, of course.
I had a few tweaks I needed to make to compile your code, which are possibly just due to my compiler support for c++0x.
Grégory LEOCADIE Said,
March 17, 2011 @ 08:02
Hi thank you for this article.
Could you provide a version without C++0x features please?
I’m not very fond of the C++ syntax for lambdas (I’m coming from OCaml, Haskell…worlds) but, IMHO, it’s good to add this feature to the language.
;)
SimonYe Said,
March 17, 2011 @ 08:44
Seems there is a snag.
The lambda object capture the cache by value. Each time the lambda object create, it has the empty cache. So the code seems doesn’t work.
How about defining the cache as static, and lambda capture it by reference.
admin Said,
March 17, 2011 @ 10:19
Yes, it doesn’t play well with recursive functions, and I can’t think of an easy fix.
The python version HAS an easy fix, try
fib=memoize(fib)
;DPpluX Said,
March 17, 2011 @ 10:40
This is a very good talk about lambdas (by Herb Sutter)
http://player.microsoftpdc.com/Session/ab8fe309-861b-4bc0-b9f1-0398f5a5cba4
The good thing is lambdas are far from “magical” objects, it has a very clear translation to old fashion code (is “almost” syntactic sugar).
Victor Bogado Said,
March 17, 2011 @ 15:09
Without c++0x features it still possible to do the same, but you would have to declare a template functor class that would hold the cache, and that class would be different for each number of arguments in your function. Feasible, but much larger code.
Afief Said,
March 17, 2011 @ 15:13
Is the link available in non-silverlight format for the rest of the world?
Boris Said,
March 18, 2011 @ 02:13
VS took a stab at this a couple of years ago too (sans variadic templates): http://blogs.msdn.com/b/vcblog/archive/2008/11/18/stupid-lambda-tricks.aspx
C++0x is definitely great stuff.
Dietmar Kuehl Said,
March 18, 2011 @ 11:49
Making the cache static does NOT work: this would share the cache between all function objects with the same return type and parameter types. This is almost certainly not desired: while memoizing the results between calls for the same function object is a fairly local decision, using a static object is not.
That said, the cache is actually copied by value into the lambda function object and the cache accessed inside the lambda function is essentially a member variable of the lambda function. Thus, there is no need to make the cache static anyway.
petke Said,
March 18, 2011 @ 13:38
Nice code. I wish VS2010 supported variadic templates.
Like SimonYe pointed out though. I cant see this code working. Cache should be a static local variable, otherwize nothing will be retained between calls. Also you should not capture by value (even if it is mutable) as again that means nothing is retained between calls. Capture cache by reference instead.
petke Said,
March 18, 2011 @ 14:03
Never mind my last comment. I see now that your intention is for the return value of memoize to be reused, not the memoize function itself. Very clever.
qosys Said,
March 18, 2011 @ 16:03
Can someone post complete code of the working C++0x memoization sample?
trying to use it with gcc 4.5 (-std=c++0x), but always getting errors.
Xavier Said,
March 18, 2011 @ 21:31
Very nice post! C++0x allows really impressive things…
I’m pretty sure we still have to discover many interesting ways to combine its new features…
SimonYe Said,
March 19, 2011 @ 08:47
I think i misunderstand your intention.
After googling, I find a more detailed memoize sample in python.
http://code.activestate.com/recipes/52201/
I have make this memoization sample works in gcc4.5.2. It’s great.
sample code:
auto tmp = memoize( (std::function(myfunc ) ) );
cout<<tmp(1, 2)<<endl;
cout<<tmp(1, 2)<<endl;
So, to make this memoization take effect, we need to store the memoize's return (I thinks that's why we don't the cache static).
Thanks for your great post!