Tuesday, October 21, 2008 10:01 AM bart

Memoization for dummies

Introduction

We’ve been talking about functional programming quite a bit already. One of the things used frequently in functional programming is recursion, instead of imperative loop constructs. Both have their advantages, but often recursive techniques can cause significant degradations in performance. The prototypical sample is the computation of the Fibonacci sequence (a typical interview question, too). In mathematical terms, Fibonacci is expressed as:

fib : N –> N

fib 1 = 1
fib 2 = 2
fib n = fib (n – 1) + fib (n – 2), n > 2

Translating this directly into functional style of code yields the following (F#):

let rec fib n =
   if n <= 2 then
      1
   else
      fib (n – 1) + fib (n – 2)

or, in C# 3.0,

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

The reason we need to spread this across two lines is interesting by itself. If we don’t do this, the following error appears:

memoize.cs(17,48): error CS0165: Use of unassigned local variable 'fib'

referring to the highlighted position in the code:

Func<uint, uint> fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

The reason this error pops up is because we’re defining a function in terms of itself, something that’s invalid in a variable declaration/assignment in C#, just like the following is invalid:

int a = a + b;

F# addresses this through the use of the rec keyword, but that’s a separate discussion. But what are we doing really when declaring the following?

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

Here’s the answer:

image

Notice the <>c__DisplayClass1, a closure. When assigning the lambda on the second line to fib, we’re capturing the fib variable itself as it appears in the lambda’s body. In more detail, this happens:

image

On lines IL_0007 to IL_0009 we store null as the value for fib, immediately replacing it on lines IL_000e to IL_001b with a new function retrieved from <Main>b__0. This is where the code becomes self-referential:

image 

As you can see on lines IL_0005 and IL_0013 we’re loading the variable we got assigned to by Main (but this code by itself doesn’t know that) in order to call it 4 lines further on, through the delegate. The rest of this code is a trivial translation of the ternary operator. Why is the interesting at all? It turns out this will be fairly important further on in this article as we’ll want to tweak this function.

 

What’s memoization?

Looking at our Fibonacci sequence sample again, try to imagine the call tree that results from a call like fib(10). Or let’s simplify it, consider Fib(5). Here’s the call tree:

Fib(5)
Fib(4)
  Fib(3)
   Fib(2)
   Fib(1)
  Fib(2)
Fib(3)
  Fib(2)
  Fib(1)

We’re calculating things over and over again. So how can we solve this? First of all, by embracing an imperative style, at the cost of the more declarative natural mapping of the original recursive definition:

uint Fib(uint n)
{
   if (n <= 2)
      return 1;
   else
   {
      uint prev = 1;
      uint curr = 1;
      for (uint i = 0; i < n – 2; i++)
      {
         uint t = curr;
         curr += prev;
         prev = t;
      }

      return curr;
   }
}

You’ll agree that this encoding of the algorithm makes things more cumbersome and far more difficult and less obvious to grasp and understand due to the temporary variables etc. With memoization we’ll be able to keep our original functional definition (using recursion), while improving the performance. To accomplish this, we’re caching the function results and therefore we’re relying on an essential property of mathematical functions: given the same set of inputs, they always yield the same result. This also implies our to-be-memoized function should be side-effect free as we’ll shortcut the function’s computation body whenever we observe the same set of arguments (depending on the underlying caching technique and cache eviction policies, the number of computation invocations might even become unpredictable, therefore we shouldn’t rely on effectful computation).

 

Measuring success

Before we claim things like “10 times better”, we should establish a baseline for comparison and create a mechanism to measure our success. As usual, we’ll rely on the System.Diagnostics.Stopwatch class to do so:

static void Test(Func<uint, uint> fib)
{
   Stopwatch sw = new Stopwatch();
   sw.Start();

   var res = from x in Range<uint>(1, 40, i => i + 1) select new { N = x, Value = fib(x) };
   foreach (var i in res)
      Console.WriteLine("fib(" + i.N + ") = " + i.Value);

   sw.Stop();
   Console.WriteLine(sw.Elapsed);
}

In here I’m using a generalization of Enumerable.Range I find useful (although here there’s no real need to range of uint for the input, our function could well be Func<int, uint>):

static IEnumerable<T> Range<T>(T from, T to, Func<T, T> inc) where T : IComparable<T>
{
   for (T t = from; t.CompareTo(to) <= 0; t = inc(t))
   {
      yield return t;
   }
}

Actually you’d call Range “For” instead and it becomes very apparent what it’s all about, isn’t it? Let’s take a look how our current implementation does:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
Test(fib);

Yes, it’s fine to say it: in one word terrible

image 

Injecting the memoizer

As mentioned before, our strategy to tackle this inefficiency will be to trade instructions for memory, essentially keeping a cache of calculated values in some kind of cache. The built-in collection type that’s ideal for this purpose is obviously the generic Dictionary<K,T> in System.Collections.Generic. But how do we get it in our function definition seamlessly? In other words, given any function of arity 1 (meaning it takes in one argument, we’ll look at extending that further on), how can we sprinkle a little bit of memoization on top without changing the outer contract of the function? Here’s the code that allows us to preserve the signature but slice the memoizer in between the original function and the memoized one:

static Func<T, R> Memoize<T, R>(this Func<T, R> f)
{
   Dictionary<T, R> cache = new Dictionary<T, R>();
   return t => {
      if (cache.ContainsKey(t))
         return cache[t];
      else
         return (cache[t] = f(t));
   };
}

Actually this code can be optimized a little further using the TryGetValue method on the Dictionary class, and if you have more taste than me the else-block statement can be writter in a nicer way (if I was in a real evil mood, I’d have put it in a ternary operator conditional). I’ll leave such rewrites to the reader as an additional opportunity to express personal style :-).

Notice how the signature of the returned function is the same as the original on: that’s what makes our implementation seamless and transparent. I’m writing this as an extension method on Func<T, R>, but there’s no need to do it that way. What’s more important though is how it works internally. Again you can see closures at work, because what we’ve really created here is something that looks like this:

class Memoizer<T, R>
{
   private Dictionary<T, R> _cache = new Dictionary<T, R>();
   private Func<T, R> _f;

   internal Memoizer(Func<T, R> f)
   {
      _f = f;
   }

   internal R Invoke(T t)
   {
      if (cache.ContainsKey(t))
         return cache[t];
      else
         return (cache[t] = _f(t));
   }
}

You can look at it as lifting an existing function into the memoizer (one per function as we need a unique cache on a function-per-function basis). Obviously you’ll need similar implementations for other function arities (including the zero-argument function, typically used for delayed computation scenarios). Here another issue pops up: the lack of Tuple<T1, …, Tn> types (with proper implementations for Equals and GetHashCode) that would be useful in such a case to express the dictionary’s key type. Even more, the debate on how much generic overloads to provide (Action<T1, …, Tn>, Func<T1, …, Tn>, Tuple<T1, …, Tn>, etc) enters the picture again. Unfortunately the type system isn’t rich enough to have a “Tuple<params T[]>”. At runtime there are ways to get around this, but then we enter dynamic meta-grounds again, so let’s not deviate from our path this time and keep that discussion for another time.

 

Putting it to the test

Back to our original code:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
Test(fib);

Easy as it seems you might think the following will do the trick:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
Test(fib.Memoize());

but unfortunately you won’t see any noticeable effect by doing so. Why? Take a closer look at what’s happening. The code above is equivalent to:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

Memoizer<uint, uint> m = new Memoizer<uint, uint>(fib);
Func<uint, uint> fibm = new Func<uint, uint>(m.Invoke);
Test(fibm);

Now we’re calling through fibm, which results in invoking the Invoke method on the (simplified) memoizer’s closure class. But look what we’re passing in to the constructor: the original fib instance, which really is a public field on another closure as explained in the introduction paragraph. So ultimately we’re just memoizing the “outer” fib function, not the “inner” recursive calls. How can we make the thing work as we expect it to? Remember from the introduction paragraph why we needed the following trick?

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

