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 (C#):
Func
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:
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
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 < t =" curr;" prev =" t;">
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
var res = from x in Range
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
static IEnumerable
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
static Func
{
Dictionary
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
class Memoizer
{
private Dictionary
private Func
internal Memoizer(Func
{
_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
Putting it to the test
Back to our original code:
Func
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
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
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2); Memoizer
Func
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
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
Func
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
fib = (n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2)).Memoize(); Test(fib); And here’s the result:
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
fibEx = n => n <= 2 ? 1 : fibEx(n - 1) + fibEx(n - 2); // what now? Test(fib); Why (not)?
