Boost logo

Boost :

Subject: [boost] Interest check: memoization
From: James Porter (porterj_at_[hidden])
Date: 2009-01-24 21:39:24


After hacking around with some simple dynamic programming, it occurred
to me that it should be possible to write a simple class template to
handle memoization of functions. With the changes in C++0x that help
solve the forwarding problem, writing a generic memoizer should be
fairly straightforward. (Or so I thought!)

The interface is straightforward, so I'll let the following code snippet
speak for itself:

        memoizer<int (int,int)> memo(my_func);
        int ret = memo(i,j);

As you'd expect, this creates a memoizer that caches results of calls to
my_func. Pretty simple, right? Well, not exactly. :)

(If you'd rather not read about the implementation, you can skip ahead
to the end, where there is a link to download the source.)

There are a number of issues that make this a fairly complicated
problem, even with the improved generic programming facilities in C++0x.
Chief among these is copying. With the naive implementation of the
memoizer, I found that calculating the result of an unmemoized value
created 3 copies (one for creating a tuple to search a map for, and two
to insert the tuple into the map), and returning a memoized value
created 1 copy (to create a tuple to search the map).

To make a long story short, I set about trying to reduce the number of
copies to the expected amount: 1 copy for unmemoized values and 0 for
memoized values. I'm happy to say that this was a success! The trick was
creating a tuple that holds references to each argument and can be
upgraded to hold the arguments by value. In this way, we can compare by
reference and store by value. This is simple on the surface, but
requires some care when dealing with rvalue references.

There are also issues with passing convertible types to the memoizer
(e.g. passing floats when the function expects ints). For complicated
types, you certainly wouldn't want to copy them more than once, and
you'd want to use move constructors where possible. This is resolved
with some creative manipulation of template types (lines 52-58 of
memoizer.hpp).

There are still a number of things missing in this code, such as the
ability to use function objects with the memoizer, or the ability to
specify the map type, but I believe that the most important issues are
resolved:

* Minimizes copying of arguments
* Supports move constructors wherever possible
* Safely converts arguments to the appropriate types

The full source code for this is available here (requires gcc 4.3 or a
compiler that supports variadic templates and rvalue refs):
http://www.teamboxel.com/misc/memoizer.tar.gz

Comments and criticisms are welcome. If there's interest, I will - of
course - work on a version that supports the current C++ standard.

- Jim


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk