Comparison of memoization implementations (v3)

Revision 3 of this benchmark created by Mariusz Nowak on

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 @philogb
  //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;  
              toString = Object.prototype.toString,
              callEm = toString.call({}),
              currentArg = null;
          while(i--){  
            currentArg = args[i];
            hash += (callEm == toString.call(currentArg)) ?   
            JSON.stringify(currentArg) : currentArg;  
            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;
        };
  }
  
  // memo5 - @medikoo
  // https://github.com/medikoo/es5-ext/blob/master/lib/Function/memoize.js
  
  var memoize7 = (function () {
        var isArray = Array.isArray
          , slice   = Array.prototype.slice
  
          , resolve;
  
        resolve = function (args) {
                return this.map(function (r, i) {
                        return r ? r(args[i]) : args[i];
                }).concat(slice.call(args, this.length));
        };
  
        return function (fn, length, resolvers) {
                var cache, resolver;
                cache = [];
                if (isArray(length)) {
                        resolvers = length;
                        length = fn.length;
                } else if (length == null) {
                        length = fn.length;
                }
  
                resolver = resolvers ? resolve.bind(resolvers) : null;
  
                return function () {
                        var limit, i, index, args, current, found;
  
                        args = resolver ? resolver(arguments) : arguments;
                        i = 0;
                        index = limit = (length === true) ? args.length: length;
                        current = cache;
  
                        if (limit === 0) {
                                found = current.hasOwnProperty(0);
                        } else {
                                while (i !== limit) {
                                        if (!current[index]) {
                                                current = (current[index] = [[args[i]], []]);
                                                index = 0;
                                        } else if (
                                                (index = (current = current[index])[0].indexOf(args[i])) === -1) {
                                                index = current[0].push(args[i]) - 1;
                                                found = false;
                                        } else {
                                                found = current[1].hasOwnProperty(index);
                                        }
                                        current = current[1];
                                        ++i;
                                }
                        }
                        if (found) {
                                return current[index];
                        }
                        return current[index] = fn.apply(this, args);
                };
        };
  }());
  
  var fib, fiborg;
  fiborg = fib = function (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
fib = memoize1(fiborg);
console.log(fib(20),'test1-norm');
 
ready
Memo 2 - addyosmani + philogb
fib = memoize2(fiborg);
console.log(fib(20),'test2-norm');

 
ready
Memo 3 - unscriptable
fib = memoize3(fiborg);
console.log(fib(20),'test3-norm');
 
ready
Memo 4 - stevenlevithan
fib = memoize4(fiborg, 1000);
console.log(fib(20),'test4-norm');
 
ready
Memo 5 - gbradley
fib = memoize5(fiborg);
console.log(fib(20),'test5-norm');
 
ready
Memo 6 - madrobby
fib = fiborg.cached();
console.log(fib(20),'test6-norm');
 
ready
Memo 7 - medikoo (generic - any type of arguments)
fib = memoize7(fiborg);
console.log(fib(20),'test7-norm');
 
ready

Revisions

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