Comparison of memoization implementations

JavaScript performance comparison

Revision 10 of this test case created by Jamie Mason

Info

Hey guys, first time using jsperf so apologies if I've messed anything up. All this change is, is memo2 but with the lookups moved into local scope and i thought the declaration of fn.memoize didn't need to be done every pass of the loop.

Very minor gains...

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;
        };
  }
 
  //memo7 - as memo2 but with lookups localised to a closure and the declaration of fn.memoize moved outside the loop, by @GotNoSugarBaby
  function memoize7 ( fn )
  {
        var sliceArray = Array.prototype.slice
            , stringifyJson = JSON.stringify
            , castAsObject = Object;
       
        fn.memoize = fn.memoize || {};
 
        return function ()
        {
                var args = sliceArray.call(arguments)
                    , hash = ""
                    , i = args.length
                    , currentArg = null
                    , memoizedFn = fn.memoize;
 
                while (i--)
                {
                        currentArg = args[i];
                        hash += (currentArg === castAsObject(currentArg)) ?
                                stringifyJson(currentArg)
                                :
                                currentArg;
                }
 
                return (hash in memoizedFn) ?
                        memoizedFn[hash]
                        :
                        memoizedFn[hash] = fn.apply( this , args );
        };
  }
 
  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…
Memo 7 - GotNoSugarBaby
var fibTest7 = memoize7(fib);
console.log(fibTest7(20),'test7-norm');

setTimeout(function(){
        console.log(fibTest7(20),'test7-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:

0 comments

Add a comment