Hacker News Reader

Comment by mananaysiempre | Hacker News Reader

> we might conclude that the speed-up of a manual assembler implementation compared to a generated interpreter is about 30%[, t]herefore it's no longer worth the effort to implement an interpreter in assembler

You got that backwards. The paper reports Deegen’s generated interpreter is faster than LuaJIT’s handwritten one by 30%. That’s actually pretty impressive—and pretty impressively straightforwardly achieved[1], TL;DR: instruction dispatch via tail calls avoids the pessimized register allocation that you get for a huge monolithic interpreter loop.

[1] https://sillycross.github.io/2022/11/22/2022-11-22/

View on HN

    # decode next bytecode opcode
    movzwl      8(%r12), %eax
    # advance bytecode pointer to next bytecode
    addq        $8, %r12
    # load the interpreter function for next bytecode
    movq        __deegen_interpreter_dispatch_table(,%rax,8), %rax
    # dispatch to next bytecode
    jmpq        *%rax

You may reduce that even further by pre-decoding the bytecode: you replace a bytecode by the address of the its implementation and then do (with GCC extended goto)

  goto *program_bytecodes[counter]

I've been playing around with this and its worth noting that pre-decoding the bytecode because it means every instruction (without operands) is the width of a pointer (8 bytes on x86) which means you fit far fewer instructions into cache, eg my opcodes are a byte, so that's 8x more instructions. I haven't had time to compare it in benchmarks to see what the real world difference is, but its worth keeping in mind.

Somewhat off topic, looking at that assembly... mine compiles to (for one of the opcodes):

    movzx  eax,BYTE PTR [rdi]
    lea    r9,[rip+0x1d6fd]        # 2ae30 <instructions_table>
    mov    rax,QWORD PTR [r9+rax*8]
    inc    rdi
    jmp    rax

(also compiled from C++ with clang's musttail annotation)

I have wondered whether it's worth storing instruction offsets (from the first instruction) rather than raw instruction pointers to increase cache efficiency, then they could be encoded in just 2 (or at worst 3) bytes. At the cost of an extra register.

That sounds like a good middle ground. Ahh I wish I had some more time, I’d love to benchmark all three and see how they compare.

In my own you VM, I do actually have a spare general purpose registers available for use. Now I just need to find the time to try it out…

They still have register allocation issues:

> Register shuffling to fulfill C calling convention when making a runtime call.

Not sure how common is that in their benchmarks because it's tempting to handle everything frequently used as bytecode.

> Deegen’s generated interpreter is faster than LuaJIT’s handwritten one by 30%

That's exactly what I've written. But apparently I got that wrong with their baseline JIT.

> That's exactly what I've written.

In that case I don’t get the logic. “It’s no longer worth the effort to handcode an interpreter because that’d only be 30% faster” is a sentiment I could understand. “It’s no longer worth the effort to handcode an interpreter because that’d be 30% slower” I can’t. It’s that it’d be worth or not worth the effort—it’s that it’s actively detrimental! (For this particular application anyway.)

> Also note that the Deegen "interpreter" uses a "baseline JIT".

What? No it doesn’t? Unless the paper is deliberately misleading, they are completely different modules (utilizing the same set of bytecode definitions). The paper explicitly describes them as implementing the first two tiers of a three-tier architecture—two different tiers. Not once does the description of the interpreter in section 6 mention JITting anything. Figures 26–27 show e.g. array3d on “LJR (interpreter only)” is at 3× PUC Lua speed (same as “LuaJIT (interpreter only)”), while on “LJR (baseline JIT)” it’s at 7× PUC Lua speed (compared to 30× on “LuaJIT”).

English is not my native language; I probably should have written "that the speed-up *from* a manual assembler implementation compared to a generated interpreter is about 30%"; the point is that the speedup is small but at least demonstrates that assembler programming apparently isn't worth it any longer.

> Unless the paper is deliberately misleading,

Apparently I misinterpreted their paper concerning the JIT; as pointed out by others they indeed run separate measurements with baseline JIT on and off; so apparently it was off for the measurement I referred to. All in all it confirms that even for the JIT case assembler programming isn't worth it.

Reply on news.ycombinator.com