Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Write Your Own Virtual Machine

justinmeiners.github.io

Post reply on HN
Print view View original

71–79 of 79 posts

Re: Write Your Own Virtual Machine

#71

Post by wahern »

vardump wrote: post #11
chrisaycock wrote: post #2

One of my favorite techniques for implementing VMs is the "computed goto": https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Consider this example for dispatching instructions from the article: while (running) { uint16_t op = mem_read(reg[R_PC]++) >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; ... } } That code has a…

> That code has a lot of branching. The switch statement has to jump to the corresponding case, the break statement branches to the bottom, and then there is third branch to get back to the top of the while loop. Three branches just to hit one instruction. That's a bit unfair. Not all branches are equal. Only the instruction fetch branch is going to be often mispredicted. Predicted branches, like that while loop, are…

> Predicted branches, like that while loop, aren't that expensive.

The dispatch loop conditional used to be quite expensive. Since Haswell it has become much less expensive, such that it wasn't even worth threading dispatch. But now with Spectre mitigations that cost may rise again.

Also, it depends on how tight the VM loop is. The prediction buffers are only so big, so if your ops are doing alot of work you can end up back with pre-Haswell performance.

Re: Write Your Own Virtual Machine

#73

Post by wahern »

chc4 wrote: post #4
sgillen wrote: post #3

Earlier quoted context omitted.

Do you know if an optimizing compiler will ever make this transformation?

Every single C compiler worth mentioning will turn a switch statement into a jump table. The difference between a jump table and computed goto is only that one is `jmp [ecx+eax 8]` and the other is `mov edx, [ecx+eax 8]; jmp edx`. The later is faster because of weird branch prediction reasons, and no bounds checks in the switch.

> Every single C compiler worth mentioning will turn a switch statement into a jump table

Only if the case values are small integers with a compact range. But if your opcodes are large and/or sparse (more common in non-VM scenarios) compilers don't optimize switch statements very well.

There's a ton of research on switch statement optimization, but most of it doesn't translate to real-world scenarios very well. Compilers will give up fairly quickly on trying to generate a jump table because the work necessary to map the case value to an index at runtime can easily cost more than its worth in many situations.

Here's some real-world code which you can easily benchmark and compare: https://github.com/wahern/hexdump/blob/master/hexdump.c#L752

Just flip the VM_FASTER macro. Using `hexdump -C /dev/null`, on my circa 2012 Mac Mini the switch statement is 80% slower than the computed goto and on my circa 2018 Macbook Pro it's about 15% slower. (See my note elsethread about the post-Haswell branch prediction.) And this is despite the fact that the opcode range is 0-32 without holes!

Also, with computed gotos you can remove the jump table altogether. You can make your opcodes actual addresses (just like native code) if you can make the label addresses visible to the code generator. (See my post elsethread for how to make them visible.)

P.S. While I implemented hexdump.c using a VM mostly for fun, the end result not only out performs GNU od and BSD hexdump, but IMHO the code is much easier to read, too.

Re: Write Your Own Virtual Machine

#74

Post by tom_mellior »

astrobe_ wrote: post #50
banachtarski wrote: post #5

Earlier quoted context omitted.

Oh psh optimizing compilers go way beyond this. In fact, even hand implemented VMs also generally go further. The technique above is called tail dispatch and is really just the beginning.

As far as I am concerned, I stopped worrying and use direct threaded code (DTC): a VM instruction is just a pointer to the C function implementing it. It's reasonably portable and one can expect stable performance across platforms. Because, when you look at the benchmarks you find out that you are talking about single-digit percent difference between different techniques sometimes, and variations in cache size, branc…

> direct threaded code (DTC): a VM instruction is just a pointer to the C function implementing it.

Nitpick: This sounds more like subroutine threading than direct threading. https://en.wikipedia.org/wiki/Threaded_code

In subroutine threaded code, each function implementing an instruction returns before the next one is called. In direct threading, each code snippet implementing an instruction loads the next address and jumps to it directly without going through a return and another call.

Re: Write Your Own Virtual Machine

#75

Post by tom_mellior »

emilfihlman wrote: post #57
chrisaycock wrote: post #2

One of my favorite techniques for implementing VMs is the "computed goto": https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Consider this example for dispatching instructions from the article: while (running) { uint16_t op = mem_read(reg[R_PC]++) >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; ... } } That code has a…

Is that {THING, VALUE} pseudocode or is it valid C somehow?

The featured article is written in a "literate programming" style. Those {ADD, 6} markers refer to snippets of code defined elsewhere to be inserted in place of the marker.

Re: Write Your Own Virtual Machine

#76

Post by astrobe_ »

tom_mellior wrote: post #74
astrobe_ wrote: post #50

Earlier quoted context omitted.

As far as I am concerned, I stopped worrying and use direct threaded code (DTC): a VM instruction is just a pointer to the C function implementing it. It's reasonably portable and one can expect stable performance across platforms. Because, when you look at the benchmarks you find out that you are talking about single-digit percent difference between different techniques sometimes, and variations in cache size, branc…

