Wow, Perl’s is cool. Try this:

   use Memoize;
   sub fib {
      my $n = shift;
      print "called fib($n)\\n";
      return $n if $n < 2;
      fib($n-1) + fib($n-2);
   print fib(5) . "\\n\\n";
   memoize( 'fib' );
   print fib(5) . "\\n\\n";

It does two different things:

  1. It wraps the function with a caching version.
  2. It replaces all calls to the function with calls to the memoized version. This includes the recursive calls inside the function itself.

It does all of this without requiring any source-level changes to the memoized function. This makes it easy to accelerate any referrentially-transparent function. Just don’t do something dumb like memoize print() or time().

With C++ I can mimic #1, but not #2. It’s a shame, because #2 is the cool part. With my C++ implementation, I only speed up identical repeated calls:

   fib(5);  // slow: makes 14, mostly-redundant, recursive calls
   fib(5);  // fast: purely a look up
   fib(4);  // slow
   fib(6);  // slow

Perl does much better:

   fib(5);  # fast: makes 5 recursive calls
   fib(5);  # fast: purely a look up
   fib(4);  # fast: purely a look up
   fib(6);  # fast: picks up where fib(5) left off

I’m somewhat bugged that I couldn’t duplicate this behavior with C++. Perl needn’t reach into it’s “dynamic language” bag of tricks to achieve this. It just provides access to the symbol table:

   sub a() { print "a\\n"; }
   sub b() { print "b\\n"; }
   *a = \\&b;
   a();     # prints b

3 Responses to “”

  1. 1 Weimin Chen June 5, 2006 at 9:58 am

    What happens if a fuction causes side effect? For example, if I add a line “$count++” to fib to count the number of calls, will Memorize produce different value of $count?

  2. 2 Mark June 6, 2006 at 8:05 am

    The side-effect will be inhibited in the cached cases, so your count will work as expected.
    Memoize only makes most sense on “pure” functions that have no side-effects, with the possible exception of side-effects intended to measure the memoization,

  1. 1 mark++ » Blog Archive » Memoize.cpp Trackback on June 9, 2006 at 7:22 am
Comments are currently closed.

%d bloggers like this: