Comparison of memoization implementations

JavaScript performance comparison

Revision 7 of this test case created by Dmitry

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( fn ) {
        return function () {
                var args = Array.prototype.slice.call(arguments),
                hash = "",
                i  = args.length;
                currentArg = null;
                while(i--){
                        currentArg = args[i];
                        hash += (currentArg === Object(currentArg)) ?
                                JSON.stringify(currentArg) : currentArg;
                        fn.memoize || (fn.memoize = {});
                }
                return (hash in fn.memoize) ? fn.memoize[hash] :
                        fn.memoize[hash] = fn.apply( this , args );
        };
  }
 
 
  //memo2 - another variation with changes by @addyosmani
  //based on initial work by @philogb and optimized by
  //@mathias
  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;
        };
  }
 
  // memo7 - @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);
                };
        };
  }());
 
  // memo8 - @medikoo
  // https://github.com/medikoo/es5-ext/blob/master/lib/Function/memoize-primitive.js
 
  var memoize8 = (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;
 
                        found = current.hasOwnProperty(index);
                        if (limit !== 0) {
                                while (i !== limit) {
                                        if (!found) {
                                                current = (current[index] = {});
                                        } else {
                                                found = (current = current[index]).hasOwnProperty(args[i]);
                                        }
                                        index = args[i];
                                        ++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

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Memo 1 - Mine optim
fib = memoize1(fiborg);
fib(20);
 
pending…
Memo 2 - addyosmani + philogb
fib = memoize2(fiborg);
fib(20);

 
pending…
Memo 3 - unscriptable
fib = memoize3(fiborg);
fib(20);
 
pending…
Memo 4 - stevenlevithan
fib = memoize4(fiborg, 1000);
fib(20);
 
pending…
Memo 5 - gbradley
fib = memoize5(fiborg);
fib(20);
 
pending…
Memo 6 - madrobby
fib = fiborg.cached();
fib(20);
 
pending…
Memo 7 - medikoo (generic - any type and length of arguments)
fib = memoize7(fiborg);
fib(20);
 
pending…
Memo 8 - medikoo (as 7 but only string values)
fib = memoize8(fiborg);
fib(20);
 
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