> direct threaded code (DTC): a VM instruction is just a pointer to the C function implementing it. Nitpick: This sounds more like subroutine threading than direct threading. https://en.wikipedia.org/wiki/Threaded_code In subroutine threaded code, each function implementing an instruction returns before the next one is called. In direct threading, each code snippet implementing an instruction loads the next address a…

It sounds like it, but it is not. It gets confusing fast when one talks about these things in even slightly accurate ways.

In DTC to call a function of the VM code (ie a another piece of DTC) you typically have a "call" virtual instruction, followed by the virtual address to call. you also have a virtual "return" function that pops the virtual instruction pointer from the virtual call stack.

Subroutine threaded is really just a very primitive form of AoT compilation.

Re: Write Your Own Virtual Machine

#77

Post by tom_mellior »

astrobe_ wrote: post #76
tom_mellior wrote: post #74

Earlier quoted context omitted.

> direct threaded code (DTC): a VM instruction is just a pointer to the C function implementing it. Nitpick: This sounds more like subroutine threading than direct threading. https://en.wikipedia.org/wiki/Threaded_code In subroutine threaded code, each function implementing an instruction returns before the next one is called. In direct threading, each code snippet implementing an instruction loads the next address a…

It sounds like it, but it is not. It gets confusing fast when one talks about these things in even slightly accurate ways. In DTC to call a function of the VM code (ie a another piece of DTC) you typically have a "call" virtual instruction, followed by the virtual address to call. you also have a virtual "return" function that pops the virtual instruction pointer from the virtual call stack. Subroutine threaded is re…

None of this explains why you think that your code in which "a VM instruction is just a pointer to the C function implementing it" is direct threaded. If you call a C function for each VM instruction, and that function returns before the next C function is called, then your threading is not direct.

Re: Write Your Own Virtual Machine

#78

Post by KMag »

remcob wrote: post #29
chrisaycock wrote: post #2

One of my favorite techniques for implementing VMs is the "computed goto": https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Consider this example for dispatching instructions from the article: while (running) { uint16_t op = mem_read(reg[R_PC]++) >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; ... } } That code has a…

I like to go one step further and use a first pass to convert bytecodes to a list of labels. Use a pointer in this list as the program counter. Then the dispatch becomes as simple as: goto *pc++; Here's an example of the technique for a Brainfuck VM implemented in the Ethereum VM assembly. (a recent competition entry of mine): https://g.solidity.cc/submissions/wicketh.eth/3bb28842856230... This technique also makes i…

I presume you're aware, but for those reading along at home, this technique is called a "threaded" or "direct threaded" interpreter. Last I read, the BEAM virtual machine (used by Erlang and Elixir) translates arrays of opcodes to arrays of jump addresses at code load time.

For a time, outputting direct threaded code was a popular implementation technique for native code compilers.

I suspect that for many languages, what you really want is a compact SSA distribution format, and at program / library installation time, compile each extended basic block to a block of size-optimized blocks of strait-line native code. Functions would compile to stubs that pass arrays of basic block addresses to a common dispatch loop. In effect, you get a direct-threaded interpreter, where each "opcode" is a piece of strait-line native code from the application. Each basic block would need to set a known register to the address of the next basic block. In other words, the code would be compiled to native continuation-passing-style.

This provides the basis for a very low-overhead tracing JIT for native code. When a profiling timer triggers, the signal handler can walk the stack and perform some hot code detection heuristics. If a hot section is detected, the handler can perform on-stack replacement of the dispatch loop return address with a tracing version of the same. Once a hot loop is detected, the SSA form for each of the involved basic blocks can be stitched together and passed to an optimizing compiler. This would give you the fast start-up of size-optimized native code along with the long-term profile-optimized, cross-library-inlined-and-optimized code of a high performance JIT. The main downside would be the on-disk storage size of keeping both compressed SSA and size-optimized native code.

Alternatively, I could imagine processors with built-in support for native code tracing and optimization. If a trace register was non-zero, then every conditional or indirect branch would store the effective branch target at the location pointed to by the trace register, and increment the trace register by sizeof(size_t). If the trace register were equal to the trace limit register, or a performance timer had expired, then the CPU would trap to a userspace handler indicated by another register. Though, I think you'd need the threaded interpreter version of the idea to become popular before CPU manufactures started to consider the hardware supported version.

Re: Write Your Own Virtual Machine

#79

Post by delinka »

gattr wrote: post #12

I agree it's a great exercise. Years ago I added a very simple stack-based VM to my raytracer to allow procedural textures & normal maps. The scene script would e.g. contain a material description like this: material { diffuse rgb = [0, 0, 1] * (1-(0.5+0.5*noise(x*0.000002, y*0.000002, z*0.000002, 0.66, 2))) + [1, 1, 1] * (0.5+0.5*noise(x*0.000002, y*0.000002, z*0.000002, 0.66, 2)); } i.e. an expression with 3-vector…

Could I trouble you to share the code with me as well? Email in profile about box. Thanks!
Post reply on HN