Benchmarks for various interpretation techniques

bench-execute-main.rs

#![feature(test)]
extern crate test;

mod tree {
    type BNode = Box<Node>;

    pub enum Node {
        If(BNode, BNode, BNode),
        Minus(BNode, BNode),
        Add(BNode, BNode),
        LessEqual(BNode, BNode),
        Recurse(BNode),
        Literal(i64),
        /// Call fibonacci again.
        Parameter,
    }

    impl Node {
        pub fn execute(&self, recurse: &BNode, parameter: i64) -> i64 {
            let x = |node: &Self| node.execute(recurse, parameter);
            match self {
                Node::If(a, b, c) => if x(a) == 1 { x(b) } else { x(c) }
                Node::Minus(l, r) => x(l) - x(r),
                Node::Add(l, r) => x(l) + x(r),
                Node::LessEqual(l, r) => (x(l) <= x(r)) as i64,
                Node::Recurse(p) => recurse.execute(recurse, x(p)),
                Node::Literal(v) => *v,
                Node::Parameter => parameter,
            }
        }

        pub fn compile(&self) -> Box<dyn Fn(&Context, i64) -> i64> {
            match self {
                Node::If(a, b, c) => {
                    let a = a.compile();
                    let b = b.compile();
                    let c = c.compile();
                    Box::new(move |ctx, p| if a(ctx, p) == 1 { b(ctx, p) } else { c(ctx, p) })
                }
                Node::Minus(l, r) => {
                    let l = l.compile();
                    let r = r.compile();
                    Box::new(move |c, p| l(c, p) - r(c, p))
                }
                Node::Add(l, r) => {
                    let l = l.compile();
                    let r = r.compile();
                    Box::new(move |c, p| l(c, p) + r(c, p))
                }
                Node::LessEqual(l, r) => {
                    let l = l.compile();
                    let r = r.compile();
                    Box::new(move |c, p| (l(c, p) <= r(c, p)) as i64)
                }
                Node::Recurse(p) => {
                    let p = p.compile();
                    Box::new(move |c, pa| (c.recurse)(c, p(c, pa)))
                }
                Node::Literal(v) => {
                    let v = *v;
                    Box::new(move |_, _| v)
                }
                Node::Parameter => Box::new(|_, p| p),
            }
        }
    }

    pub struct Context {
        pub recurse: Box<dyn Fn(&Context, i64) -> i64>,
    }

    pub fn tree() -> BNode {
        Box::new(Node::If(
            Box::new(Node::LessEqual(
                Box::new(Node::Parameter),
                Box::new(Node::Literal(1)),
            )),
            Box::new(Node::Literal(1)),
            Box::new(Node::Add(
                Box::new(Node::Recurse(
                    Box::new(Node::Minus(
                        Box::new(Node::Parameter),
                        Box::new(Node::Literal(1)),
                    ))
                )),
                Box::new(Node::Recurse(
                    Box::new(Node::Minus(
                        Box::new(Node::Parameter),
                        Box::new(Node::Literal(2)),
                    ))
                )),
            )),
        ))
    }

    pub fn execute(n: i64) -> i64 {
        let tree = tree();
        tree.execute(&tree, n)
    }

    pub fn compile() -> Context {
        let f = tree().compile();
        let c = Box::new(move |c: &Context, p: i64| f(c, p));
        Context { recurse: c }
    }

    pub fn run(c: &Context, n: i64) -> i64 {
        (c.recurse)(c, n)
    }
}

mod single {
    use std::rc::Rc;

    type Label = usize;

    #[derive(Clone)]
    pub enum Single {
        LessEqual(usize, usize, usize),
        Minus(usize, usize, usize),
        Add(usize, usize, usize),
        BranchTrue(usize, Label),
        Parameter(usize),
        Recurse(usize, usize),
        Literal(usize, i64),
        Return(usize),
    }

    pub fn code() -> Vec<Single> {
        vec![
            Single::Parameter(0),

            // if n <= 1
            Single::Literal(1, 1),
            Single::LessEqual(2, 0, 1),
            Single::BranchTrue(2, 12),

            // f(n - 1)
            Single::Literal(3, 1),
            Single::Minus(4, 0, 3),
            Single::Recurse(5, 4),

            // f(n - 2)
            Single::Literal(6, 2),
            Single::Minus(7, 0, 6),
            Single::Recurse(8, 7),

            // return +
            Single::Add(9, 5, 8),
            Single::Return(9),

            // return 1
            Single::Literal(10, 1),
            Single::Return(10),
        ]
    }

