Rust BF interpreters, static vs dynamic dispatch

bench.b

 Benchmark brainf*ck program
>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
[>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
++++++++[>++++++++++[>++++++++++[>++++++++++[>+
+++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.
  

closures.rs

struct Tape {
    pos: usize,
    data: Vec<u8>,
}

impl Tape {
    fn new() -> Self {
        Tape {
            pos: 0,
            data: vec![0],
        }
    }

    fn get(&self) -> u8 {
        self.data[self.pos]
    }

    fn inc(&mut self, amount: i8) {
        if amount < 0 {
            self.data[self.pos] -= amount.abs() as u8;
        } else {
            self.data[self.pos] += amount as u8;
        }
    }

    fn move_(&mut self, amount: i8) {
        if amount < 0 {
            self.pos -= amount.abs() as usize;
        } else {
            self.pos += amount as usize;
        }
        while self.pos >= self.data.len() {
            self.data.push(0);
        }
    }
}

type Op = Box<dyn Fn(&mut Tape)>;

fn bf_parse<It>(it: &mut It) -> Vec<Op>
where
    It: std::iter::Iterator<Item = char>,
{
    let mut ops = Vec::<Op>::new();

    loop {
        let c = if let Some(c) = it.next() {
            c
        } else {
            break;
        };

        ops.push(match c {
            '+' => Box::new(|tape| tape.inc(1)),
            '-' => Box::new(|tape| tape.inc(-1)),
            '>' => Box::new(|tape| tape.move_(1)),
            '<' => Box::new(|tape| tape.move_(-1)),
            '.' => Box::new(|tape| {
                use std::io::Write;

                print!("{}", tape.get() as char);
                std::io::stdout().flush().unwrap();
            }),
            '[' => {
                let inner_ops = bf_parse(it);
                Box::new(move |tape| {
                    while tape.get() != 0 {
                        bf_run(tape, &inner_ops);
                    }
                })
            }
            ']' => break,
            _ => continue,
        });
    }

    ops
}

fn bf_run(tape: &mut Tape, ops: &Vec<Op>) {
    for op in ops {
        op(tape);
    }
}

fn main() {
    let fname = std::env::args().nth(1).expect("Expected filename arg");
    let ops = bf_parse(
        &mut std::fs::read_to_string(fname)
            .expect("Failed to read file")
            .chars(),
    );
    bf_run(&mut Tape::new(), &ops);
}

enums.rs

struct Tape {
    pos: usize,
    data: Vec<u8>,
}

impl Tape {
    fn new() -> Tape {
        Tape {
            pos: 0,
            data: vec![0],
        }
    }

    fn get(&self) -> u8 {
        self.data[self.pos]
    }

    fn inc(&mut self, amount: i8) {
        if amount < 0 {
            self.data[self.pos] -= amount.abs() as u8;
        } else {
            self.data[self.pos] += amount as u8;
        }
    }

    fn move_(&mut self, amount: i8) {
        if amount < 0 {
            self.pos -= amount.abs() as usize;
        } else {
            self.pos += amount as usize;
        }
        while self.pos >= self.data.len() {
            self.data.push(0);
        }
    }
}

enum Op {
    Inc(i8),
    Move(i8),
    Print,
    Loop(Vec<Op>),
}

fn bf_parse<It: std::iter::Iterator<Item = char>>(it: &mut It) -> Vec<Op> {
    let mut ops = Vec::new();
    loop {
        let c = if let Some(c) = it.next() { c } else { break };
        ops.push(match c {
            '+' => Op::Inc(1),
            '-' => Op::Inc(-1),
            '>' => Op::Move(1),
            '<' => Op::Move(-1),
            '.' => Op::Print,
            '[' => Op::Loop(bf_parse(it)),
            ']' => break,
            _ => continue,
        });
    }
    ops
}

fn bf_run(tape: &mut Tape, ops: &Vec<Op>) {
    for op in ops {
        match op {
            Op::Inc(n) => tape.inc(*n),
            Op::Move(n) => tape.move_(*n),
            Op::Print => {
                use std::io::Write;
                print!("{}", tape.get() as char);
                std::io::stdout().flush().unwrap();
            }
            Op::Loop(inner_ops) => {
                while tape.get() != 0 {
                    bf_run(tape, inner_ops)
                }
            }
        }
    }
}

fn main() {
    let fname = std::env::args().nth(1).expect("Expected filename arg");
    let ops = bf_parse(
        &mut std::fs::read_to_string(fname)
            .expect("Failed to read file")
            .chars(),
    );
    bf_run(&mut Tape::new(), &ops);
}

run.sh

for f in traits enums closures; do
  echo "$f"
  rustc -C opt-level=3 "$f.rs"
  "./$f" bench.b  # run once so MacOS can scan it or whatever it does
  time "./$f" bench.b
done

traits.rs

struct Tape {
    pos: usize,
    data: Vec<u8>,
}

impl Tape {
    fn new() -> Self {
        Tape {
            pos: 0,
            data: vec![0],
        }
    }

    fn get(&self) -> u8 {
        self.data[self.pos]
    }

    fn inc(&mut self, amount: i8) {
        if amount < 0 {
            self.data[self.pos] -= amount.abs() as u8;
        } else {
            self.data[self.pos] += amount as u8;
        }
    }

    fn move_(&mut self, amount: i8) {
        if amount < 0 {
            self.pos -= amount.abs() as usize;
        } else {
            self.pos += amount as usize;
        }
        while self.pos >= self.data.len() {
            self.data.push(0);
        }
    }
}

trait Op {
    fn run(&self, tape: &mut Tape);
}

struct Inc(i8);
struct Move(i8);
struct Print;
struct Loop(Vec<Box<dyn Op>>);

fn bf_parse<It>(it: &mut It) -> Vec<Box<dyn Op>>
where
    It: std::iter::Iterator<Item = char>,
{
    let mut ops = Vec::<Box<dyn Op>>::new();

    loop {
        let c = if let Some(c) = it.next() {
            c
        } else {
            break;
        };

        ops.push(match c {
            '+' => Box::new(Inc(1)),
            '-' => Box::new(Inc(-1)),
            '>' => Box::new(Move(1)),
            '<' => Box::new(Move(-1)),
            '.' => Box::new(Print),
            '[' => Box::new(Loop(bf_parse(it))),
            ']' => break,
            _ => continue,
        });
    }

    ops
}

impl Op for Inc {
    fn run(&self, tape: &mut Tape) {
        tape.inc(self.0);
    }
}

impl Op for Move {
    fn run(&self, tape: &mut Tape) {
        tape.move_(self.0);
    }
}

impl Op for Print {
    fn run(&self, tape: &mut Tape) {
        use std::io::Write;

        print!("{}", tape.get() as char);
        std::io::stdout().flush().unwrap();
    }
}

impl Op for Loop {
    fn run(&self, tape: &mut Tape) {
        while tape.get() != 0 {
            bf_run(tape, &self.0);
        }
    }
}

fn bf_run(tape: &mut Tape, ops: &Vec<Box<dyn Op>>) {
    for op in ops {
        op.run(tape);
    }
}

fn main() {
    let fname = std::env::args().nth(1).expect("Expected filename arg");
    let ops = bf_parse(
        &mut std::fs::read_to_string(fname)
            .expect("Failed to read file")
            .chars(),
    );
    bf_run(&mut Tape::new(), &ops);
}

The result:

traits
ZYXWVUTSRQPONMLKJIHGFEDCBA
ZYXWVUTSRQPONMLKJIHGFEDCBA
"./$f" bench.b  1.52s user 0.00s system 99% cpu 1.532 total
enums
ZYXWVUTSRQPONMLKJIHGFEDCBA
ZYXWVUTSRQPONMLKJIHGFEDCBA
"./$f" bench.b  1.88s user 0.00s system 99% cpu 1.886 total
closures
ZYXWVUTSRQPONMLKJIHGFEDCBA
ZYXWVUTSRQPONMLKJIHGFEDCBA
"./$f" bench.b  1.21s user 0.00s system 99% cpu 1.221 total

Using traits and Box<dyn Op> is actually faster (consistently so) than a match on an enum in a for loop 🤯

EDIT: Using Fn(&mut Tape) and closures to represent opcodes is even faster than the solution using traits 🤯