Comparison of memoization implementations

JavaScript performance comparison

Revision 11 of this test case created by Jamie Mason

Info

https://github.com/addyosmani/memoize.js/pull/4#issuecomment-2168862

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 );
        };
  }
 
  //memo8 - @GotNoSugarBaby
  function memoize8(fn) {
     "use strict";
     var cache = (fn.memoize = fn.memoize || {}),
         stringifyJson = JSON.stringify,
         sliceArray = Array.prototype.slice;
 
      return function () {
          var hash = stringifyJson(sliceArray.call(arguments));
          return (hash in cache) ? cache[hash] : cache[hash] = fn.apply(this, arguments);
      };
  }
 
  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…
Memo 8 - GotNoSugarBaby
var fibTest8 = memoize8(fib);
console.log(fibTest8(20),'test8-norm');

setTimeout(function(){
        console.log(fibTest8(20),'test8-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