Saturday, March 14, 2009

Memoization with Javascript

Memoization is somewhat common optimization where the results of a function are cached, so that subsequent calls to that same function, with the same arguments can skip the execution and return the object from cache. With interpreted languages, the savings of memoizing frequently called funcitons with a limited domain of arguments can save quite a bit of execution time. Obviously, you need to balance this speed with the amount of memory that your page will consume. Finding DOM objects is a pretty good application of memoization.


function memoize(obj, func) {
the_func = obj[func];
cache = {};

return function() {
var key = Array.prototype.join.call(arguments, '_');
if (!(key in cache))
cache[key] = the_func.apply(obj, arguments);
return cache[key];
}
}

var ElementFinder = {
findById: function(id) {
console.log('Calling Function with id: %s', id);
return document.getElementById(id);
}
}

ElementFinder.findById = memoize(ElementFinder, 'findById');

function load() {
for(var i=0;i<10;i++) {
console.log(ElementFinder.findById('my_div').id);
}
}

Tuesday, March 10, 2009

How Firefox 3.1 Uses Trace Trees to Optimize Javascript Runtimes

Version 3.1 of Firefox should be a pretty marked improvement for Javascript performance because of a compilation optimization that the Firefox team is putting in place for that release. Trace-based compilation identifies loops, and records frequently visited paths within those loops to determine what needs to be compiled.

Traditional Just-In-Time compilation usually happens at the method/function level, where the need for compilation is simply determined by whether or not the function/method has been visited. When a function is visited for the first time, the control flow graph for the entire function is created, then compiled into the proper instruction set. This could cause quite a bit of unnecessary overhead given the way that Javascript applications are delivered via the internets.

With trace compilation, the compiler first determines the loop headers, since most frequently called code usually exists within a loop. To determine loop headers, the compiler keeps a counter of back branches (ones that send control back to a previous location), and once that counter hits a certain threshold, that is identified as a "hot" trace. Subsequent paths starting at that loop header are then recorded and compiled.

In this scheme, the interpreter and the compiler are handing control back and forth to each other, which itself can be somewhat expensive. However, all along the way, whenever interpretation of a branch is occurring within these "hot" traces, the recorder is keeping track and compiling the alternate paths.

There's a bunch more information on this method of compilation, including information that's specific to TraceMonkey implementation.