Comparison of memoization implementations

JavaScript performance comparison

Test case created by Addy Osmani

Preparation code

<script>
  //memo6 - by @madrobby/thomas fuchs
  
  Function.prototype.cached = function(){
    var self = this, cache = {};
    return function(arg){
      if(arg in cache) {
        //console.log('Cache hit for '+arg);
        return cache[arg];
      } else {
        //console.log('Cache miss for '+arg);
        return cache[arg] = self(arg);
      }
    }
  }
  
  
  //memo1
  //underscore.js implem
  
  function memoize1(func, hasher) {
      var memo = {};
      hasher || (hasher = function(value){
        return value; //^this could be done better..surely..
      });
      return function() {
        var key = hasher.apply(this, arguments);
        return hasOwnProperty.call(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
      };
    };
  
  
  //memo2 - another variation with changes by @addyosmani
  //based on initial work by thejit
  //note: I'm aware of the perils of hanging the implem off
  //fn, just want to find out if this version performs much better
    function memoize2(fn) {
      return function () {
          var args = Array.prototype.slice.call(arguments),
              hash = "",
              i  = args.length;
          while(i--){
            hash += (Object.prototype.toString.call({}) == Object.prototype.toString.call(args[i])) ? JSON.stringify(args[i]) : args[i];
            fn.memoize = fn.memoize || {};
        } 
          return (hash in fn.memoize) ? fn.memoize[hash] : fn.memoize[hash] = fn.apply(this, args);
      };
  }
  
  //memo3 - unscriptables implem.
  function memoize3(func, context) {
      function memoizeArg (argPos) {
          var cache = {};
          return function () {
              if (argPos == 0) {
                  if (!(arguments[argPos] in cache)) {
                      cache[arguments[argPos]] = func.apply(context, arguments);
                  }
                  return cache[arguments[argPos]];
              }
              else {
                  if (!(arguments[argPos] in cache)) {
                      cache[arguments[argPos]] = memoizeArg(argPos - 1);
                  }
                  return cache[arguments[argPos]].apply(this, arguments);
              }
          }
      }
      // JScript doesn't grok the arity property, but uses length instead
      var arity = func.arity || func.length;
      return memoizeArg(arity - 1);
  }
  
  //memo4 - by stevenlevithan
  function memoize4(functor, expiration) {
        var memo = {};
        return function () {
                var key = Array.prototype.join.call(arguments, "§");
                if (key in memo)
                        return memo[key];
                if (expiration)
                        setTimeout(function () {delete memo[key];}, expiration);
                return memo[key] = functor.apply(this, arguments);
        };
  }
  
  
  //memo5 - @gbradley
  
  function memoize5(fn){
  var lookup={};
  return function(){
        var args=[].slice.call(arguments);
        var key=JSON.stringify(args);
        var result=lookup[key];
        if (!result){
                result=fn.apply(this,args);
                lookup[key]=result;
                }
        return result;
        };
  }
  
  function fib(x) {
      if(x < 2) return 1; else return fib(x-1) + fib(x-2);
  }
  
  
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Memo 1 - underscore.js
 
var fibTest1 = memoize1(fib);
console.log(fibTest1(20),'test1-norm');

setTimeout(function(){
        console.log(fibTest1(20),'test1-memo');
}, 1000);
 
 pending…
Memo 2 - addy + thejit
 
var fibTest2 = memoize2(fib);
console.log(fibTest2(20),'test2-norm');

setTimeout(function(){
        console.log(fibTest2(20),'test2-memo');
}, 1000);
 
 pending…
Memo 3 - unscriptable
 
var fibTest3 = memoize3(fib);
console.log(fibTest3(20),'test3-norm');

setTimeout(function(){
        console.log(fibTest3(20),'test3-memo');
}, 1000);
 pending…
Memo 4 - stevenlevithan
 
var fibTest4 = memoize4(fib,1000);
console.log(fibTest4(20),'test4-norm');

setTimeout(function(){
        console.log(fibTest4(20),'test4-memo');
}, 1000);
 pending…
Memo 5 - gbradley
 
var fibTest5 = memoize5(fib);
console.log(fibTest5(20),'test5-norm');

setTimeout(function(){
        console.log(fibTest5(20),'test5-memo');
}, 1000);
 pending…
Memo 6 - madrobby
 
var fibTest6 = fib.cached();
console.log(fibTest6(20),'test6-norm');

setTimeout(function(){
        console.log(fibTest6(20),'test6-memo');
}, 1000);
 pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

3 comments

Addy Osmani (revision owner) commented : ∞

I'll update the description later, but basically the setup for this is:

1) I'm defining each memoization implementation in sequence (eg. memoize1,memoize2,memoize3 etc..., with the exception of Fuchs implem which is hanging off the Function.prototype.

2) We're memoizing a fibonacci function called 'fib', which all implementations used have been previously tested with to ensure they're able to successfully memoize correctly.

3) Output is made twice, first to cache the result, the second time to lookup the cached result.

Addy Osmani (revision owner) commented : ∞

There are currently some issues with the test setup here. I think option 2 is faster than many of the others, but certainly not by the magnitude thats being reported. Looking into what's broken.

Addy Osmani (revision owner) commented : ∞

Believe I've finally tamed the tests. Using console for additional verification of results, but they're looking more sensible now.

Add a comment