{'fraction_non_alphanumeric': 0.03158320723510575, 'fraction_numerical': 0.007425132843016504, 'mean_word_length': 4.889637305699482, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A fast in-place interpreter for WebAssembly

WebAssembly (Wasm) is a compact, well-specified bytecode format that offers a portable compilation target with near-native execution speed. The bytecode format was specifically designed to be fast to parse, validate, and compile, positioning itself as a portable alternative to native code. It was pointedly not designed to be interpreted directly. Instead, design considerations at the time focused on competing with native code, utilizing optimizing compilers as the primary execution tier. Yet, in JIT scenarios, compilation time and memory consumption critically impact application startup, leading many Wasm engines to later deploy baseline (single-pass) compilers. Though faster, baseline compilers still take time and waste code space for infrequently executed code. A typical interpreter being infeasible, some engines resort to compiling Wasm not to machine code, but to a more compact, but easy to interpret format. This still takes time and wastes memory. Instead, we introduce in this article a fast in-place interpreter for WebAssembly, where no rewrite and no separate format is necessary. Our evaluation shows that in-place interpretation of Wasm code is space-efficient and fast, achieving performance on-par with interpreting a custom-designed internal format. This fills a hole in the execution tier space for Wasm, allowing for even faster startup and lower memory footprint than previous engine configurations.


Whither the Interpreter?
Seemingly overlooked in this development arc is the obvious choice of using an interpreter to execute bytecode. After all, traditionally, virtual machines are developed with an interpreter first. There are a lot of advantages to interpreters.
(1) Since interpreters are easier to write, understand, and maintain, they allow more rapid experimentation in bytecode design. (2) Since they need no translation or rewriting step, start up is fast.
(3) Bytecode is usually more compact than machine code, so interpeters generally use less memory than compilers. (4) Debugging application code is easier, as the interpreter loop can be stopped at any instruction and program state inspected, altered, and resumed. (5) Interpreters are easier to audit, since there is a fixed amount of code, and usually have fewer security vulnerabilities. (6) Dynamic code generation is sometimes impossible, either because is not allowed on the platform, like iOS, or code space is limited.
For all these reasons, nearly all virtual machines, from pioneering work on Lisp to Smalltalk to Self, to today's broadly-accepted VMs such as the Java Virtual Machine, the CLR, Python, Ruby, and JavaScript, have an interpreter.
Why then, is Wasm any different? The answer is simply that efficient interpretation was explicitly not in the design criteria 1 . But some Wasm engines do indeed employ interpreters, such as JavaScriptCore, Chakra 2 , and Wasm3. These engines use interpreters for exactly the advantages listed above. Yet none of these interpreters work directly on the original bytecode; all of them rewrite Wasm bytecode to a different internal format. Rewriting Wasm bytecode has similar disadvantages to baseline-compiling: it still takes time and memory.

The Final Tier is Shed
There is an important point missing in the Wasm virtual machine design tradeoff space. An in-place interpreter, i.e. one that interprets the original bytes of a binary module, would offer the best startup time and lowest memory consumption. For cold or never executed code, where the downside of the interpreter's much slower execution speed is outweighed by the major savings of avoiding translation time, it would be the optimal choice. Employed in concert with compilation tiers for hot code, such an interpreter would serve the role it does in other mature systems like JVMs. Is it possible to interpret Wasm in-place efficiently? Until now, this was thought infeasible. In this work, we solve this open problem and supply the missing point in the design tradeoff space: the first fast in-place interpreter for Wasm (empirical measurements in Figure 1&2). We first identify the interpreter-crucial information that is missing in Wasm's bytecode design. This information, namely key control-flow and value stack information, is not actually missing, but rather implicit. Our insight is that the validation algorithm for Wasm bytecode already computes this information in its modeling the control and value stack during typechecking. All that remains is to distill a few key numbers into a compact side-table that is used during interpretation. The side-table is organized so that all accesses occur in constant ( (1)) time, and no searches of the table are necessary. Thus the interpreter always has relevant information directly at hand and behaves like a standard interpreter. Other details are important for making a fast interpreter as well, such as hand-coding key parts in assembly and combining exactly the right layout of value stack and virtual memory protections to robustly handle application stack overflow without needing any explicit checks.
With these new techniques, we have finally achieved an in-place interpreter for Wasm that is on par with state-of-the-art interpreters for other bytecodes and for Wasm interpreters using rewriting. This paper completes the triad of basic tier designs (interpreter, fast compiler, optimizing compiler) for Wasm. In a comical twist of fate, Wasm's tiers have arrived exactly backward!

Organization
The remainder of this paper is organized as follows. Section 2 recaps the design of Wasm's functions, stack machine, and control flow constructs, which are key to understanding why interpretation has been challenging until now. Section 3.1 shows the design of the side table used for the interpreter and how the validation algorithm already contains the key information necessary to emit the side table in a single pass. Section 3 details the interpreter implementation, including key assembly techniques to achieve the best-performing dispatch loop, and the design of the data structures necessary to make a fast operand and execution stack. Section 4 evaluates the interpreter on standard benchmarks and compares translation time, memory consumption, and execution time to JITs (4.4.1) and other interpreters (4.4.2) for Wasm. Prior work related to optimizing interpreters is summarized in Section 5, followed by the conclusion.

WASM DESIGN
Wasm provides a low-level programming model consistent with its original goal of a minimal, high-performance abstraction over hardware. Its principal features include: • i32, i64, f32, f64, and v128 primitive types • an opaque reference type The Wasm binary format is designed to be compact yet fast to decode and validate in a single pass. This includes not just bytecode, but all constructs.

Modules and Instances
Wasm code is organized into modules which are in turn organized into a list of sections. Sections in a module declare functions, memories, tables, global variables and static data. Bytecode is grouped into functions with statically-typed parameters, results, and local variables. All operations in core Wasm manipulate only a module's own internal state. Modules must import functions (and memories, tables, etc) in order to access platform capabilities or state outside the module. Imports may be provided by the "host" environment, such as JavaScript and the Web, or from other modules.
A module is akin to an executable file, or part of one, rather than an executing program. To run, a module must be instantiated, supplying bindings for its imports. At instantiation time, a Wasm engine creates the state (tables, globals, and memories) declared by the module, with the result being called an instance. An instance may export its own functions, memories, tables, etc. to other modules or the host environment.
The primary dynamic storage of a Wasm program is typically one large, bounds-checked, byteaddressable memory, but global variables and tables of opaque host references can also be used. Future proposals will add first-class function references and garbage-collected objects to Wasm. These too are forms of local state and must be shared explicitly with other instances.

Bytecode design
Functions. All code 3 in Wasm is organized into functions. Functions each have a signature with a fixed number of parameter and result types, such as [i32 f32 externref] -> [i32 i32]. Execution of a Wasm program entails executing functions that may call each other, maintaining an execution stack 4 that stores their local variables and operands, and running their internal code. In a binary module, the body of a Wasm function begins by declaring the number and type of their additional local variables, followed immediately by the bytecode.
Stack machine. As is common for many bytecode designs, Wasm is a stack machine, meaning individual bytecode instructions take their operand values from an operand stack and push their results back. Local variables are separate. To be used, a local must be explicitly loaded onto or stored back from the operand stack. Implementations typically store them internally as a prefix of the operand stack, together referred to here and throughout as the value stack. The arguments of an outgoing function call become the first locals of the callee function.
Structured control flow. Unlike most bytecode designs, however, Wasm has structured control flow constructs such as blocks, ifs, loops, and switches that are encoded inline in the bytecode. We refer to them as structured, since they must be properly nested. This was a deliberate choice for compactness and to ensure that bytecode validation can be done in a single pass with minimal data 3 other than trivial initializers for globals 4 Note that the execution stack is not aliased by Wasm memory, thus not vulnerable to stack smashing structures 5 . In contrast, a typical bytecode design with jumps usually requires more bytes to store and two passes to verify.
Direct interpretation not straightforward. Most bytecode formats can be interpreted directly in their binary form (i.e. in-place), with an instruction pointer stepping through the bytes of the original code. Jumps typically have an offset or instruction number of the target instruction directly in the bytes, allowing a constant-time adjustment of the instruction pointer. But Wasm is unusual in that a branch instruction specifies a target construct by relative nesting depth, transferring control to the beginning (in case of loop), middle (in the case of if) or end (for block, if, else) of the construct. Wasm is also unusual in that branches can also copy and pop values off the operand stack 6 . Thus a direct Wasm interpreter faces two unusual problems when executing a branch: • can't quickly find the target bytecode offset, e.g. start of a loop or end of a block • can't determine how many values to pop off the operand stack To understand how this paper efficiently solves this open problem, we must first journey deep into how Wasm bytecode validation is done in production-quality engines.

Bytecode validation
Wasm, though low-level, is typed. A number of static checks ensure that a module is well-formed. Within a function, all instructions, including arithmetic, calls, control flow, etc. must be applied to the correct number and type of operands. All control flow constructs must be properly nested with no invalid branches. In the specification, this validation is expressed in a standard type system formalism. In engines, the algorithm is implemented as an abstract interpreter that models an abstract control and value stack. We describe such an implementation here to later make it clear how our modifications affect an already very efficient verification implementation. Figure 3 illustrates the operation of a production quality Wasm code validator. Three primary data structures are used.
• The module environment models the types of functions, tables, globals, and number of memories of the enclosing module. The module environment is not mutated during verification of a function's bytecode. • An abstract control stack models the nested control-flow constructs, keep tracking of where each starts and its expected parameter and result types 7 . This is used to properly match block, if, and loop starts with their else and/or end. • An abstract value stack tracks abstract values for stack slots and local variables. In current Wasm, abstract values are simply value types, i.e. i32, i64, externref, etc. If a future proposal introduces flow-sensitive validation, the abstract values for locals would need to be extended to include initialization information. The validation algorithm proceeds in a single forward pass over the bytecode, never needing to backtrack. For simple instructions like arithmetic or calls which only pop their operands from the value stack and push results back, the algorithm pops and checks required input types and pushes resulting output types. Control-flow instructions are validated using the control stack. For example, a br (branch) instruction references the target block or loop by relative nesting depth; the validator matches the opening construct by indexing into the control stack. Since, in Wasm block, if, and loop can have parameter and result types, the validator must check that the value stack contains the appropriate types expected for the target construct.
Importantly, an end bytecode closes a control-flow construct, either a block, if, loop, or the whole function. At end, all branches that can legally target the construct have been seen. Thus the implicit target bytecode offset of all branches to this construct are known, because that offset must be either the start of a loop or, for any other construct, the end, i.e. here. This information just needs to be saved somewhere easily accessible for the interpreter. After processing end, the algorithm pops the control stack entry and can reuse its storage space, which is optimally efficient.

INTERPRETER DESIGN
In this section, we present our fast in-place Wasm interpreter design.
The key enabling techniques are: • an innovative side-table design which allows efficient access to missing branch information • a highly efficient value stack organization for (1) local variable and operand access as well as zero-copy function calls Additionally, we chose to implement the core logic of the interpreter in hand-written assembly language 8 , which allows for near-perfect register allocation and unlocks all possible dispatch and organization techniques. We discuss the rationale for hand-written assembly at the end of this section.

Sidetable Design
As we've seen, Wasm control-flow bytecodes represent nested control constructs, rather than low-level jumps. However, an interpreter needs the bytecode offset of where to go if a branch is taken, ideally in (1) time. This includes not only explicit branches like br, br_if, br_table, but also the implicit branch in else. Note that block, loop, end and return are not branching bytecodes, since they either fall through or exit the function.
To supply the in-place interpreter with the missing information, the validation algorithm saves a portion of its work into a per-function side-table data structure separate from the original bytecode. This side-table is a compact, highly-efficient mapping from branch origin to target offset, plus some additional stack manipulation information.  To make the data structure time-and space-efficient, it consists of entries sorted by branch origin and omits non-branch instructions. It is emitted as a side-effect of the single-pass validation algorithm above. Because the validation algorithm already visits bytecodes in forward order, it simply emits branch entries as it goes, obviating a separate sorting step. Since only branches need entries, the sidetable is very small, often empty. Empirically, most Wasm functions are small with no control flow, so they have no side-table at all.
Every entry in the side-table is a 4-tuple of the form ⟨Δip, Δstp, valcnt, popcnt ⟩, where: • Δip the amount to adjust the instruction pointer by if the branch is taken • Δstp the amount to adjust the side-table pointer by if the branch is taken • valcnt the number of values that will be copied if the branch is taken • popcnt the number of values that will be popped if the branch is taken 3.1.1 The Sidetable Pointer. Like most interpreters, our in-place interpreter maintains an instruction pointer (IP) into the bytecode during execution. It also maintains an end instruction pointer (EIP), which is used to check if the program falls off the end of the function, which is a legal implicit return in Wasm. To use the side-table, the interpreter simply maintains another pointer, the side-table pointer (STP), consulted when executing branches. Figure 4 illustrates the interpreter state for the bytecode and sidetable, and Listing 1 illustrates how side-table entries are used by the interpreter during execution. The instruction pointer (IP) is initialized to point directly into the bytecode and the sidetable pointer (STP) points at the first side-table entry. Branch instructions make use of the doControlTransferFromSTP() subroutine which adjusts both the IP and STP based on the entry to which it points, as well as adjusting the value stack. Notice that a conditional branch that is not taken still must update the STP so that it points at the next entry for the next branch, if any, in the code. Note that br_table works much like a jump table, computing an index into the side-table and using the corresponding entry.

Value stack design
Since Wasm bytecode constitutes a stack machine, nearly all instructions access the value stack, making it crucial for interpretation speed. A single indirection to local variables and the top of the operand stack is ideal. Wasm's numbering scheme for locals is inspired by JVM bytecode. Parameter #0 is local #0, followed by declared locals, then the operand stack. Outgoing arguments of a call become the first local variables of the callee function's value stack. The JVM chose this design so interpreters could overlap the value stack of the callee frame with the operand stack of the caller, avoiding copying any argument values. This never panned out for Wasm until now. Our design succeeds in using the JVM trick to avoid copying arguments, but requires separating the value stack from the execution stack. Figure 5 illustrates the value stack design. We separate the storage of Wasm program values from the control information of the interpreter itself. That is, the value stack contains only Wasm values, while the interpreter's call stack contains only control information, organized into one execution frame per Wasm call frame. As such, the value stack is a contiguous array of Wasm values which increases in size towards higher addresses. Though invisible to Wasm programs, and orthogonal to our design here, the interpreter frames are on the native stack and use the native stack pointer (e.g. %rsp on x86-64) which grows towards lower addresses.

Value tagging.
Wasm values can be 32-bit or 64-bit integers, 32-bit or 64-bit floats, 128-bit SIMD vectors, or external references. We choose to store all Wasm values in the value stack as unboxed, so that the interpreter never needs to implicitly allocate a heap object 9 . This obviously makes sense for all primitive values, since they can share storage as raw bytes in the memory of the value stack. However, an engine may need to find externref values in a value stack during garbage collection. Natively-compiling Wasm engines use stackmaps [30]. But an interpreter is different, and typically cannot afford either space or time to precompute stackmaps. Instead, we chose to tag value stack entries with a 1-byte type tag, inflating entries to be 32 bytes, i.e. really fat 10 . Type tags are written into the value stack only when necessary (i.e. when initializing locals in the function prologue, not at all for primitive arithmetic, etc). To be clear, type tags are never needed for any dynamic check, since Wasm code is statically typechecked. They can be omitted if there is no garbage collector or it uses conservative stack scanning [28].

Stack overflow.
Wasm engines must be robust to call stack overflow. The Wasm specification includes one test with unbounded recursive function calls. Every engine must fail gracefully, though the exact point where overflow is detected is not specified.
Checking for stack overflow should not ruin performance. A check on every value stack push would be prohibitive. Instead, we use a guard page at the end of the value stack and rely on an OS-level signal upon fault to catch and report stack overflow. A single guard page suffices, as the interpreter cannot inadvertantly stride over it; by design it never accesses arbitrarily far ahead. Similarly, interpreter execution frames (on the native stack) are all fixed size and another guard page 11 will cause a fault if the native execution stack overflows before the value stack.

3.2.3
Putting it all together. At this point, we've designed two critical data structures necessary to make an efficient in-place interpreter. Figure 6 completes the set of 9 state registers used by our interpreter implementation. In addition to the 3 "control" registers pointing into the bytecode and sidetable and the two "data" pointers into the value stack, the interpreter also requires: • MEM a pointer to the start of the wasm memory 12 • FUNCTION a reference to the current function • INSTANCE a reference to the current instance • DISPATCH for dynamically enabling per-instruction probing

Interpreter implementation in assembly
We chose to implement our interpreter in a new Wasm research engine, wizard [60]. While most of the engine is written in a portable, safe, high-level language [59], we use custom hand-written assembly for the fast interpreter. Using assembly or a custom code generation facility is relatively common for production interpreters. For example, the Java HotSpot virtual machine generates its interpreter [1] using a macro assembler (at startup), V8's Ignition [14] interpreter is generated from hand-written TurboFan compiler IR (at build time), and JSC's LLint is written in a macro assembler language (build time). Several factors impinge on our decision.
(1) an interpreter is a small, important piece of code (2) the bytecode format and semantics of Wasm are very stable (3) compilers have trouble generating optimal code for interpreter loops (4) we wish to study interpreter performance in detail (5) key dispatch techniques are difficult to obtain from compilers (6) developing and debugging assembly code is relatively time consuming Key advantages of using assembly to implement an interpreter are 1) its code is not perturbed by changing compiler optimizations, 2) key interpreter state can be fixed to specific architectural registers, 3) threaded [20], indirect-threaded [29], and other dispatch techniques can be used, 4) handlers can be ordered and aligned cache line boundaries, 5) fast-and slow-paths can be organized inline or out-of-line, 6) all hardware instructions can be used, 7) self-modifying code and dispatch table swap techniques can be used, 8) error handling and hard cases can be factored from handlers, 9) very small resultant code footprint.
The interpreter that we present in this paper makes use of nearly all of these techniques. It is implemented using a macro assembler that generates x86-64 machine code, has many switches to enable different features, and provides an instrumentation interface for profiling and debugging. It consists of 2800 source lines of code which generate approximately 14KiB of machine code and 7KiB of dispatch tables.

Dispatch tables and handlers.
Wasm is a bytecode in the true sense of the word. An instruction is encoded as a byte-sized opcode, followed by zero or more immediates. Longer instructions are preceded by prefix byte. It is natural therefore to design a software interpreter around 256-entry dispatch tables that contain pointers to handlers that implement each bytecode. Figure 7 illustrates the dispatch table and handler organization for our fast Wasm interpreter.
The fast interpreter uses multiple dispatch tables, each of which points to a sequence of machine code called a handler. A dispatch through a table consists of loading the address at a particular index and indirectly jumping to that address. The first dispatch table, the main dispatch table, is used for the first byte of an instruction. Since the most important bytecodes in Wasm were assigned a non-prefixed opcode, the first dispatch through the main table normally lands in a handler that will directly execute the bytecode.
Prefix dispatch tables handle the tricky but rare corner cases. If the first byte of an instruction is a prefix, then the target address in the main table will be a special handler that loads the next byte in the instruction stream and dispatches through the appropriate table. There is still one more wrinkle, however. Wasm is unusual in that the opcode after a prefix can be a variable-length LEB [16], where the uppermost bit of the byte indicates continuation bytes follow. Thus, in prefix dispatch tables, entries for the upper 128 opcodes (i.e. where the upper bit is 1) point to another special handler that fully decodes the LEB and finally dispatches to an actual bytecode handler, using yet another dispatch table. Of current Wasm bytecodes, only the SIMD opcodes occupy the upper part of their prefix space (0xFD). Thus, in practice, Wasm opcodes normally require just one dispatch, two if prefixed, and maximum three if the LEB opcode is longer than 1 byte.
3.3.2 Direct vs threaded dispatch. Each bytecode handler consists of machine instructions that manipulate the value stack or module instance or perform control flow. A handler usually simply leaves the interpreter registers ready to start the next bytecode pointed to by IP, except for instructions like unreachable and return, which will terminate execution or return from the current interpreter frame, respectively.
Conceptually an interpreter has a single loop that repeatedly dispatches one instruction at a time, each handler jumping back to the loop header. Nowadays, a technique known as threaded dispatch [58] is often used, where instead of a jump, a copy of the dispatch code is inlined at the end of each handler. This is difficult to do in a high-level language 13 , but easy in assembly. This saves a jump instruction and typically makes better use of the CPU's indirect branch predictor. We implemented both and report the performance difference in Section 4.
3.3.3 Debugging and instrumenting with probes. One of the motivating advantages for an interpreter tier in any virtual machine is ease of debugging and instrumentation. In particular, an interpreter implements an exact bytecode-by-bytecode emulation of the machine, offering the possibility of stopping before or after any bytecode and inspecting the virtual machine state. This is key to support both high and low-level debugging of a program as well as instrumentation such as profiling.
Our fast interpreter design has provisions for general instrumentation at the bytecode level. It offers the ability to insert probes [61] at either local locations in a program, or global, the interpreter loop itself. Both have different use cases. A probe is simply a callback to engine-level code that fires when the given bytecode is executed, or each time the interpreter loop is executed. In a probe callback, one can inspect virtual machine state through an engine API and then indicate if the 13 Compilers generally will not transform a straight-forward loop-over-switch into threaded dispatch, as the necessary transformation, tail-duplicating the loop header for many hundreds of cases, is highly specific. Instead, we must arduously fill out manual dispatch tables and either use tail calls or, in C, the non-standard gcc "labels as values" [15] extension. The resulting control flow is complex, with multiple irreducible loops and hundreds of indirect branch targets, and may lead to spills across important instructions. To use tail calls, we must rewrite the entire interpreter as individual handler functions that end with a tail-call to the next handler (as is done in Ignition [14]), passing the entire interpreter state forward as arguments. Yet only some C compilers support a non-standard tail-call optimization. In any case, without a custom calling convention, we run out of registers and spill some interpreter state on the stack unnecessarily. program should resume normally or do something else (typically, terminate). Probes are primitives from which debugging support (e.g. breakpoints), tracing support (e.g. logging), or profiling support (e.g. counters), are built. Figure 7 shows how the fast interpreter supports probes.
• Local probes. For a probe inserted at a particular instruction, the original bytecode of the function containing the location is copied and the bytecode is overwritten with a special, normally-illegal bytecode, PROBE. Since illegal bytecodes will be rejected by the code validator, they will never appear in valid programs. Dispatching on PROBE will land in a special handler that looks up the user's callback associated with this bytecode, calls it, and then after, loads the original bytecode and dispatches through the main table. • Global probes. For a probe inserted into the global interpreter loop, the interpreter switches modes, using the probe dispatch table for every instruction. Similar to the local probes, the interpreter looks up the global instrumentation, calls it, and then after, dispatches through the main table.
It's important to note that this design allows probes to be inserted and removed dynamically. This allows maximum flexibility to instrumentation code while allowing the interpreter to run at full speed otherwise. For example, suppose a user wants to trace the execution of just one particular function in a module. They could insert global instrumentation into the main interpreter loop and filter out all callbacks where the function of interest is not on the top of the stack. But this is inefficient; the interpreter will go through the probed table every time, issue calls into the runtime, into the user code, which inspects state, etc. A more efficient way is to insert a local probe into the interesting function. When the local probe is fired, it dynamically inserts the global probe, thereby getting called for every subsequent bytecode. When the function calls another, or when it returns, the global probe can be disabled, and everything goes back to full speed. The interpreter is careful to switch back to the main dispatch table whenever it detects global instrumentation is disabled, so it will always run fast when it has opportunity to do so.