The generated code stores fib in a closure class field <>c__DisplayClass1::fib. In fact, there’s no such thing as a local variable fib in the IL-code; instead all occurrences of fib have been replaced by ldfld and stfld operations on the closure class’s field. But what’s more is that the closure class’s <Main>b__0 method uses the same field for the recursive calls to fib (see the last figure in the introduction paragraph). That’s precisely what we need to know in order to make the memoizer work: if we assign the result of fib.Memoize() to fib again, we’re replacing the field value that’s also used in the recursive calls:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
fib = fib.Memoize();
Test(fib);

As a little quiz question: why can’t we write the following instead?

Func<uint, uint> fib = null;
fib = (n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2)).Memoize();
Test(fib);

And here’s the result:

image

Much better, actually much more than “10 times better”.

 

Additional quiz question

Would you be able to do all of this with expression trees, i.e. with the following hypothetical piece of code:

LambdaExpressiion<Func<uint, uint>> fibEx = null;
fibEx = n => n <= 2 ? 1 : fibEx(n - 1) + fibEx(n - 2);
// what now?
Test(fib);

Why (not)?

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# re: Memoization for dummies

Tuesday, October 21, 2008 1:09 PM by Jonathan Allen

Um, where are the timings for the imperative style?

I ask because I tried memorization in the past and found it to be much, much slower than simply recomputing.

# re: Memoization for dummies

Tuesday, October 21, 2008 3:43 PM by aL_

awsome yet noodle baking stuff :)

will you be posting the quiz awnsers by the way? :D

for the first one im guessing it has something to do with the fib variable not beeing captured by the closed but i cant quite fit all the bit together in my head :)

# re: Memoization for dummies

Tuesday, October 21, 2008 8:56 PM by bart

Hi Jonathan,

If by the words "relative style" you mean the relatively incomprehensible loop-based implementation, sure there will be significant difference (along the lines of one order of magnitude) and you'll be trading off in terms of memory. There are obviously things that can improve this, for example replacing Dictionary<K, T> (which doesn't have intrinsic knowledge about the characteristic of the function domain) by a specialized collection, at the cost of making the memoizer less generic.

In fact, if you're about to write the core of an all-for-performance piece of software (by which I mean something in the area of number crunching and database engines), you'll typically align as much as possible with the underlying machine (which is intrinisically imperative style, at least for all machines I know of), often at the cost of readability. The extreme of it is for example graphics software with low-level assembly code.

However, specifying the problem in a functional manner gives us the opportunity to reason more about the code, not only as humans but also in runtimes (ultimately of course also crafted by humans), so turning the algorithm in a parallel multi-core one will be easier. Things like the Task Parallel Library and Coordination Data Structures in the Parallel Extensions to the .NET Framework help doing so, as illustrated by PLINQ.

Thanks,

-Bart

# re: Memoization for dummies

Tuesday, October 21, 2008 9:10 PM by bart

Hi aL_,

Glad you like noodles (honestly I don't). I'll leave the second quiz question open for now, but give a golden tip for the first one: do lambdas have a type by themselves? Try to compile the following:

(() => 0).ToString()

Based on what you get back, try to insert a cast on the dots:

((...)(() => 0).ToString()

Sorry for all of the parentheses :-), oops another one slipped in that smiley. Let me know if the compiler outcome doesn't make sense.

Thanks,

-Bart

# re: Memoization for dummies

Wednesday, October 22, 2008 1:31 AM by aL_

aah ok i think im getting it... lambdas can be either expressions or delegates and the compile infers that from the type they're getting assigned to, so:

(() => 0).ToString()

doesnt compile because the compiler has no idea if it should call ToString() on an instance of Func<int> or Expression<Func<int>>

casting to an int

(int)( ( ) => 0 )

adds an additional hint as the error states that int "is not a delegate type"

the fact that the memoizer works while the dictionary is a local variable in the extension method is still something im trying to completly wrap my head around but i feel im on the brink of comprehention :) (but if you where to elaborate more on that i wouldnt object ;))

