Reading Material about Interpreters and VMs

[Robbepop]

Here I just want to collect some interesting papers about interpreters and virtual machines which could help wasmi in the future.

• The Structure and Performance of Efficient Interpreters
  • Very classic paper about the architectural designs and structure of efficient interpreters generally. The key take-away is that the performance of efficient interpreters is dominated by branch mispredictions due to instruction dispatch therefore proposing methods and techniques to reduce those branch mispredictions.
• Optimizing direct threaded code by selective inlining.
  • Talks about an optimization during translation phase of the interpreter bytecode. In wasmi's case this would affect the translation of Wasm bytecode to wasmi bytecode. It extends direct-threaded code by inlining common code sequences which is made possible by "abusing" a GCC C extension that is not available to Rust, yet.
• A fast in-place interpreter for WebAssembly
  • The paper presents and describes the architecture of an in-place WebAssembly interpreters. That means that the interpreter (mostly) interprets the raw WebAssembly bytecode instead of "rewriting" the WebAssembly bytecode into an internal bytecode such as wasmi, Wasm3 and iwasm interpreters are doing. This reduces the memory consumption. The paper argues that with significant engineering effort, hand-crafted assembly and side tables acting as caches to crucial execution information the downside of reduced execution performance can be mitigated entirely.
• A fast WebAssembly Interpreter design in WASM-Micro-Runtime
  • In this technical preview paper from Intel the architecture and design of their new efficient iwasm interpreter are presented. It shows the steps taken in order to optimize their slower "classic" interpreter, displays difficulties during the implementation and their proposed solutions as well as giving a quick run and outlook about the performance improvements and future gains.
• Simple and Efficient SSA Construction
  • This paper proposes a novel algorithm to construct SSA bytecode from a reducible control flow graph. While SSA bytecode usually is not used in interpreters it is still interesting since WebAssembly was designed to form a reducible control flow graph and thus this efficient algorithm is applicable to all WebAssembly modules. My assumption is that all non-singlepass Wasm JIT compilers are using this algorithm to construct their SSA bytecode or a similar version of it. The downside is that the performance of this algorithm is still not linear-time with respect to the input Wasm bytecode. Furthermore there are papers about efficient interpretation and register allocation of SSA bytecode.
• RegCPython: A register based CPython implemetation
  • This paper discusses in detail how the authors implemented a register machine interpreter for the popular CPython implementation that uses a stack machine approach itself. The authors conclude that a register machine approach for CPython yields better runtime performance while having similar translation time performance.
• The Implementation of Lua 5.0
  • Describes techniques and methods used to craft the register-machine based interpreter for Lua 5.0 and compares its performance with the stack-machine based Lua 4.0. Also goes in depth with other Lua specific optimizations that shows how important those details are, too.
• Crafting Interpreters
  • Actually not a scientific paper but I think this book about crafting virtual machine interpreters cannot be left out here.