Tuning
Considerable work has gone into designing efficient data structures and dispatch tables for the fast interpreter presented here. We'd be remiss in not enumerating the many other tuning strategies applied here and what we've learned. This was made easier by the fact that the fast interpreter presented here was implemented not in textual assembly language, but in a macro assembler framework we built in a high-level language. Thus configuration options were easy to introduce into the code that generates the interpreter, rather than relying on macro facilities in a textual assembly language.
• Manual register allocation. The fast interpreter state consists of 9 registers ( Figure 6). All of today's 64 bit architectures have enough architectural registers that it is simply a matter of assigning interpreter registers to architectural registers. For x86-64, we chose register assignments carefully to eliminate REX prefixes for the most commonly-occurring registers. We did not measure alternative assignments, but suspect that CPU register renaming makes additional tuning moot. • Minimal dispatch sequence. In addition to the choice between threaded and non-threaded dispatch, we experimented with dispatch table designs where entries were 2, 4, and 8 bytes.
In the 2 byte design, entries are not direct addresses, but deltas that are applied to the start of a code region, requiring an additional add instruction in the dispatch sequence. In the 4 and 8 byte alternatives, the entries are direct addresses, constrained to be in the lower 4gb of address space in the former case. Of these alternatives, the 4 byte sequence is fastest, often as much as 10% faster. Unsurprisingly, we found threaded dispatch is fastest, on average 14%, maximum 29% faster. • Value tagging. Our interpreter design uses value tags to find GC roots when necessary.
We evaluated the alternative and found that eliminating tags improves performance, on average 8%, maximum 15% faster. • Really fat values. SIMD values are 128 bits wide. When coupled with value tagging, values occupying 32 bytes of memory each in the value stack. • Inline/out-of-line LEB decoding. The interpreter must dynamically decode the many immediates in Wasm that are encoded as variable-length LEBs, e.g. the index of a local.get.
Often these variable-length immediates are just a single byte. We experimented with moving the uncommon case out-of-line and concluded that out-of-line LEB slow cases could be as much as 5% faster. • Memory #0 base pointer. Wasm programs access memory very frequently. As described earlier, our implementation caches a pointer to the base of the (first) Wasm memory in an architectural register. We did not evaluate the performance impact of this optimization. • Handler alignment. Bytecode handlers are short but critically important sequences of code.
We suspected they may be subject to microarchitectural effects of instruction and trace caches arising from code alignment. We experimented with 1, 2, 4, 8, 16, and 32 byte alignment of handlers but detected no statistically significant performance variation. • Handler order. We suspect that handler code order may introduce significant microarchitectural effects [45] [26]. However, we did not study the effect of handler order beyond simply emitting common bytecode handlers first. • Error case sharing. Several Wasm bytecodes trap on error cases, like divide by zero, unrepresentable floats, etc. We factored the error handling paths in order to save space. Since traps usually terminate the program, the performance does not matter. • Call/entry/exit sharing. We exploit commonalities among call bytecodes (call, call_indirect, and tail calls 14 ), return/fall-through, as well as branches in order to save code space. This may have a small effect on performance, but we did not measure this. • Handler sharing. We exploit the fact that some instructions end up with identical handler code and share the handlers (e.g. block and loop, some memory stores). We did not measure alternatives. The above conclusions are supported by a performance evaluation of alternatives that is beyond the scope of this paper. To summarize those experiments, the overall difference between the best (tuned) and worst (untuned) interpreter performance is 20% to 60% across the benchmark suite. Interestingly, as we will see in the next section, this difference is enough to make our interpreter design meet and exceed existing (re-writing) interpreters in comparative performance tests.

