AST vs RPN evaluation performance. JavaScript version: https://gist.github.com/koorchik/9717b893ae2134e21dbe

ast_vs_rpn.rs

//! 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);
    });
}

gistfile1.txt

test bench_ast ... bench:         220 ns/iter (+/- 50)
test bench_rpn ... bench:         155 ns/iter (+/- 25)