David Mandelin’s blog

If you’re reading this, chances are that you already know about SquirrelFish, Appl/WebKit’s new Javascript implementation. Early tests show SquirrelFish to be 60% faster than WebKit 3.1 JS, 46% faster than Spidermonkey and 52% faster than TT (Tamarin Tracing) on SunSpider.

Clearly we have some work to do. The plan is to improve TT so that hot loops run highly optimized native code; TT’s optimizer is in the early stages, and we think there’s a lot of room for further optimization. For example, as explained in my previous posts, when TT jumps from one trace to another, it has to save the interpreter state to a standard format and then reload the state on the new trace, and no cross-trace optimization is possible. Ideas like trace folding have potential for a big improvement here.

But I still wanted to take a quick peek into why SquirrelFish’s interpreter is so fast. The announcement touts 3 key design features:

• Using a bytecode interpreter.
• Using direct-threaded interpreter dispatch.
• Using a register-based bytecode interpreter.

Bytecode interpreter. The old WebKit JS was based on an AST walk, which is explained in some detail in the announcement. It’s well-known that bytecode interpreters are faster, so it’s no surprise Apple made this change. Spidermonkey and TT’s interpreter have always been bytecode interpreters.

Direct-threaded dispatch. Interpreters tend to spend a lot of time dispatching bytecode operations. Direct-threaded dispatch is a technique for efficient dispatch.

The obvious way to write a bytecode interpreter is with a switch statement inside a loop:

void run(Bytecode *ip) {
for (;;) {
switch (*ip++) {
case OP_ADD: …
case OP_JUMP: …

Each iteration runs one bytecode instruction. Each case of the switch handles one instruction type. It really doesn’t look like there’s any room for improvement here unless you look at the assembly code generated for the switch dispatch (from a tiny test interpreter I wrote today, comments added by me):

# ip is in %edx
# Check that switch expression (%edx) is in table range
cmpl    $9, (%edx)
leal    4(%edx), %ecx
ja    L26
# Look up case address offset for (%edx) in table (L37)
movl    (%edx), %eax
movl    L37-”L00000000006$pb”(%ebx,%eax,4), %eax
# Add base address to offset
addl    %ebx, %eax
# Indirect jump to computed address
jmp    *%eax

The basic idea is to keep a table of relative offsets to the cases, and then jump using that offset. Because the switch expression could evaluate to anything, the compiler must first generate a range check, so that if the switch expression doesn’t map to any case, the program leaves the switch instead of crashing unpredictably.

But in reality the range check is useless, because the interpreter can control what bytecodes actually appear, so this is 3 wasted instructions. Also, the lookup and base+offset address computation seems kind of clunky. I’d prefer dispatch code something like this:

jmp    *%edx

This is direct threading. In principle, the idea is simple: the instruction code (e.g., OP_ADD) is the address of the case target code. (In the basic design, instruction codes are integers.) Then, this jump is all you need for dispatch.

Coding up direct threading is weird; normal C compilers don’t know how to do it. But it can be done with GCC’s computed goto extension (see the paper on direct threading from the SquirrelFish announcement). See also my tiny interpreter.

I believe TT and Spidermonkey use an intermediate design called indirect threading, which gets most of the speedup of direct threading, but allows integer opcodes. The opcode is an index into a table of case target addresses. So the dispatch code has to look up the case target, then jump, something like:

leal   TABLE(%edx,4), %eax
jmp   *%eax

Not too bad. I have no idea how significant the difference between direct and indirect threading is in practice, but even a few percent speedup would be great.

Register-based interpreter. “Traditional” interpreter design keeps all operands and intermediate values of expressions on a data stack. (This is completely different from the call stack.) I can think of a few design reasons why this might be, but I really don’t know why it’s been done this way. Anyway, with a stack, bytecode for a line of code like “x = a + b + c” looks like this:

LOAD a  # push a onto stack
LOAD b
ADD      # pop 2 elements, add them, push the result
LOAD c
ADD
STORE x

One nice thing about this is that the algorithm for generating this bytecode is very simple, so it’s not a lot of work to code and runs fast. But there’s a lot of code just to manipulate the stack here, and it might be nice to avoid it. (Real stack-based programs have even more stack manipulation, with DUP, SWAP, ROT, etc. operations.)

A register-based design avoids the stack by using a fixed array of “slots” or “registers” for operands. (These registers are completely different from assembly code registers.) The register-based version of the above line of code would be something like:

ADD temp, a, b   # temp = a + b
ADD x, temp, c

Keep in mind that in the register-based bytecode, where I have “x” it would actually have something like “0″, if x had been assigned slot 0 in the register table. Note also that the bytecode generator has to analyze the code a bit to decide how many registers are needed and assign them to the variables and temporaries.

Each design has advantages and disadvantages:

• Bytecode code size. Stack-based bytecode programs tend to be smaller, because the operands are implicit. But the register-based program gets to omit the stack manipulation instructions, so the stack-based bytecode should be only a little bit smaller. The memory savings shouldn’t matter in most environments, but reading less bytecode will save the interpreter a bit of time.
• Bytecode instruction count. As shown above, a register-based program will have fewer bytecodes. Fewer bytecodes to execute means faster run times, if it takes the same length of time to execute a bytecode in each design. Which it doesn’t:
• Operand access. To access operands, the stack-based interpreter just reads and writes from the top of the stack or very near it. A register-based interpreter needs a two-step process: first it has to get the address of that register, then read or write it. But the register-based version doesn’t need to adjust the stack. Still, it seems like more work per instruction for the register version: for ADD, the register version needs to compute 3 operand addresses, while the stack version just one (the new stack pointer).

Overall, when you look across instructions, I think the total amount of operand addressing computation is about the same. The stack version distributes it across more instructions. The stack version might be able to save a few by having special instructions like LOAD0 (to load slot 0, needing no computation). But the register version still has few instructions, so fewer dispatches. With direct threading, the dispatch is fairly efficient, so this is less important, but an indirect jump is still usually pretty expensive compared to a normal instruction because of the high branch mispredict probability.

Microbenchmarking. I wrote a tiny interpreter that runs a bytecode program for an empty for loop using doubles as numbers (as in JS) to test out these things for myself. I tried 4 design choices: direct threading vs. switch and stack vs. register. The times for 10M iterations in milliseconds:

Here you see huge differences. The reason the differences are so big (far bigger than WebKit got) is that my tiny interpreter’s opcodes are very simple. In a real JS interpreter, the code to run for the average operation is a lot longer, so dispatch overhead is a much smaller fraction of total time, and dispatch overhead is the main thing saved by direct-threading and registers.

Note that the speedup of register vs. stack is smaller in the direct-threaded case, as I predicted above. But not that much smaller, because the dispatch really is expensive compared to everything else in this simple interpreter.

You can get my microbenchmark code here.