Comparison of memoization implementations

JavaScript performance comparison

Revision 17 of this test case created and last updated

Info

fixed tests so they setup and teardown, fixing erroneous statistics

Preparation code

<script>
var fib, fiborg;
fiborg = fib = function (x) {
        if(x < 2) return 1; else return fib(x - 1) + fib(x - 2);
}

//true underscoer impl:
function identity(value) {
        return value;
};
function has(obj, key) {
        return hasOwnProperty.call(obj, key);
};
function memoize_ (func, hasher) {
        var memo = {};
        hasher || (hasher = identity);
        return function() {
        var key = hasher.apply(this, arguments);
        return has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
        };
};
var fib2 = memoize_(fiborg);

//old underscore.js implem
function memoize3(func) {
        "use strict";
        var memo = {};
        var slice = Array.prototype.slice;
        return function() {
                var key = "" + slice.call(arguments);
                return (key in memo) ? memo[key] : (memo[key] = func.apply(this, arguments));
        };
}
var fib3 = memoize3(fiborg);

//memo4 - unscriptables implem.
function memoize4(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);
}
var fib4 = memoize4(fiborg);

//memo5 - by stevenlevithan
function memoize5(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);
        };
}
var fib5 = memoize5(fiborg,1000);


//memo6 - @gbradley
function memoize6(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;
        };
}
var fib6 = memoize6(fiborg);

//memo7 - by @madrobby/thomas fuch
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);
        }
        }
}
var fib7 = fiborg.cached();


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;

                        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 fib8 = memoize8(fiborg);


//memo10 - by @yoannSitbon
Function.prototype.memoize10 = function () {
        'use strict';
        var self = this,
                cache = (self.MEM10 = self.MEM10 || {}),
                strfy = JSON.stringify;

        return function () {
                var hash = strfy(arguments);
                return (hash in cache) ?
                        cache[hash] : cache[hash] = self.apply(this, arguments);
        };
};
var fib10 = fiborg.memoize10();

//memo11 - by @yoannSitbon
Function.prototype.memoize11 = function () {
        'use strict';
        var self  = this,
                cache = (self.MEM11 = self.MEM11 || {}),
                strfy = JSON.stringify,
                slice = Array.prototype.slice;

        return function () {
                var hash = strfy(slice.call(arguments));
                return (hash in cache) ?
                        cache[hash] :
                        cache[hash] = self.apply(this, arguments);
        };
};
var fib11 = fiborg.memoize11();

//      var memo = {};
//      hasher || (hasher = identity);
//      return function() {
//      var key = hasher.apply(this, arguments);
//      return has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
//      };

function mem_fast(func){
        var cache = {},
                stringifyJson = JSON.stringify,
                sliceArray = Array.prototype.slice;
        return function () {
                var hash = stringifyJson(arguments);
                return has(cache,hash) ? cache[hash] : cache[hash] = func.apply(this, arguments);
        };
};
var fib12 = mem_fast(fiborg);

//      var memo = {};
//      hasher || (hasher = identity);
//      return function() {
//      var key = hasher.apply(this, arguments);
//      return has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
//      };
function memoize14(func, hasher){
        var cache = {};
        if(hasher)
                return function () {
                        var hash = hasher.apply(this,arguments);
                        return (hash in cache) ? cache[hash] : cache[hash] = func.apply(this, arguments);
                };
        return function() {
                var hash = JSON.stringify(arguments);
                return (hash in cache) ? cache[hash] : cache[hash] = func.apply(this, arguments);
        };
}
var fib14 = memoize14(fiborg);

//      var memo = {};
//      hasher || (hasher = identity);
//      return function() {
//      var key = hasher.apply(this, arguments);
//      return has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
//      };
function memoize9(func, hasher){
        var cache = {};
                //stringifyJson = JSON.stringify,
                hasher || (hasher = JSON.stringify);
        return function () {
                var hash = hasher.apply(this,arguments);
                return (hash in cache) ? cache[hash] : cache[hash] = func.apply(this, arguments);
        };
};
var fib9 = memoize9(fiborg);


//memoize.js - by @addyosmani
// with tweaks from @philogb, @mathias, @DmitryBaranovsk, @JamieMason
function memoize13(func) {
        var cache = {},
                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);
        };
};
var fib13 = memoize13(fiborg);

</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
Just Fib
fib(20);
pending…
underscore
fib2(20);
pending…
old underscore we think
fib3(20);
pending…
Memo 4 - unscriptables
fib4(20);
pending…
Memo 5 - stevenlevithan, expire 1000ms
fib5(20);
pending…
Memo 6 - gbradley
fib6(20);
pending…
Memo 7 - madrobby, direct call 1 arg
fib7(20);
pending…
Memo 8 - medikoo (generic - any type of arguments)
fib8(20);
pending…
underscore hasher=JSON.stringify
fib9(20);
pending…
Memo10 - fun prototype without slice
fib10(20);
pending…
Memo11 fun prototype with slice
fib11(20);
pending…
see - fastest? JSON
fib12(20);
pending…
JSON(slice) @philogb, @mathias, @DmitryBaranovsk, @JamieMason
fib13(20);
pending…
Underscore hardcode default hasher = JSON
fib14(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