Tuesday, May 5th, 2009

A Better Javascript Memoizer

Category: JavaScript, Performance

<p>We have covered memoizers in the past, but John Hann has posted on a nice implementation that takes advantage of closures, arity, and recursion — 3 concepts/features that Javascript was meant to use.

It leads to this generic version:

< view plain text >
  1. // memoize: a general-purpose function to enable a function to use memoization
  2. //   func: the function to be memoized
  3. //   context: the context for the memoized function to execute within
  4. //   Note: the function must use explicit, string-serializable parameters
  5. function memoize (func, context) {
  6.     function memoizeArg (argPos) {
  7.         var cache = {};
  8.         return function () {
  9.             if (argPos == 0) {
  10.                 if (!(arguments[argPos] in cache)) {
  11.                     cache[arguments[argPos]] = func.apply(context, arguments);
  12.                 }
  13.                 return cache[arguments[argPos]];
  14.             }
  15.             else {
  16.                 if (!(arguments[argPos] in cache)) {
  17.                     cache[arguments[argPos]] = memoizeArg(argPos - 1);
  18.                 }
  19.                 return cache[arguments[argPos]].apply(this, arguments);
  20.             }
  21.         }
  22.     }
  23.     // JScript doesn't grok the arity property, but uses length instead
  24.     var arity = func.arity || func.length;
  25.     return memoizeArg(arity - 1);
  26. }

and this conclusion:

Yes, memoization is a neat concept. But why use it rather than just hand-coded caching mechanisms? It’s easy enough to write a caching routine, right? Here are a few good reasons:

  • hand-coded caching mechanisms obfuscate your code
  • multi-variate caching routines are bulky in Javascript
  • fewer lines of code means fewer bugs
  • Java programmers will think more highly of you ;)

Related Content:


Comments feed TrackBack URI

Wondering why he used func.arity || func.length instead of just func.length. Mozilla Developer Center marks Function.arity as deprecated.
Nitpicking anyway.

Comment by igstan — May 5, 2009

I coded a memoization function that works with non-unary functions some time ago (last year actually):


I wonder what are the tradeoffs/benefits of using my memoization function and his.

Comment by philogb — May 5, 2009

I think that ‘Java programmers will think more highly of you’ is more of a negative than a positive :)

Comment by Sembiance — May 5, 2009

Hey igstan, thanks for alerting me to the fact that arity is deprecated. I have no idea why we’d want to deprecate the proper mathematical term. Go figure! :-)

@philogb: You’ve got a great article. Very in-depth discussion. I think the main difference between our implementations is that I am favoring recursion over serialization of multiple parameters (as yours implements). If I am in total control of the data that will be fed in as parameters, then I might not be so picky about serialization. However, my mind is always focused on componentization and code reuse. (I think it’s always a good idea to program defensively, too.) Therefore, I wanted to find a method that could work with any parameter data. I didn’t quite do it, but I feel I got further than any other implementation I’ve seen so far (in Javascript).

Comment by unscriptable — May 5, 2009

Leave a comment

You must be logged in to post a comment.