Skip to content

Instantly share code, notes, and snippets.

@koorchik
Last active July 6, 2023 09:27
Show Gist options
  • Save koorchik/9717b893ae2134e21dbe to your computer and use it in GitHub Desktop.
Save koorchik/9717b893ae2134e21dbe to your computer and use it in GitHub Desktop.
Compare AST and RPN evaluation performance
/*
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);
@Fonger
Copy link

Fonger commented Jun 21, 2018

Great test. Thank you!

@breezewish
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment