Compare AST and RPN evaluation performance

ast vs rpn.js

/*
   There is an AST (Abstract syntax tree) in JSON format. 
   AST represents Excel spreadsheet formula. 
   Is it possible in JavaScript to make RPN (Reverse Polish Notation) faster than AST?
  
   AST evaluation is recusive and RPN evaluation is iterative. 
   But in any case, AST evaluation is faster despite recursion.
   I guess that the main problem is in using dynamic js arrays to emulate stack. 
   Would RPN win if it was written in C/C++?
   
   If C++ version of RPN is faster than AST. Then there is one more question. 
   Wil be RPN still faster after conversion C++ to asm.js? 
*/

// EVALUATOR

function Evaluator() {
    this.isBinaryFunction = {
        '+': true,
        '-': true,
        '*': true,
        '/': true
    };

    this.functions = {
        '+': function(args) {
            return args[0] + args[1];
        },
        '-': function(args) {
            return args[0] - args[1];
        },
        '*': function(args) {
            return args[0] * args[1];
        },
        '/': function(args) {
            return args[0] / args[1];
        },
        'SUM': function(args) {
            var sum = 0;

            for ( var i = 0; i < args.length; i++ ) {
                sum += args[i]
            }

            return sum;
        }
    };
}

Evaluator.prototype = {
    evaluateRPN: function(rpn) {
        if ( ! Array.isArray(rpn) )  {
            return rpn;
        }

        var evaluationStack = [];

        for (var i = 0; i < rpn.length; i++) {
            var token = rpn[i];

            if ( token === '^' ) {
                var oper  = evaluationStack.pop();
                var func  = this.functions[oper];
                var arity = this.isBinaryFunction[oper] ? 2 : evaluationStack.pop();

                var args = [];
                for (var j = 0; j < arity; j++) {
                    args.push( evaluationStack.pop() );
                }

                var res = func(args);
                evaluationStack.push(res);
            } else {
                evaluationStack.push(token);
            }
        }

        return evaluationStack.pop();
    },

    evaluateAST: function(ast) {
        if ( ! Array.isArray(ast) )  {
            return ast;
        }

        var oper = ast[0];
        var func = this.functions[oper];

        var evaluatedArgs = [];

        for (var i = 1; i < ast.length; i++) {
            evaluatedArgs.push( this.evaluateAST(ast[i]) );
        }

        var res = func(evaluatedArgs);

        return res;
    }
}

// AST to RPN Convetor

var isBinaryFunction = {
    '+': true,
    '-': true,
    '*': true,
    '/': true
};

function AST2RPN(ast, rpn) {
     var isReady = false;

    if (!rpn) {
        isReady = true;
        rpn = []
    };

    if (!Array.isArray(ast)){
        rpn.push(ast);
        return ast;
    }

    var operator = ast[0];

    rpn.push('^'); // operator flag
    rpn.push(operator);

    if (! isBinaryFunction[operator] ) {
        // push number of arguments for not binary functions
        rpn.push(ast.length-1);
    }

    for (var i = 1; i < ast.length; i++) {
        var arg = ast[i];
        AST2RPN(arg,rpn);
    };

    if (isReady) {
        return rpn.reverse();
    }
}


// BENCHMARK

function timeRPN(rpn) {
    var evaluator = new Evaluator();

    console.time('EVALUATE RPN');

    for (var i = 0; i < 1000000; i++) {
        var res = evaluator.evaluateRPN(rpn);
    }

    console.timeEnd('EVALUATE RPN');
}


function timeAST(ast) {
    var evaluator = new Evaluator();

    console.time('EVALUATE AST');

    for (var i = 0; i < 1000000; i++) {
        var res = evaluator.evaluateAST(ast);
    }

    console.timeEnd('EVALUATE AST');
}


var ast1 = ['SUM',
    [ '-',['+',['/',['*',10,20],30],40],50],
    [ '-',['+',['/',['*',10,20],30],40],50],
    [ '-',['+',['/',['*',10,20],30],40],50],
    [ '-',['+',['/',['*',10,20],30],40],50]
];

var rpn1 = AST2RPN(ast1);


timeRPN(rpn1);
timeAST(ast1);

Great test. Thank you!

Rust version: https://gist.github.com/breeswish/6c98e7a41940547a93fa674a04557fbe (RPN is faster)