Emerging first for the Web in 2017 [Haas et al. 2017], WebAssembly is a portable, low-level compilation target supported in all major browsers. Originally designed as a successor to asm.js [Zakai 2013], which allowed C/C++ to be compiled to JavaScript, Wasm has supplanted other technologies such as Native Client [Yee et al. 2010] as the new best target for native compilation to the Web. Since that time, WebAssembly has seen rapid uptake in a number of new spaces, including cloud computing [Nurul-Hoque and Harras 2021], digital contracts, edge computing [Nieke et al. 2021][Fas 2020], IOT [Li et al. 2021], and embedded systems [Gurdeep Singh and Scholliers 2019].
A key design criteria for Wasm was offering performance competitive with native code. Initially, top-tier performance was considered paramount, and approaching native code performance to compete with technologies like Native Client was realized by reusing the optimizing JIT compiler infrastructure in browsers. Yet Wasm bytecode was also designed to be fast to parse, validate, and compileścriteria validated during the design process by building single-pass validators and single-pass decoding to SSA compiler IR to minimize upfront costs in the compilation pipeline.
However, despite minimizing bytecode parsing work by careful design, optimizing compilers inescapably take considerable time and memory to produce good native code, penalizing application startup in JIT scenarios. To address startup time problems, browsers prototyped separate, faster compilers during Wasm's design phase, validating that the same choices that enabled single-pass validation enabled single-pass compilation. Such often-termed łbaselinež compilers spend far less compilation time, often 10×-20× less, but produce code that typically runs 1.5× to 3× slower than an optimizing compiler. This represents a classic tradeoff space known to VMs for decades; more compilation time means better code quality. Today, all browser engines employ multiple Wasm compiler tiers to strive for both good startup time and high throughput.
1.1 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, startup is fast.
(3) Since bytecode is usually more compact than machine code, interpeters generally use less memory than compilers. (4) Since the interpreter loop can be stopped at any instruction and program state inspected, altered, and resumed, debugging application code is easier. (5) Since there is a fixed amount of code, interpreters are easier to audit and usually have fewer security vulnerabilities. (6) Since dynamic code generation is sometimes impossible, either because is not allowed on the platform, like iOS, or code space is limited, an interpreter might be the only choice. 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 criteriafoot_0 . But some Wasm engines do indeed employ interpreters, such as JavaScriptCore, Chakrafoot_1 , 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 is effectively a compilation step that takes time and memory, impacting startup and memory consumption contrary to the primary advantages of interpreters.
So far, there is an important point missing in the Wasm virtual machine design tradeoff space. An in-place interpreter operating on the original bytes of a binary module occupies a uniquely advantageous point in the tradeoff space. For cold or never executed code, where the interpreter's much slower execution speed is outweighed by avoiding translation time, it should offer the best startup time and lowest memory consumption. Employed in concert with compilation tiers for hot code, such an interpreter would serve the role it does in other mature systems like JVMs. Not to be overlooked is debugging; not needing a location mapping between the original code and the internal code is a major simplification. To date, we have found only two examples of in-place interpreters for Wasm: the testing interpreter in V8 and the łclassicž interpreter in the WebAssembly Micro-Runtime[ Wam 2021], referred to here as wamr-classic.
The testing interpreter in V8, implemented in C++, was originally intended to support debugging only. Never employed as a production tier, its performance is nearly 1000× slower than the other tiers, and it is now relegated to testingfoot_2 . That leaves only wamr-classic as the only production in-place interpreter. As we detail in 4.5.4, it employs a dynamic control stack with caching that can suffer pathological slowdowns as programs grow large. Aware of this vulnerability, the developers have deprecated this design in favor of a rewriting interpreter and a JIT compiler.
To date, the only high-performance interpreter designs for Wasm have employed rewriting or suffered from pathological cases. Is it possible to interpret Wasm in-place efficiently? In this work, we solve this open problem: the first fast in-place interpreter for Wasm without pathological behavior. As empirical measurements in Figure 1&2 show, our interpreter design occupies a new region in the tradeoff space of execution tiers for Wasm.
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 with execution time on-par with state-of-the-art rewriting interpreters. 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!
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.5.1) and other interpreters (4.5.2) for Wasm. Prior work related to optimizing interpreters is summarized in Section 5, followed by the conclusion.
Wasm provides a low-level execution model consistent with its original goal of a minimal, highperformance abstraction over hardware. Its principal features include: 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.
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.
Functions. All code 4 in Wasm is organized into functions. Functions each have a signature with a fixed number of parameter and result types, such as
A Fast In-Place Interpreter for WebAssembly 148:5 execution stackfoot_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 structuresfoot_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 stackfoot_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.
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 validation 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 validation 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 typesfoot_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.
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 Fast In-Place Interpreter for WebAssembly 148:7
• 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 languagefoot_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.
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, vals, pop ⟩, 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
• vals the number of values that will be copied if the branch is taken
• pop 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 exactly as intended, as a jump table, computing an index into the side-table and using the corresponding entry in 𝑂 (1) time.
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.
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 objectfoot_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 [Diwan et al. 1992]. 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 fatfoot_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 [Demers et al. 1989].
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. An overflow should not crash the engine uncontrollably either, but be handled gracefully like other Wasm traps. 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 pagefoot_11 will cause a fault if the native execution stack overflows before the value stack.
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 13• FUNCTION a reference to the current function • INSTANCE a reference to the current instance • DISPATCH for dynamically enabling per-instruction probing
We chose to implement our interpreter in a new Wasm research engine, wizard [Titzer 2021]. While most of the engine is written in a portable, safe, high-level language [Titzer 2013], 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 [Hot 1998] using a macro assembler (at startup), V8's Ignition [ Ign 2022] 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 consumingfoot_13 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 [Bell 1973], indirect-threaded [Dewar 1975], and other dispatch techniques can be used, 4) handlers can be ordered and aligned for optimal I-cache behavior, 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.
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 start with a 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 integer. Like nearly all integers in the Wasm binary format, this is a LEB128 [ LEB 2022] encoding that uses the uppermost bit of each byte to indicate if 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 [Shi et al. 2005] 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 languagefoot_14 , but easy in assembly. This saves a jump instruction and typically makes better use of the CPU's indirect branch predictor.
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 [Titzer and Palsberg 2005] 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 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.
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. There are enough left-over registers to implement all bytecode handlers without spilling. Registers are only spilled when the interpreter performs a Wasm call or calls into the engine runtime. Our implementation against the macro assembler uses symbolic registers throughout, allowing the mapping to change easily. 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, where the dispatch sequence is duplicated at the end of every handler to be on average 14%, maximum 29% faster. • Hardware checking of memory bounds. Like most Wasm implementations on 64-bit machines, our engine uses virtual memory protection to catch out-of-bounds memory accesses by the program, reserving 8GiB of address space for a memory and protecting the out-ofbounds address ranges. We did not evaluate the cost of explicit memory bounds checks, but anecdotal data from other engines suggests this is on the order of 20-30%, even in JITed code.
It may be proportionately less for an interpreter. • Value tagging. Our interpreter design uses value tags to find GC roots when necessary. To evaluate the performance cost, we measure with and without tags and found that tags reduce performance of the interpreter on average 8%, maximum 15%. We did not pursue design alternatives that would require computing a reference stack map (as done in JITs), as the space cost negates the primary advantage of the in-place interpreter design. • Really fat values. SIMD values are 128 bits (16 bytes) wide. When coupled with value tagging, values occupy 32 bytes of memory each in the value stack. Uniform size for values in the value stack (Figure 5) is effectively required because, unlike the JVM, Wasm bytecode doesn't use multiple łslotsž for wider values; the numbering and operations like drop treat each value as a single slot. While our experimental engine fully supports the v128 type in its type system and validation, we did not yet implement the 236 Wasm SIMD instructions in the assembly interpreter, thus we did not measure their performance. • 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. Moving the multi-byte case out-of-line (leaving the inline 1-byte case as three instructionsśłload, test upper bit, branch out-of-linež) improves performance as much as 5%. • Memory #0 base pointer. Wasm programs access memory very frequently. As described earlier, our implementation caches a pointer to the base of Wasm memory #0 in an architectural register. This saves one or two loads for every memory access (łload memory tables from instance, load memory startž), depending if the base for memory #0 is directly in the instance, rather than in an array of memory bases. 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 and concluded that 8 byte alignment was consistently fastest, but not by much (0-5%); variance is high and very application-dependent. • Handler order. We suspect that handler code order may introduce significant additional microarchitectural effects [Mytkowicz et al. 2009] [Curtsinger andBerger 2013]. However, we did not heavily optimize the handler order beyond simply emitting common bytecode handlers first, clustering them near the beginning of the interpreter code. • 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 code space. Since traps usually terminate the program, the performance does not matter. • Call/entry/exit sharing. We exploit commonalities among the call, call_indirect and tail callfoot_15 bytecodes, return/fall-through, and 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 but suspect the performance effect is neglible.
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.
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.
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. In addition to the rapid evolution of Web engines, a number of non-Web Wasm engines have appeared.
• wasmtime [Was 2021b] -A standalone runtime implemented in Rust.
One compiler tier. The optimizing Cranelift compiler can be used in JIT or AOT modes. 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, this paper focuses on interpreter design, which is a crucial point in the tradeoff space of execution tiers. There we include several experiments that compare engines with multiple tiers to understand their current tradeoffs. We chose to measure these engine/tiering configurations:
• wizard-Our engine with its in-place interpreter that uses a sidetable.
• wamr-classic -The WAMR engine with its łclassicž in-place interpreter.
• wamr-fast -The WAMR engine with its (now default) rewriting interpreter.
• wasm3 -Default configuration of a rewriting interpreter.
• v8-liftoff -V8 with only the Liftoff baseline JIT.
• v8-turbofan -V8 with only the TurboFan optimizing JIT.
• sm-base -Spidermonkey with only the baseline compiler.
• sm-opt -Spidermonkey with only the optimizing compiler.
• jsc-int -JSC with JITs disabled, i.e. only the rewriting interpreter.
• jsc-bbq -JSC with the rewriting interpreter and BBQ quick JIT only.
• jsc-omg -JSC with the rewriting interpreter and OMG optimizing JIT only.
Evaluation methodology. 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.2.1 suite, with the MEDIUM dataset. As included in the artifact accompanying this paper, all engines were cloned from source on roughly 2022-07-10. That implies V8 version 10.5.0, JSC version 614.1.20, and Spidermonkey version C104.0a1. All engines were built as "release" from source. Data was collected in two experiments; 100 uninstrumented runs of 10 engine configurations on the 24 benchmarks to gather execution time, and 100 instrumented runs of the same to collect translation time and space statistics. Every run represents a separate OS process. Execution times are of the complete process (i.e. not internally timed), while translation times are the sum over all Wasm functions translated in the run. All timing results are the averagefoot_17 over the 100 runs, and when error bars are shown, they represent the 5 th and 95 th percentiles of the distribution.
All of our chosen execution tiers apply some form of translation to the input bytecode, except wizard and wamr-classic (the only other in-place interpreter of which we are aware). 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 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. lazy 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-flowfoot_18 , 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. 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. 4.5.2 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 Figure 12 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 performance advantage to wasm3's threaded code dispatch technique (where the IR is simply a list of function pointers with immediates), its several bytecode-level optimizations, and its register machine design which also incorporates global constants. In the first 4 (shortest running) benchmarks on the left, we see the amortization effect of wizard's lower translation cost; it is faster than jsc-int and wamr-classic and nearly on par with wamr-fast. Moving to the right, difference in translation time becomes amortized, and interpreter speed starts to dominate, though the difference is not nearly as dramatic as the comparison of JITs, and levels off quickly. We see that our design performs better than the other in-place interpreter, wasm-classic in most situations, and generally on-par with jsc-int. 4.5.3 Multi-tier configurations in context. 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.1. We ran additional experiments for engines in their default configuration, but we found that the default configurations do not always yield the best performance results. The design space for tiering strategies is vast, with many variables, such as laziness, concurrency, thresholds for tiering up, on-disk caching, etc. So far, our measured results are complex enough to merit a more detailed study in their own right, which is unfortunately beyond the scope of this paper. Thus, for now, we cannot characterize the performance of Wasm interpreters in complex multi-tier configurations. 4.5.4 Avoiding pathological behavior. The only other production Wasm interpreter to use an inplace design is wamr-classic. 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 wamr-classic in its fastest configuration, as 2× would have put it handily out of the running.
The wamr-classic design 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. Thus the rescan overhead is bounded only by the function size, and the miss rate is determined by the program's temporal and spatial locality of branch instructions, regardless of their outcome (taken/not taken). 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 a large function consisting of a few thousand branches with poor locality and observed slowdowns of as much as 8×. It could be even worse on larger programs with millions of instructions that have hundreds of thousands of branches. This vulnerability was known to its authors and is one of the motivations for wamr to now ship the faster rewriting interpreter (wamr-fast) by default.
Given the potential pathological behavior of wamr-classic, we believe wizard represents the first viable fast in-place design.
Interpreters are as old as the hills. From the first popular interpreted language, Lisp [McCarthy 1960] 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 [Barany 2014] [Zhang et al. 2022]. Because of their advantages, new interpreters continue to appear, even for languages previously compiled [Hu et al. 2021].
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 [Shi et al. 2005] [Davis et al. 2003].
Interestingly, though it was not a research question at the outset of this work, our experimental results lend some credence to the conclusion that interpreters for register-based VMs are faster than stack-based ones, since the rewriting interpreters that are faster than wizard are both register machines. Though it is too late to change the JVM, CLR, Dalvik, or Wasm, research here informs the next proposed format. Yet note also that the side-table strategy employed here can also inform the next proposed format, as a bytecode not designed for fast interpretation can be augmented with additional metadata to improve interpretation speed.
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 [Bell 1973] or more compact indirect threaded code [Dewar 1975] can be used. A large amount of work has aimed to improve the predictability of indirect branches [Rohou et al. 2015] by exploiting the microarchitectural details of branch target buffers (BTBs) [Chang et al. 1997]. Some of the latter techniques may also be applicable to wizard's interpreter design.
Superinstructions. For flexible formats, the number of dispatches can be reduced with superinstructions [Proebsting 1995], replacing small opcodes with larger, combined opcodes. This can be done online [Ertl and Gregg 2004a], offline, or a mixture of both. Super-instructions can be formed from combinations of simpler instructions, often in embedded Java VMs [Zilli et al. 2015b], or by defining language-specific high-level operations like in CPython and JavaScript VMs. Superinstructions might not necessarily apply to a fixed format, but given that many Wasm instructions are a single byte, an intriguing possibility might be to dispatch on two bytes at a time, using a table of 64K entries that has some superinstruction entries for common patterns. At the least, the superinstruction could eliminate the need to check for multi-byte LEBs, e.g. in local.get/set, two very frequent Wasm instructions.
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 [Kalibera et al. 2014]. Instead, interpreting IR has other benefits, e.g. proving the correctness of the interpreter, partial evaluation, and collapsing multiple levels of interpretation [Amin and Rompf 2017]. Truffle/Graal [Würthinger et al. 2012] uses ASTs, for example [Niephaus et al. 2018], as a way to express an interpreter for the Futamura [Futamura 1983] projection. Other graph-based IRs have been explored [Williams et al. 2010]. Some compilers have IR interpreters [Lli 2015] for testing. A standard compilers course [Palsberg 2014] includes interpreters for each IR during translation. None seem to compete with bytecode interpreters in speed.
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 [Savrun-Yeniçeri et al. 2014]. For stack machines, stack caching [Peng et al. 2004] [Ertl and Gregg 2004b] [Ogata et al. 2002] 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 [Prokopski and Verbrugge 2008] handlers to get more BTB entries [Casey et al. 2007]. Recent work has also proposed new hardware support for indirect speculation [Zilli et al. 2015a] [Williams et al. 2008] or to directly address BTB entries [Kim et al. 2016]. Many JVMs mutate bytecode in-place [Brunthaler 2010] to replace symbolic references with indexes and offsets.
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 [Casey et al. 2005], VMGen [Ertl et al. 2002], and a JavaScript VM generator [Kataoka et al. 2018], that automate much of the tedious bookkeeping and broadly apply best practices.
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 [Zaleski et al. 2005], where code is represented as a sequence of calls to handlers, can be used. From there, selective inlining [Piumarta and Riccardi 1998] 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 [Gal et al. 2009] is fed by collecting execution traces from an interpreter. Metatracing [Bolz et al. 2009], 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.
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.
The experiments in this paper were conducted on open-source software which has been packaged and made available as an accompanying artifact accessible on GitHub [Titzer 2022a] and on Zenodo [Titzer 2022b].
In fact, in a smoky back room, I probably declared, łInterpreters don't matter here. ž
Though discontinued, ChakraCore was the first Wasm engine to feature a rewriting interpreter.
Today, V8 supports debugging of Wasm code in Liftoff, its baseline compiler tier. Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
Note that the execution stack is not aliased by Wasm memory, thus not vulnerable to stack smashing
Provably minimal, if a CFG is restructured from the known algorithm for optimal interval analysis, ensuring the validation metadata per control flow construct is discarded and reused as promptly as possible.
Other stack machine designs, like JVM bytecode, allow values on the operand stack while branching, but stack heights and contents must match. Thus JVM branches cannot implicitly pop values. Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
In Wasm, all control constructs can have data parameters and results, represented as a block signature. Thus a block can be seen as a super-instruction; it pops values off the stack, and every path to its end pushes the same number and type of results. This allows for very compact code, often obviating local variables. In practice, most blocks have an empty block signature.Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
More precisely, a macro assembler API in a high-level language that has methods to generate individual instructions, allowing it to be configurable in ways that typical textual assembly languages are not.Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
Boxing is a major overhead in dynamic language implementations and would be prohibitively expensive for Wasm, outweighing all optimizations described in this paper.
Aligning value stack entries on a power-of-two boundary allows for shift-based arithmetic when indexing.
Using sigaltstack on POSIX platforms for signal handling. Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
Though not shown, Wasm memories also have a guard region, obviating the need for an explicit bounds check.
This deserves some careful consideration. As Wasm is a standardized wire format that is likely to change only by extension, the interpreter is subject to less change pressure, except to adapt to internal changes in engine organization (e.g. layout of internal data structures). We feel its warranted to hand-optimize assembly in this limited case. Further, much work on the interpreter can be reused in a baseline compiler, as the code sequences emitted by a single pass compiler are nearly identical to interpreter bytecode handlers.Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
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ž [Gcc 2022] 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 [Ign 2022]), 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.Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
wizard implements a few Wasm extension proposals such tail-call. Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
It is; we confirm their measurements in our experiments.
Arithmetic mean, including all measurements. We report the average to include the effect of outliers, while reporting the 95% confidence interval to characterize the distribution.Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October 2022.
Note that here, we measure wizard sidetable entries compressed to 2 bytes where possible, though this is not the default.Proc. ACM Program. Lang., Vol. 6, No. OOPSLA2, Article 148. Publication date: October