    pub fn execute(codes: &Vec<Single>, n: i64) -> i64 {
        // let mut frame: Vec<i64> = vec![0; 11];
        let mut frame: [i64; 11] = [0; 11];
        let mut current = 0;

        loop {
            // Changing to get_unchecked_mut for all array indexes
            // creates only a little improvement.
            let mut next = current + 1;
            match &codes[current] {
                Single::LessEqual(t, l, r) => frame[*t] = (frame[*l] <= frame[*r]) as i64,
                Single::Minus(t, l, r) => frame[*t] = frame[*l] - frame[*r],
                Single::Add(t, l, r) => frame[*t] = frame[*l] + frame[*r],
                Single::BranchTrue(c, l) => if frame[*c] == 1 { next = *l; }
                Single::Parameter(t) => frame[*t] = n,
                Single::Recurse(t, p) => frame[*t] = execute(codes, frame[*p]),
                Single::Literal(t, l) => frame[*t] = *l,
                Single::Return(t) => return frame[*t],
            }
            current = next;
        }
    }

    pub struct Context {
        pub frame: [i64; 11],
        pub current: usize,
        pub next: usize,
        pub recurse: Rc<dyn Fn(&mut Context, i64) -> i64>,
    }

    pub fn compile() -> Context {
        let mut block: Vec<Box<dyn Fn(&mut Context, i64) -> Option<i64>>> = Vec::new();
        for code in code().iter() {
            block.push(match code.clone() {
                Single::LessEqual(t, l, r) => Box::new(move |ctx, _| {
                    ctx.frame[t] = (ctx.frame[l] <= ctx.frame[r]) as i64;
                    None
                }),
                Single::Minus(t, l, r) => Box::new(move |ctx, _| {
                    ctx.frame[t] = ctx.frame[l] - ctx.frame[r];
                    None
                }),
                Single::Add(t, l, r) => Box::new(move |ctx, _| {
                    ctx.frame[t] = ctx.frame[l] + ctx.frame[r];
                    None
                }),
                Single::BranchTrue(c, l) => Box::new(move |ctx, _| {
                    if ctx.frame[c] == 1 { ctx.next = l; }
                    None
                }),
                Single::Parameter(t) => Box::new(move |ctx, p| {
                    ctx.frame[t] = p;
                    None
                }),
                Single::Recurse(t, p) => Box::new(move |ctx, _| {
                    let p = ctx.frame[p];
                    ctx.frame[t] = (ctx.recurse.clone())(ctx, p);
                    None
                }),
                Single::Literal(t, l) => Box::new(move |ctx, _| {
                    ctx.frame[t] = l;
                    None
                }),
                Single::Return(t) => Box::new(move |ctx, _| {
                    Some(ctx.frame[t])
                }),
            });
        }

        Context {
            frame: [0; 11],
            current: 0,
            next: 0,
            recurse: {
                Rc::new(move |ctx, p| {
                    let ctx = &mut Context {
                        frame: [0; 11],
                        current: 0,
                        next: 0,
                        recurse: ctx.recurse.clone(),
                    };

                    loop {
                        ctx.next = ctx.current + 1;
                        let v = (block.get(ctx.current).unwrap())(ctx, p);
                        if let Some(v) = v { return v; }
                        ctx.current = ctx.next;
                    }
                })
            },
        }
    }

    pub fn run(c: &mut Context, n: i64) -> i64 {
        (c.recurse.clone())(c, n)
    }
}

pub fn baseline(n: i64) -> i64 {
    if n <= 1 { 1 } else { baseline(n - 2) + baseline(n - 1) }
}

fn main() {
    println!("Hello, benchmark!");
    println!("Baseline: {}", baseline(32));
    println!("Walking: {}", tree::execute(32));
    println!("Compile: {}", tree::run(&tree::compile(), 32));
    println!("Single: {}", single::execute(&single::code(), 32));
    println!("Single Compile: {}", single::run(&mut single::compile(), 32));
    // println!("Big: {}", tree::run(&tree::compile(), 42));
}

#[cfg(test)]
mod tests {
    use std::hint::black_box;
    use test::Bencher;

    use super::*;

    const N: i64 = 20;

    #[bench]
    fn bench_tree_execute(bencher: &mut Bencher) {
        bencher.iter(|| tree::execute(N));
    }

    #[bench]
    fn bench_tree_compiled(bencher: &mut Bencher) {
        let c = tree::compile();
        bencher.iter(|| tree::run(&c, N));
    }

    #[bench]
    fn bench_baseline(bencher: &mut Bencher) {
        bencher.iter(|| baseline(black_box(N)));
    }

    #[bench]
    fn bench_single(bencher: &mut Bencher) {
        let code = &single::code();
        bencher.iter(|| single::execute(&code, N));
    }

    #[bench]
    fn bench_single_compile(bencher: &mut Bencher) {
        let ctx = &mut single::compile();
        bencher.iter(|| single::run(ctx, N));
    }
}

results.txt

    Finished bench [optimized] target(s) in 1.18s
     Running target/release/deps/bench_execute-4715ccc8dd85a958

running 5 tests
test tests::bench_baseline       ... bench:      22,210 ns/iter (+/- 931)
test tests::bench_single         ... bench:     471,071 ns/iter (+/- 10,970)
test tests::bench_single_compile ... bench:   1,038,359 ns/iter (+/- 59,626)
test tests::bench_tree_compiled  ... bench:     338,726 ns/iter (+/- 41,526)
test tests::bench_tree_execute   ... bench:     653,318 ns/iter (+/- 44,373)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out