Comparison of memoization implementations (v10)

Revision 10 of this benchmark created by Jamie Mason on

Description

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 HTML

<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

Ready to run.

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

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

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

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

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

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

setTimeout(function(){
        console.log(fibTest6(20),'test6-memo');
}, 1000);
ready
Memo 7 - GotNoSugarBaby
var fibTest7 = memoize7(fib);
console.log(fibTest7(20),'test7-norm');

setTimeout(function(){
        console.log(fibTest7(20),'test7-memo');
}, 1000);
 
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.