# re: Memoization for dummies

Wednesday, October 22, 2008 4:09 AM by JohanH

(() => 0) is a Func<int> isn't it?

but yea, according to the compiler (() => 0).ToString() complains about "Operator '.' cannot be applied to operand of type 'lambda expression'" so there is a "type" in a way :)

# re: Memoization for dummies

Wednesday, October 22, 2008 4:40 AM by Eamon Nerbonne

Actually, there multiple levels problems with the first question.

Something like

   var somefunc =  a=>a

Is illegal.

If you have

   public delegate R MyFunc<T, R>(T t);

then

MyFunc<int,int> myfunc = a=>a;

Func<int,int> func = myfunc;

Is illegal.  You can't circumvent this issue by first casting to Delegate and then casting back to Func<int,int> ... The compiler is simply unable to deal with delegates flexibly.

Of course, you can do:

Func<int, int> func = (Func<int,int>)Delegate.CreateDelegate(typeof(Func<int,int>),myfunc.Target,  myfunc.Method);

...but that's not exactly legible.

So how can the compiler be unable to recognize classes of delegates and yet still correctly infer the proper generic arguments to all those LINQ queries?  Exceptionally, lambda expressions are one of the few places the type of an expression is determined not from the inside out (i.e. (3+4.5) is always of type double, irrespective of context), but from the outside in: a lambda expression is mapped to whatever type the surrounding expression expects - if possible.

So, even if the compiler would somehow infer a general delegate signature from a lambda, it's currently not capable of casting delegates, and would therefore never be able to apply the extension method.

# Dew Drop - October 22, 2008 | Alvin Ashcraft's Morning Dew

Wednesday, October 22, 2008 8:25 AM by Dew Drop - October 22, 2008 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - October 22, 2008 | Alvin Ashcraft's Morning Dew

# re: Memoization for dummies

Wednesday, October 22, 2008 11:47 PM by Philippe

Func<int> myFunc = () => 0;

myFunc.ToString();

Expression<del> expr = () => 0;

expr.ToString();

where del is delegate int del();

Expression<Func<int>> expr2 = () => 0;

expr3.ToString();

Are all three valid. So my guess is that the compiler is not able to cast delegates, as said by Eamon.

# re: Memoization for dummies

Monday, October 27, 2008 1:15 AM by aL_

i dont think its fair to say that "the compiler can't" infer the type.. nobody can infer the type except for the programmer that knows what they want to get.

even if the c# compiler was completly dynamic and swallowed the code, what method should the runtime bind to? Func<int> or Expression<Func<int>>?

its an ambiguity of the language, not a flaw in the compiler imo..

# re: Memoization for dummies

Monday, October 27, 2008 6:55 PM by bart

Indeed, the type of a lambda is intentionally left unspecified (so I won't call it an ambiguity of the language either). The target of the assignment drives what the result should look like: an anonymous method or an expression tree.

Based on this observation, there's nothing to infer as the two are possible. Of course a default could be chosen, but that's not the way things were done; in the end, there's no betterness between "code as code" and "code as data", as long as we live in the world of von Neumann :-).

Thanks,

-Bart

# Stupid Lambda Tricks

Tuesday, November 18, 2008 11:22 AM by Visual C++ Team Blog

Hi. I’m Arjun Bijanki, the test lead for the compiler front-end and Intellisense engine. One afternoon

# Websites tagged "stopwatch" on Postsaver

Sunday, December 21, 2008 3:47 PM by Websites tagged "stopwatch" on Postsaver

Pingback from  Websites tagged "stopwatch" on Postsaver

# Recursive Fibonacci with F# : Philippe

Thursday, July 02, 2009 10:13 AM by Recursive Fibonacci with F# : Philippe

Pingback from  Recursive Fibonacci with F# : Philippe

# Lazy Evaluation in C# &laquo; xosfaere

Sunday, March 21, 2010 1:03 PM by Lazy Evaluation in C# « xosfaere

Pingback from  Lazy Evaluation in C# &laquo; xosfaere