_Util_eq optimization

Util.js

/* SETUP */

var Benchmark = require('benchmark');

function _Utils_Tuple2(x,y) {
    return {
        $: '#2',
        a: x,
        b: y
    };
}

function _Make_List(size, list) {
    if (!list) {
        list = { $: '[]' };
    }

    for (var i = 0; i < size; i++) {
        list = {
            $: '::',
            a: 0,
            b: list
        };
    }

    return list;
}

/* ORIGINAL */

function _Utils_eq(x, y)
{
  /* Add this for 8x performance improvement when two primitives (non-objects) are equal
  if (x === y) return true;
  */
  
  /* Add this for 8x performance improvement when two primitives (non-objects) are inequal
    if (typeof x !== 'object' || x === null || y === null)
    {
        //if (typeof x === 'function') throw new Error("function not supported");
        return false;
    }
   */
  
    for (
        var pair, stack = [], isEqual = _Utils_eqHelp(x, y, 0, stack);
        isEqual && (pair = stack.pop());
        isEqual = _Utils_eqHelp(pair.a, pair.b, 0, stack)
    )
    {}

    return isEqual;
}

function _Utils_eqHelp(x, y, depth, stack)
{
    if (depth > 100)
    {
        stack.push(_Utils_Tuple2(x,y));
        return true;
    }

    if (x === y)
    {
        return true;
    }

    if (typeof x !== 'object' || x === null || y === null)
    {
        //if (typeof x === 'function') throw new Error("function not supported");
        return false;
    }

    /**__DEBUG/
       if (x.$ === 'Set_elm_builtin')
       {
       x = __Set_toList(x);
       y = __Set_toList(y);
       }
       if (x.$ === 'RBNode_elm_builtin' || x.$ === 'RBEmpty_elm_builtin')
       {
       x = __Dict_toList(x);
       y = __Dict_toList(y);
       }
    //*/

    /**__PROD/
       if (x.$ < 0)
       {
       x = __Dict_toList(x);
       y = __Dict_toList(y);
       }
    //*/

    for (var key in x)
    {
        if (!_Utils_eqHelp(x[key], y[key], depth + 1, stack))
        {
            return false;
        }
    }

    return true;
}


/* OPTIMIZED */

var _Eq_Stack_Empty = _Eq_Stack_Cons(null, null, null, null);

function _Eq_Stack_Cons(key, x, y, stack) {
    return {
        a: stack,
        b: key,
        c: x,
        d: y,
    };
}

function _Opt_Utils_eq(x, y)
{
    for (
        var stack = _Opt_Utils_eqHelp(x, y, _Eq_Stack_Empty);
        stack && stack !== _Eq_Stack_Empty;
        stack = _Opt_Utils_eqHelp(stack.c[stack.b], stack.d[stack.b], stack.a)
    )
    {}

    return stack === _Eq_Stack_Empty;
}

function _Opt_Utils_eqHelp(x, y, stack)
{
    if (x === y)
    {
        return stack;
    }

    var xType = typeof x;
    if (xType !== 'object' || xType !== typeof y || x === null || y === null)
    {
        //if (xType === 'function') throw new Error("function not supported");
        return null;
    }

    /**__DEBUG/
       if (x.$ === 'Set_elm_builtin')
       {
       x = __Set_toList(x);
       y = __Set_toList(y);
       }
       if (x.$ === 'RBNode_elm_builtin' || x.$ === 'RBEmpty_elm_builtin')
       {
       x = __Dict_toList(x);
       y = __Dict_toList(y);
       }
    //*/

    /**__PROD/
       if (x.$ < 0)
       {
       x = __Dict_toList(x);
       y = __Dict_toList(y);
       }
    //*/

    for (var key in x)
    {
        stack = _Eq_Stack_Cons(key, x, y, stack);
    }

    return stack;
}

/* TESTING */

function test(message, a, b) {
    if (_Utils_eq(a, b) !== _Opt_Utils_eq(a, b)) {
        throw new Error(message);
    }
}

test("Equal primitives doesn't work", "same", "same");
test("Inequal primitives doesn't work", 5, 6)
test("Equal lists doesn't work", _Make_List(1000), _Make_List(1000));
test("Inequal lists doesn't work", _Make_List(1000), _Make_List(800));

var shared = _Make_List(500);
test("Equal (average case) doesn't work", _Make_List(500, shared), _Make_List(500, shared));

/* BENCHMARK SETUP */

var prepSuite = new Benchmark.Suite;
prepSuite.add('Preperation', function() {
    // Call eq with a bunch of different inputs to make sure the JIT doesn't optimize
    // the function specifically for the provided inputs.

    var fns = [_Utils_eq, _Opt_Utils_eq];

    for (var i = 0; i < fns.length; i++) {
        var fn = fns[i];

        fn(5, 10);
        fn("test", "test");
        fn([1,2,3], [4,5,6]);
        fn({a: 2}, {b: 3});
        fn(true, false)
        fn(new Number(6), new Number(6));
    }
}).run({ 'async': false });

function runBenchmark(name, a, b) {
    var suite = new Benchmark.Suite;

    suite.add(name + "#Original", function() {
        _Utils_eq(a, b);
    }).add(name + "#Optimized", function() {
        _Opt_Utils_eq(a, b);
    }).on('cycle', function(event) {
        console.log(String(event.target));
    }).on('complete', function() {
        console.log('Fastest is ' + this.filter('fastest').map('name'));
    }).run({ 'async': false });
}

/* BENCHMARKS */

runBenchmark("equalPrimitives", "same", "same")
runBenchmark("nonEqualPrimitives", 5, 6);
runBenchmark("equalLists", _Make_List(1000), _Make_List(1000));
runBenchmark("inequalLists", _Make_List(1000), _Make_List(800));
runBenchmark("equalAvgLists", _Make_List(500, shared), _Make_List(500, shared));