Boost logo

Boost :

Subject: Re: [boost] Interest check: memoization
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-01-25 18:50:06


----- Original Message -----
From: "James Porter" <porterj_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Sunday, January 25, 2009 3:39 AM
Subject: [boost] Interest check: memoization

>
> 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.

Hi,

The implementation is very elegant and the use of the C++0x facilities reduce the code to the minimum.

I remember that something like this was requested to the Flyweigth library. The following is extracted from the documentation: "
Example 5: flyweight-based memoization
Memoization is an optimization technique consisting in caching the results of a computation for later reuse; this can dramatically improve performance when calculating recursive numerical functions, for instance. Key-value flyweights can be used to implement memoization for a numerical function f by modeling a memoized invocation of the function as a value of type flyweight<key_value<int,compute_f> >, where compute_f is a type that does the computation of f(n) at its compute_f::compute_f(int) constructor. For instance, the Fibonacci numbers can be computed with memoization like this:

struct compute_fibonacci;
typedef flyweight<key_value<int,compute_fibonacci>,no_tracking> fibonacci;

struct compute_fibonacci{
  compute_fibonacci(int n):
    result(n==0?0:n==1?1:fibonacci(n-2).get()+fibonacci(n-1).get())
  {}

  operator int()const{return result;}
  int result;
};

  for(int n=0;n<40;++n){
    std::cout<<"F("<<n<<")="<<fibonacci(n)<<std::endl;
  }

The no_tracking policy is used so that the memoized computations persist for future use throughout the program. "

How both solutions compares?
    int fibonacci_impl(int n);
    memoizer<int (int)> fibonacci(fibonacci_impl);

    int fibonacci_impl(int n) {
        return (n==0?0:n==1?1:fibonacci(n-2)+fibonacci(n-1))
    }

    for(int n=0;n<40;++n){
        std::cout<<"F("<<n<<")="<<fibonacci(n)<<std::endl;
    }

We can memoize only unary functions with flyweight and have flyweight values with memoize(identity function). So which one perform better.

If I understand memoizer can be used only with pure functions, isn't it? Is there a way to check for a pure function in C++0X? Is there a way to constraint the template parameter to only pure functions?
Should the following compile?
    memoizer<int&& (int,int)> memo(my_func); // move result on calling
    int ret = memo(i,j);

Should the following compile?
    memoizer<int (int&,int)> memo(my_func); // allows to modify the first argument
    int ret = memo(i,j);

Some minor changes in
    typedef const Ret & result_reference;

will be needed to return references.
    memoizer<int& (int,int)> memo(my_func);
    int& ret = memo(i,j);

Best,
Vicente


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