Archive

Posts Tagged ‘memoization javascript’

A Better Javascript Memoizer

May 1st, 2009

Last month, I had the pleasure of meeting tons of excellent and intelligent front-end engineers at JSConf 2009 — the conference for Javascript in Washington DC. If you are a front-end engineer — or even if you write programs in Javascript for back ends, mobile devices, or desktops — you absolutely have to go to JSConf 2010. It’s apparent that Javascript is quickly becoming one of the hottest languages for all environments and applications, and JSConf is the first (and only) conference that deals with Javascript exclusively.

JSConf 2009

Track A presentations from JSConf 2009

One of the Track A speakers was Stoyan Stefanov, a really smart guy from Yahoo. His presentation was about high-performance web apps, but on one slide in particular, I was struck by his implementation of memoization (slide 79 of 87) because he used the function instance to cache the results of the function itself.

If you’re not familiar with memoization, here’s 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.

Memoization (Wikipeida)

In other words, it’s a way to cache the results of function calls so that repeated expensive computations or lengthy lookups can be avoided.

Here’s Stoyan’s example:

function myFunc(param){
    if (!myFunc.cache) {
        myFunc.cache = {};
    }
    if (!myFunc.cache[param]) {
        var result = {}; // ...
        myFunc.cache[param] = result;
    }
    return myFunc.cache[param];
}

(Use your imagination to fill in some complex or lengthy task in place of the line with the “…”!)

Again, what struck me was his use of the function instance to cache the results. In Javascript, functions are first-class objects and can be assigned properties just like any other object. But should we do this? It certainly seems like this could cause intractable problems if used widely. Imagine if everybody started decorating functions and methods with properties? (Actually, debuggers such as Drosera and Firebug now use properties on function instances to help identify them in logs and traces. It seems to me we should try not to invade on that space!)

So, of course, I set out to answer the question, “Do we really need to use the function instance to hold the result cache?”

The answer is “No”. It’s really quite easy to avoid, too.
Read more…

Javascript, performance