Tail-Call Interpreters in Rust – Jimmy Ostler

Inspired by an article on VM dispatch in Scala, Jimmy Ostler embarked on an experiment to implement and benchmark various dispatch styles in Rust, with a keen focus on leveraging tail-call interpretation for performance. The exploration systematically breaks down how different approaches impact a VM's efficiency.

• The article first introduces tail-call interpretation, a compilation technique essential for functional languages to prevent stack overflows by transforming recursion into jumps.
• It details the implementation of a simple stack machine with five instructions, showcasing four dispatch styles: Switch, Subroutine, Indirect, and Direct dispatch. Each style is presented with Rust code snippets, highlighting considerations like static mut and unsafe.
• Initial benchmarks for the stack machine reveal Direct dispatch as significantly faster, with a performance nearly twice that of Indirect dispatch and substantially better than Subroutine and Switch dispatch.
• The author then extends the experiment to a more complex 16-bit register machine, better reflecting typical VM architectures and his ternary project.
• Again, all four dispatch styles are implemented and benchmarked for the register machine, with Direct dispatch emerging as the performance leader, although the relative performance order of other methods shifts slightly.
• Finally, the article touches upon advanced control flow capabilities enabled by these tail-call techniques, citing the wasm3 virtual machine architecture as an example for handling exceptions and privileged execution.

Ultimately, the author concludes that these tail-call-driven dispatch methods offer a natural and highly efficient way to design VM event loops, providing significant control flow advantages and mitigating stack overflow risks compared to traditional switch-based dispatch, especially with Rust's explicit tail-calling capabilities.