Comparison of memoization implementations (v26)

Revision 26 of this benchmark created 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
  
  //_.identity
  function identity(value) {
      return value;
  };
  
  //_.memoize
  function memoize1(func, hasher) {
      var memo = {};
      hasher || (hasher = identity);
      return function() {
        var key = hasher.apply(this, arguments);
        return hasOwnProperty.call(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
      };
    };
  
  
  //memoize.js - by @addyosmani
  // with tweaks from @philogb, @mathias, @DmitryBaranovsk, @JamieMason
  function memoize2(func) {
       "use strict";
       var cache = (func.memoize = func.memoize || {}),
           stringifyJson = JSON.stringify,
           sliceArray = Array.prototype.slice;
        return function () {
            var hash = stringifyJson(sliceArray.call(arguments));
            return (hash in cache) ? cache[hash] : cache[hash] = func.apply(this, arguments);
        };
    }; 
  
  //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);
                };
        };
  }());

  function memoize8 (fn, cache) {
    cache = memoed._cache = cache || {}
    function memoed () {
      var args = JSON.stringify(Array.prototype.slice(arguments))
      if (!(args in cache)) cache[args] = fn.apply(this, arguments)
      return cache[args]
    }
    return memoed
  }
  
  var fib, fiborg;
  fiborg = fib = function (loanamt, term_in_months, rate_as_percent) {
                //console.log("namespaced getPayment");
                var term = term_in_months;
                var rate = rate_as_percent/100;
                return (loanamt * (rate / 12)) / (1 - Math.pow(1 + (rate / 12), -term));
        };
  
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
Memo 1 - underscore.js
fib = memoize1(fiborg);
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Memo 2 - addy, mathias, jamie etc.
fib = memoize2(fiborg);
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Memo 3 - unscriptable
fib = memoize3(fiborg);
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Memo 4 - stevenlevithan
fib = memoize4(fiborg, 1000);
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Memo 5 - gbradley
fib = memoize5(fiborg);
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Memo 6 - madrobby
fib = fiborg.cached();
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Memo 7 - medikoo (generic - any type of arguments)
fib = memoize7(fiborg);
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Memo 8 - nrn
fib = memoize8(fiborg);
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready
Unmemoized
for(var i =0; i<500; i++) {
  fib(300000,360,  Math.ceil(Math.random()*40)  );
}
 
ready

Revisions

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