EVALUATION
In this section, we evaluate our Wasm interpreter against many state-of-the-art Wasm engines. The goal is to assess our claim that an in-place interpreter supplies the missing point in the execution tier tradeoff space between translation time, space overhead, and execution time. In particular, an in-place interpreter should offer superior translation time and space overhead compared to other tiers. Ideally, such an interpreter should also have comparable execution time to existing interpreter tiers. Of course we expect that interpreters should be handily outclassed by JIT compilers for long-running programs, so we shouldn't expect to replace them. Our experiments quantify the tradeoff space empirically.

Wasm Engines in 2022.
Today, five years after support was announced in 4 major browsers, engines are significantly different, and many new competitors have appeared. In particular, Web engines have evolved significantly from what has been reported in the literature to date. Today, all Web engines are sophisticated multi-tier systems.
• V8 [11] -two compiler tiers. V8 eagerly compiles the entirety of a module with Liftoff [3], a baseline compiler, with many parallel threads. Upon completing baseline compilation, a module is ready to run. Optimized compilation with TurboFan [4], the optimizing compiler shared with JavaScript, is begun in parallel in the background. Optimized code gradually replaces baseline code as it is finished, until all functions in a module are fully optimized. Either compiler can be disabled with command-line flags. . Dynamic counters tier-up hot functions from interpretation to BBQ, a fast compiler that has a minimal IR, and then to OMG, a fully optimizing compiler based on B3 [53]. Either compiler can be disabled with flags. • ChakraCore [44] -one interpreter tier and one compiler tier. Now largely unsupported, Wasm modules were not eagerly compiled. Instead, individual functions were lazily translated to interpreter bytecode. Dynamic counters tier-up hot functions from interpretation to a fully optimizing compiler. In addition to the rapid evolution of Web engines, a number of non-Web Wasm engines have appeared.
• wasmtime [13] -A standalone runtime implemented in Rust. One compiler tier. The optimizing Cranelift compiler can be used in JIT or AOT modes. Two interpreter tiers and one compiler tier, but only one at a time. The "classic" interpreter, we discovered, is an in-place interpreter that does not use a side table, but a control flow cache. The "fast" interpreter is a rewriting interpreter that reuses most of the standard Wasm bytecodes but rewrites control flow. Both interpreter loops are written in C and use gcc extensions for threaded dispatch, if possible. A one-pass JIT can be used instead. • wasm3 [8] -The self-proclaimed fastest WebAssembly interpreter 15 .
One interpreter tier. All design considerations emphasize interpreter performance. It is implemented using tail calls and relies on gcc tail-call optimization. The internal bytecode format consists of a list of function pointers to handlers, plus immediates, i.e. classic threaded code. • wasmer [12] -A standalone runtime for lightweight containers.
Three compiler tiers, one at a time. Packages two compilers from other projects: Cranelift (from wasmtime) or LLVM, and offers its own one-pass compiler.

