Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
AST vs RPN evaluation performance. JavaScript version: https://gist.github.com/koorchik/9717b893ae2134e21dbe
//! AST vs RPN evaluation performance in Rust language.
#![feature(test)]
extern crate test;
#[derive(Clone, Copy, Debug)]
pub enum Function {
Plus,
Minus,
Multiply,
Divide,
Sum,
}
impl Function {
#[inline]
pub fn eval(self, args: &[i64]) -> i64 {
match self {
Function::Plus => {
assert_eq!(args.len(), 2);
args[0] + args[1]
}
Function::Minus => {
assert_eq!(args.len(), 2);
args[0] - args[1]
}
Function::Multiply => {
assert_eq!(args.len(), 2);
args[0] * args[1]
}
Function::Divide => {
assert_eq!(args.len(), 2);
args[0] / args[1]
}
Function::Sum => {
assert!(args.len() >= 1);
args.iter().sum::<i64>()
}
}
}
}
#[derive(Clone, Debug)]
pub enum ASTNode {
Fn(Function, Vec<ASTNode>),
Constant(i64),
}
impl ASTNode {
#[inline]
pub fn eval(&self) -> i64 {
let mut evaluated_args: [i64; 10] = [0; 10];
match self {
ASTNode::Fn(ref func, ref args) => {
let number_of_args = args.len();
for i in 0..number_of_args {
evaluated_args[i] = args[i].eval();
}
func.eval(&evaluated_args[0..number_of_args])
},
ASTNode::Constant(ref v) => *v,
}
}
fn append_rpn(&self, rpn: &mut Vec<RPNNode>) {
match self {
ASTNode::Fn(ref func, ref args) => {
rpn.push(RPNNode::Fn(*func, args.len()));
for arg in args {
arg.append_rpn(rpn);
}
},
ASTNode::Constant(ref v) => {
rpn.push(RPNNode::Constant(*v));
},
}
}
pub fn to_rpn(&self) -> Vec<RPNNode> {
let mut ret = Vec::new();
self.append_rpn(&mut ret);
ret.reverse();
ret
}
}
#[derive(Clone, Copy, Debug)]
pub enum RPNNode {
Fn(Function, usize),
Constant(i64),
}
#[inline]
pub fn eval_rpn(rpn: &[RPNNode]) -> i64 {
let mut stack: [i64; 100] = [0; 100];
let mut stack_pointer = 0;
let mut args: [i64; 10] = [0; 10];
for node in rpn {
match node {
RPNNode::Fn(ref func, ref number_of_args) => {
let n = *number_of_args;
for i in 0..n {
stack_pointer -= 1;
args[i] = stack[stack_pointer];
}
let ret = func.eval(&args[0..n]);
stack[stack_pointer] = ret;
stack_pointer += 1;
},
RPNNode::Constant(ref v) => {
stack[stack_pointer] = *v;
stack_pointer += 1;
},
}
}
stack[0]
}
pub fn new_payload() -> ASTNode {
let inner = ASTNode::Fn(Function::Minus, vec![
ASTNode::Fn(Function::Plus, vec![
ASTNode::Fn(Function::Divide, vec![
ASTNode::Fn(Function::Multiply, vec![
ASTNode::Constant(10), ASTNode::Constant(20)
]),
ASTNode::Constant(30),
]),
ASTNode::Constant(40),
]),
ASTNode::Constant(50),
]);
ASTNode::Fn(Function::Sum, vec![
inner.clone(),
inner.clone(),
inner.clone(),
inner.clone(),
])
}
#[test]
fn test_eval() {
let ast_node = new_payload();
assert_eq!(ast_node.eval(), -16);
let rpn_nodes = ast_node.to_rpn();
assert_eq!(eval_rpn(&rpn_nodes), -16);
}
#[bench]
fn bench_ast(b: &mut test::Bencher) {
let ast_node = new_payload();
b.iter(|| {
let v = test::black_box(&ast_node).eval();
test::black_box(v);
});
}
#[bench]
fn bench_rpn(b: &mut test::Bencher) {
let ast_node = new_payload();
let rpn_nodes = ast_node.to_rpn();
b.iter(|| {
let v = eval_rpn(test::black_box(&rpn_nodes));
test::black_box(v);
});
}
test bench_ast ... bench: 220 ns/iter (+/- 50)
test bench_rpn ... bench: 155 ns/iter (+/- 25)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment