Apr
17

Function Memoization in Actionscript Paul

Actionscript

Lets say you’ve got a grid based game and you’re using a path finding algorithm to get from cell A to B. You’re making path finding calculations several times per frame, and its starting to become a burden on your processor. You know your path finding algorithm is reasonably optimized and you won’t get huge performance boosts from tinkering with its internals, so what can you do to speed up your game? Well, if the conditions are right, we can use memoization and get a dramatic performance boost that should save the day.

What is memoization?

As always, Wikipedia offers a great overview:

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.

Basically, you have a function that takes inputs and produces an output. If those inputs have been used before, we can look up the cached result instead of re-computing the costly function.

When should I use it?

Whenever you have a function that is expensive to run you should consider using memoization. However, you can’t memoize every function. First, a memoizable function must be pure. This means that it shouldn’t cause side-effects, which happen when a function changes data outside of its scope. For instance, a function is un-memoizable if it changes class level variables or dispatches an event. Here are some examples of what I’m talking about:

Memoizable:

function(a:int, b:int):int { 
	return a + b;
}

The function above will do the exact same thing every time we call it with the same inputs.

Un-Memoizable:

var counter : int = 0;
function(a:int, b:int):int {
	counter++; 
	return a+b; 
}

This function will do something just a little bit different each time we call it with the same inputs, making it un-memoizable.

An AS3 Implementation

Now that you’re familiar with the basics, lets go about implementing a somewhat generic implementation in as3.

/**
 * Takes a function defined with only primitive arguments and returns
 * a new memoized version that avoids repeating the calculation of 
 * results for previously-processed input
 */
function memoize(fn:Function):Function {
	// lookup dictionary for our cached results.
	var cache : Object = {};

	// creates the memoized function that is returned. It will check for 
	// cached results and if one doesn't exist it will call the original function.
	return function(...args):* {
		var memoized : Function = function(...args):* {
			// generates a quick and dirty hash 
			// from our arguments that we can use to look up results
			// Because of this hash, arguments of memoized functions
			// can only be primitives!
			var key : String = "";
			for(var i : int = 0; i < args.length; i++) {
				if(typeof args[i] == "object" ) {
					throw new ArgumentError("This version of memoize() " + 
						"only works on functions with primitive arguments.");
				}
				key += args[i].toString();
			}
			
			// we've been down this road before. Quick, return our cached result!
			if(cache[key]) {
				return cache[key];
			} else {
				// Well, these inputs are new. Compute the result for the first time 
				// and store it in our lookup. Then we pass back the result.
				var result : * = fn.apply(null, args);
				cache[key] = result;
				return result;
			}
		}
		
		return memoized.apply(null, args);
	};
}

While this may look complicated (doubly nested anonymous functions always raise a few eyebrows) not a whole lot is going on here. First, we create a cache object we can store our computed results on. Then, we build our memoized version of the function that was passed in.

In order to determine if the function has been called once with the same inputs we build a hash of our arguments by just toStringing them together. This is the key mechanic of memoization, and it is what lets us do fast lookups on pre-computed values. For instance, if we pass in (1,2,3) as arguments the generated hash will be "123" and the next time (1,2,3) is used the same hash is built and we can fetch the result from our cache instead of computing it.

It is important to note that the method above only works for pure functions that have primitive arguments. This is because the hash function uses toString() on the arguments which always returns the same thing for types that extend Object even if they are two different objects of the same type. For instance, if you were to pass in a MovieClip, toString() would yeild "[object MovieClip]", and passing in a second, different MovieClip you'd get the same thing on toString() producing the same key for two different inputs.

You can get around this limitation by overriding toString on your custom objects, or by changing the hash function to serialize arguments that are object to strings. While this is a bit outside the scope of this article I'll be addressing it in an upcoming one.

Anyway, lets see our memoization method in action using the highly contrived but standard example of the Fibonacci sequence. First, we define our fibonacci function that has no side effects:

function fib(x:Number):Number {
	return (x < 2) ? (1) : (fib(x-1) + fib(x-2))
}

Now we can memoize it and test its execution time. Our test calls memoizedFib 5000 times with a random number up to 20:

var memoizedFib : Function = memoize(fib);

var startTime : int = getTimer();
for(var i:int = 0; i < 5000; i++)
{
	memoizedFib( Math.round( Math.random() * 20 ) );
}
trace("Memoized Fibonacci Sequence: " + (getTimer() - startTime));

And here are the results:
Memoized Fibonacci Sequence: 39ms
Unmemoized Fibonacci Sequence: 1,542ms

Ok, so this example may have been a bit contrived but you can see that for functions with finite input sets that are expensive to run, memoization can dramatically improve performance. Don't feel limited to crunching numbers either, I often implement a variation of memoization on service calls that fetch data from the server, saving you the time of a round trip over the net!

The above solution isn't a one-size-fits all answer, but its a good place to start. It's important to evaluate how a function will be used and how best to cache its results in order to get the best performance improvements while still striking a balance between execution time and memory consumption.

This entry was posted on Sunday, April 17th, 2011 at 12:40 pm and is filed under Actionscript. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.