Our Tier Choices.
We chose only to compare against execution tiers that perform dynamic translation, intentionally omitting those engines performing static (AOT) translation. Further, though this paper focuses on interpreter design, we include several experiments that compare engines with multiple tiers to understand their current tradeoffs. We therefore measure these execution tiering configuration: • wizard-Our engine with its in-place interpreter that uses a sidetable.
• wasm3 -Default configuration of a rewriting interpreter.
• sm-base -Spidermonkey with only the baseline compiler.
• sm-opt -Spidermonkey with only the optimizing compiler.
• jsc-bbq -JSC with the rewriting interpreter and BBQ quick JIT only.
• jsc-omg -JSC with the rewriting interpreter and OMG optimizing JIT only.

Benchmark setup
All tests were performed on a Linux 4.15 kernel on a machine with 32GiB of RAM and one Intel Core i7-8700K CPU @ 3.7GHz and the CPU governor set to "performance". Benchmarks used are the PolyBenchC-4.

Translation Time
All of our chosen execution tiers, except wizard and wamr-classic, the only other in-place interpreter of which we are aware, apply some form of translation to the input bytecode. Rewriters either generate an internal bytecode (interpreters) or machine code (compilers). Thus we measure the time taken for the respective translation by instrumenting the source code of each engine by adding time and space measurements. In the case of wamr-fast, the custom bytecode is generated as a side-effect of validation, so we measure the additional time for translation by subtracting the baseline validation time obtained from wasmr-classic, which has no translation time. wizard doesn't translate, but instead the reported time is the sidetable tracking and construction time, measured as the difference between validation time with and without sidetable tracking. We plot the average translation time, divided by the number of input bytes translated. The ratio of translation time to input bytes normalizes differences in tiering strategy (e.g. lazy compilation) and benchmark size. Figure 8 gives the results (note Y-axis is logarithmic).
Here we focus on configurations that isolate individual tiers, rather than multi-tier adaptive configurations. The experimental results show a dramatic difference in translation time for these tiers, nearly 3 orders of magnitude. Though baseline compilers often differ from optimizing compilers by more than 10×, they are still 10× more expensive than rewriting interpreters. Yet there is overlap, as the rewrite time of jsc-int, an interpreter, is almost on-par with v8-liftoff, a baseline compiler. Similarly, the jsc-bbq quick compiler is closer to an optimizing compiler, as it uses an IR, unlike v8-liftoff. The winner is clearly our in-place interpreter design, as the sidetable generation in wizard is a full order of magnitude cheaper than the cheapest rewriting interpreters.

Translation Space
Translation not only consumes time, but space. We measure the memory overhead of translation in terms of bytes generated per input byte of code. Here again, the ratio of output bytes to input bytes normalizes differences in tiering strategy (e.g. lazily compilation) and benchmark size. Note that we only measure the size of generated code (whether internal bytecode or machine code) and not additional metadata such as code objects or a source position table, which all rewriters need for debugging. We also do not measure per-module space costs. Thus this experiment underestimates space costs of rewriters when debugging is involved. Figure 9 gives the results.
There are several somewhat surprising results here. We find that some rewriting interpreters (such as wamr) can consume up to 4× as much space as the original bytecode, while others (such as jsc-int) consume about the same amount of space as the original bytecode. We believe this is because jsc-int uses an internal bytecode similar to JSC's JavaScript bytecode, which has been heavily tuned to reduce memory consumption on webpages. Also somewhat surprising is that JIT compilers, which generate machine code, do not necessarily consume more code space, in general, than rewriting interpreters, though jsc-bbq is an outlier. We discovered that wasm3, like wamr, often trades space for time-nearly all of its bytecode quantities are word-sized. Yet during rewriting, wasm3 does a number of peephole-like optimizations, globally canonicalizes constants, and uses a register machine internally, all of which save space.
These measurements show the sidetable in wizard takes far less space, only about 30% additional space compared to the original bytecode, as it only requires entries for control-flow 16 , and many sidetables are empty. That is a full order of magnitude more space-efficient than the other tiers, which typically cost 2× to 4× the original bytecode's space. Figure 10 gives the absolute execution times of the benchmarks for the v8-turbofan and wasm3 execution tiers. Execution times reported in other figures in this section are normalized to either of these two baselines.

Interpretation vs JIT compilation.
Interpreters start up faster, but have slower execution time compared to JIT compilers. But how much? We measured the execution time of the benchmarks in the six single-JIT tier configurations and the fastest interpreter that we measured, wasm3. Since the execution time of benchmarks varies by two orders of magnitude, we normalize execution times for each benchmark to the corresponding execution time on v8-turbofan. Figure 11 gives the results.
On the horizontal axis, we sorted the benchmarks by their execution time on wasm3 (same as in the table). As we can see, the shortest-running benchmarks on the left side of the graph do not run long enough to benefit from the work spent by the optimizing compiler, and all baseline compilers are faster, with the interpreter fastest. There is also a fixed cost of starting a relatively heavyweight JSVM, which contributes to the interpreter being fastest for the shortest 4 benchmarks. Moving to the right, as execution time increases with longer-running benchmarks, the fixed cost of startup and the   cost of compilation are increasingly amortized. Thus the middle of the graph shows more balanced results; the interpreter falls behind but the baseline compilers, particularly v8-liftoff, remain competitive. Continuing on, the gap between optimizing compilers (particularly v8-turbofan and sm-opt) and the rest increases; execution time is now dominated by code quality. Baseline compilers level off, with v8-liftoff and sm-base around 2× slower and jsc-bbq closer to 3×. The common rule of thumb that interpreters are 10× slower than JITs turns out to be roughly accurate in the end, as there is a clear trend towards roughly 10× for wasm3 vs v8-turbofan here. These results match our intuition, but better, quantify it, giving us fairly round numbers to reason with. They also reaffirm the need to have a broad picture of execution time: • Each of (interpreter, baseline compiler, optimizing compiler) runs some benchmark fastest.

Interpreter showdown.
Of course, this paper focuses on making a fast, in-place interpreter. Using similar benchmarking methodology, on the same benchmarks, we evaluated the five interpreter tiers. Figure 12 gives the results. As we found that wasm3 was consistently the fastest interpreter across the board, we chose to normalize all execution times in this graph to it. Here we find that wamr-fast, the configuration of the wamr engine with its rewriting interpreter, is consistently 2 nd fastest, nearly always 1.5× to 1.7× slower than wasm3, while the others are typically 2×-3× slower. We attribute this not only to wasm3's threaded code dispatch technique, but its several bytecode-level optimizations. Our design, wizard, performs better than the other in-place interpreter design, wasm-classic in most situations. It performs nearly equivalent to wamr-fast on the 4 shortest-running benchmarks.

4.4.3
Multi-tier configurations in context. Note that our experiments in this section focused on isolating individual execution tiers in order to study their tradeoffs. In production configurations, all web engines run in multi-tier configurations, as described in Section 4.0.1. The space for tiering designs is vast, with many variables, such as laziness, concurrency, thresholds for tiering up, on-disk caching, etc. We ran additional experiments for engines in their default configuration, but we found the the results are complex enough to merit study in their own right-a topic that is unfortunately beyond the scope of this paper.

Avoiding pathological behavior.
We discovered wamr-classic uses an in-place design just days before publication. Since then, we studied its implementation in earnest. It is written in C and uses gcc extensions to construct a jump table for threaded dispatch. The jump table is crucial for performance; disabling it via a configuration variable reduces performance by more than 2×, which reaffirms the need for this crucial optimization in interpreter design. Of course, we tested its fastest configuration, as 2× would have put it handily out of the running.
However we discovered that, instead of an (1) sidetable like our design, it uses both a dynamic control stack and a cache of control entries that help it find branch targets during runtime. The cache is a fixed-size, 128-element, 2-way set associative cache indexed by branch address. That amounts to a fixed cost per module, rather than per function (we did not include its space cost in Figure 9). A cache miss results in a slow path where the entire function may be rescanned to the end, repopulating the cache with new entries, including an entry for the current branch. The performance could be pathological for a large program with many branches, a fact obscured by the relatively small benchmark programs in our suite. To verify the pathological behavior, we constructed an adversarial program consisting of thousands of branches, approximating a larger program, and observed slowdowns of as much as 8×. This vulnerability was known to its authors and is one of the reason that wamr now ships the rewriting interpreter (wamr-fast) by default.
Given the potential pathological behavior of wamr-classic, we still believe that wizard represents the first viable fast in-place design.

RELATED WORK
Interpreters are as old as the hills. From the first popular interpreted language, Lisp [43] in 1960, to today's modern scripting and data manipulation languages like Python, Ruby, R, PHP, and MatLab, interpreter performance has been a key subject of interest. Many languages that are now fast through dynamic compilation were once primarily interpreted, such as Smalltalk, Self, Java, C#, OCaml, and JavaScript. Python is still most-often interpreted, and its performance is still of key concern [19] [68]. Because of their advantages, new interpreters continue to appear, even for languages previously compiled [38].
5.0.1 Fixed or flexible format? Research into interpreter techniques either assumes the code format to be fixed, such as standardized bytecode formats like the JVM, the CLR, Dalvik, and WebAssembly, where binary programs arrive metaphorically chiselled into stone, or flexible, where the format can be changed to suit the needs of a specific language or implementation. Clearly the larger design space of flexible formats affords more techniques, though key lessons hopefully improve the design of future fixed formats. For example, a key question of interest is whether a stack machine (such as the JVM or WebAssembly), or a register machine (such as the CLR or Dalvik bytecode), is inherently more efficient [58] [27]. Though it is too late to change the JVM, CLR, Dalvik, or Wasm, research here informs the next proposed format.
5.0.2 Interpreter dispatch techniques. As our own experimental results reaffirm, the dispatch sequence is critical to interpreter performance. If the format is flexible, e.g. if entirely in-memory, then threaded code [20] or more compact indirect threaded code [29] can be used. A large amount of work has aimed to improve the predictability of indirect branches [56] by exploiting the microarchitectural details of BTBs [25].

Superinstructions.
For flexible formats, the number of dispatches can be reduced with superinstructions [54], replacing small opcodes with larger, combined opcodes. This can be done online [31], offline, or a mixture of both. Super-instructions can be formed from combinations of simpler instructions, often in embedded Java VMs [70], or by defining language-specific high-level operations like in CPython and JavaScript VMs.

Radically different interpreter IRs.
Bytecode is not the only interpretable format. Abstract syntax trees or other intermediate representations can be interpreted directly in memory. Usually, speed is not the goal, though recently a fast AST-walking interpreter has been described for R [39]. Instead, interpreting IR has other benefits, e.g. proving the correctness of the interpreter, partial evaluation, and collapsing multiple levels of interpretation [18]. Truffle/Graal [64] uses ASTs, for example [47], as a way to express an interpreter for the Futamura [34] projection. Other graphbased IRs have been explored [62]. Some compilers have IR interpreters [2] for testing. A standard compilers course [50] includes interpreters for each IR during translation. None seem to compete with bytecode interpreters in speed. 5.0.5 Optimizing fixed format interpreters. A number of interpreter optimizations can still apply to fixed formats. The most common is duplicating the dispatch sequence at the end of every handler (referred to in this paper and elsewhere, if somewhat imprecisely, as a threaded interpreter or threaded dispatch), and is used in all the interpreters we tested. Threaded dispatch has even been applied to hosted interpreters on the JVM [57]. For stack machines, stack caching [51] [32] [49] VMs try to keep the top-of-stack cached in a register, reducing loads and stores to the value stack. It is possible to further duplicate [55] handlers to get more BTB entries [23]. Recent work has also proposed new hardware support for indirect speculation [69] [63] or to directly address BTB entries [41]. Many JVMs mutate bytecode in-place [22] to replace symbolic references with indexes and offsets.
5.0.6 Interpreter generators. Writing a highly efficient interpreter remains a black art. It is challenging, sometimes impossible, to convince compilers for high-level languages to emit perfect interpreter code. A number of interpreter generation frameworks have been proposed, including Tiger [24], VMGen [33], and a JavaScript VM generator [40], that automate much of the tedious bookkeeping and broadly apply best practices. 5.0.7 Interplay with JITs and debugging. If the virtual machine is allowed to generate new machine code, then the entire VM design space is unlocked. Context threaded code [67], where code is represented as a sequence of calls to handlers, can be used. From there, selective inlining [52] of handlers can be applied to improve performance. Discussion of JIT designs is beyond the scope of the paper, yet their interactions with interpreters is of note. Trace compilation [35] is fed by collecting execution traces from an interpreter. Meta-tracing [21], i.e. tracing through the handler implementation, has been employed by the PyPy dynamic optimizer. Dynamic adaptive optimization with deoptimization is now standard in many virtual machines. The design of interpreter stack frames determines the cost and complexity of on-stack replacement. In-place interpretation has been shown to ease debugging support, since no mapping need be maintained from rewriting.

CONCLUSION
In-place interpretation has long been considered when designing fixed code formats such as the JVM, CLR, and Dalvik, since it is the most memory-efficient. Wasm is unique in that it was explicitly designed with near-native performance as the highest priority and engines shipped with optimizing compiler tiers first. Interpretation was not thought necessary, and in-place interpretation, stymied by structured control flow, was dismissed as either impossible or at least unneeded. Yet in the intervening five years, startup time and memory consumption have increased in priority, and interpretation of Wasm (by rewriting to an internal format) has become more widespread.
This paper restores the missing execution tier for Wasm, regaining the key property of efficient in-place interpretation that was thought lost. We presented the design and implementation of the first fast in-place interpreter for Wasm that utilizes a compact sidetable easily generated as a side-effect of the code validation algorithm. We measured an order of magnitude improvement in memory consumption and processing time over rewriting Wasm. With this open problem now solved, we believe that Wasm engines in the future will employ new interpreter tiers for improved startup time, reduced memory consumption, and improved debugging support.

ACKNOWLEDGMENTS
Thanks to Paolo Severini at Microsoft for discussions on interpreter design and benchmarking considerations. Thanks to Hannes Payer and Toon Verwaest at Google for discussions on interpreters and V8. Thanks to Saam Barati, Keith Miller, and Fil Pizlo of the JavaScriptCore team for interpreter design discussions and tuning parameter hints. Thanks to Wasm Community Group members, specifically Andreas Rossberg, Luke Wagner, and Francis McCabe for discussions surrounding this work. Thanks to Lars T. Hansen at Mozilla for comments on a draft of this paper. Thanks to Tony Hosking and Steve Blackburn at ANU for shelter during (part of) the storm; truly Wizard is of Oz.