When pigs fly: optimising bytecode interpreters

If a CPU ran on its own, then there's no end to our optimization potential. If it were a strict Harvard architecture where instructions could only run in immutable (ROM) areas, we could translate the instructions, remove all unnecessary flag calculations, and then statically recompile the result to a native program.

But when the CPU needs to talk to the audio chip, the video chip, the other audio CPU running alongside it, etc ... the reason everything ends up so slow is that there's no viable path for speeding up that synchronization.

You try and do it with real hardware resources: a real CPU core/thread for each emulated chip, and performance falls off a cliff. Even with simple atomic reads/writes for one thread/chip to set a "waiting on you" flag, and another thread/chip to clear it, modern CPUs can only do this around 100,000 times a second ... and that's before the overhead of your emulation. So, if you want to emulate two CPUs that run at more than 0.1 MIPS (which even the NES surpasses), you're out of luck.

So you try and do it with a single thread, but you get destroyed through context switches. You're in the middle of executing a 68K instruction, but that instruction writes to RAM that the Z80 can read from. You don't know if the Z80 is going to read there, so you have to run the Z80 until it's "ahead" in time to the 68K. Switching into the Z80 interpreter absolutely murders your performance.

Pretty much the primary key to optimizing CPU emulators is to synchronize less often. Making assumptions like, "it's very unlikely the Z80 is going to write to the CPU instruction stream in the middle of it executing instructions ... the 68K is most likely executing code in ROM anyway" and not synchronizing the Z80 when the 68K fetches an opcode or operand byte.

But these optimizations always come at a cost. When you get a library of thousands of programs designed to eke out every last drop of performance from old, legacy 2MHz hardware, there's always that one program ... either by design or by fluke, does something crazy and relies on something you optimized away as extremely improbable, and breaks as a result.

In my view, the way to optimize real-world emulation of machines is that we need to be able to spawn lots of 1 core = 1 thread objects, and have their synchronizations be as cheap as humanly possible. The cores do not have to be lightning fast, they just have to be able to synchronize as quickly and as cheaply as real code running on a 90s era 68K+Z80 machine (eg a Sega Genesis) is able to. Many, many bonus points if the "waiting on another chip" operation can result in sapping less power for that thread, without increasing the latency necessary for it to resume operating once the condition is met.

The industry has, for decades, been moving in the complete opposite direction, so I don't have a lot of hope. At this point, I think it's more viable (but still very unlikely) to put FPGAs into home computers for this purpose.

In fact, I took one of the techniques (traces) directly from a paper describing how the Bochs x86 virtual machine works :-)

But it goes deeper than that. I believe the whole "trace" thing in both jits and vms comes from a few papers describing trace-based instruction predecoding for hardware CPUs.

The big problem was that Apple was lousy at specifying how much cache they needed. IBM told Apple that it needed a LOT more cache on the 603 unless everything was running native. Apple ignored the advice.

The result was that the 603 and 604 were performance dogs because so much was still running in emulation.

So, IBM went back and bumped the cache for the 603e, and performance went up dramatically. This then led to the unfortunate situation wherein the "low-power" chip from IBM (the 603e) tended to be far more performant than the "high-performance" chip (the 604) from Motorola.

The microinstruction is 23 bits wide (plus one for parity). Rather than doing a lot of masking, shifting, and testing to extract fields (some fields are non-contiguous even), I instead use 64b per microword.

bits [23:0] -- original microinstruction bits [31:24] -- 8b op-dependent predecode value bits [39:32] -- 8b interpreter dispatch index bits [47:40] -- 8b op-dependent predecode value bits [63:48] -- 16b op-dependent predecode value

There are a few oddball instructions which could use more than the 8b and 16b predecode fields, and instead do the old shift and mask on the raw microword to figure out what is needed.

Overall, it nearly doubled my performance.

with an even lovelier title.

This sentence is more like a description of the current state of affairs: people go for very complicated jits instead of trying to push the basic interpreter to its limits.

And jits are complicated, and are very hard to get right.

    cpython vs pypy
    lua vs luajit
    dalvik vs art (which isn't jit)
    zend vs hhvm

My gut feeling, though is that is because of the inefficiencies in php, many inherent in the language design, rather than because php7 were the only people to know how to write a fast interpreter.

It seems a sound generalisation that you get another order of magnitude by moving from interpretation to compilation.

I was also surprised to see the switch-based solution winning here. But I was even more surprised to see how a simple change (a primitive stack top caching) suggested by one of the readers radically changed my perf benchmarks: the threaded interpreter was the fastest interpreter again.