2 ms·
> Machine code is very dense. It's intriguingly dense. If you're writing an emulator or a bytecode VM, and you can't just slap a JIT in (because you need to en
by derefr 7y ago
> Machine code is very dense.
It's intriguingly dense. If you're writing an emulator or a bytecode VM, and you can't just slap a JIT in (because you need to ensure that e.g. data races resolve the same way they did on the original machine), it's very hard to come up with a data structure to represent "decoded" code, that is more performant than just keeping the original code around in memory in its packed-stream-of-opcodes form.
One would think, for example, that it would make sense to do the "instruction decode" pass ahead of time, to end up with an array of pointers-to-instructions plus literal-values... but the resulting representation of the code is usually much larger in memory, and so less of it will fit in cache (and it'll also fight the VM interpreter itself for cache-lines.) You might gain from your instruction impls not having to trampoline back to the interpreter (https://en.wikipedia.org/wiki/Threaded_code https://en.wikipedia.org/wiki/Threaded_code, basically), but you'll lose in cache coherence.
Really, the best you can do in such a situation is to translate the stream of opcodes to another stream of opcodes, just ones that you can execute more efficiently (i.e. create your own "microcode" ISA for your VM.)
Either way, "a loop that walks/jumps through an in-memory buffer of variable-length CISC opcodes using a byte-granular program-counter pointer register" seems to be an optimum somehow in design space.
- earlz 7y ago> One would think, for example, that it would make sense to do the "instruction decode" pass ahead of time, to end up with an array of pointers-to-instructions plus literal-values... but the resulting representation of the code is usually much larger in memory, and so less of it will fit in cache (and it'll also fight the VM interpreter itself for cache-lines.) You might gain from your instruction impls not having to trampoline back to the interpreter (https://en.wikipedia.org/wiki/Threaded_code https://en.wikipedia.org/wiki/Threaded_code, basically), but you'll lose in cache coherence. As someone currently writing a (subset of an) x86 VM, I feel this pain entirely too much. My subset greatly simplifies things by not using segment registers and getting to (mostly) not have to implement the 16bit version of ModR/M. The biggest problem with x86 is the sheer number of ways to do addressing within a single opcode using a Mod R/M operand. For instance, all of these lines of assembly can use the same primary opcode: push eax push [eax] push [1000] push [1000 + eax] push [0x11 + (eax * 2 + ecx)] push [0x11223344 + (eax * 8 + ecx)] push [(eax * 8 + ecx) - 10] If not for the Mod R/M and SIB operands, x86 would be a static-width instruction set I'm building an interpreter that goes the way of decoding to build a pipeline (really a "basic block") and then to execute the entire pipeline with minimal branching across execution. I'm less afraid of excessive cache use than the unpredictable indirect branch problem. The hope is that building a pipeline and executing it with a branchless unrolled loop will allow me to avoid that problem, while also greatly simplifying the implementation of each opcode where the actual logic just receives a set of operands it can get or set.
- Narishma 7y ago> but you'll lose in cache coherence. Did you mean cache locality?