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

11–20 of 79 posts

Re: Write Your Own Virtual Machine

#11

Post by vardump »

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, aren't that expensive. Mispredicted branches cost 10-20x more.

Of course less branches and less code in general is better.

One big issue writing interpreters in C/C++ is that compiler register allocation can't usually follow the data flow, and needs to keep unnecessarily loading and storing from/to memory same common variables.

Interpreters need to also be careful not to exceed 32 kB L1 code cache limits.

All this means to write a truly efficient interpreter, you'll need to do it in assembler.

The step after that is to write a simple JIT that does away with data dependent (= VM instruction) branches altogether.

Then you'll notice you don't need to update some VM registers every time, but can coalesce for example program counter updates to certain points.

Eventually you'll find you have a full fledged JIT compiler doing instruction scheduling and register allocation, etc.

Been down that rabbit hole, except for the last step. That's where it becomes a true challenge.

LuaJIT (http://luajit.org/) project followed all the way through, and studying it is a great resource for anyone interested on the topic. Kudos to Mike Pall.

Re: Write Your Own Virtual Machine

#12

Post by gattr »

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-vectors and scalars and a few basic functions (noise, sin/cos, etc.). This can be easily "compiled" (during script parsing) for execution on the VM. Then the overhead during actual raytracing was quite small.

Re: Write Your Own Virtual Machine

#13

Post by tonyjstark »

toolslive wrote: post #6
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.

indeed. I think the second optimization on the list is super-instructions: frequent combinations of 2 (or even 3) instructions are transformed into 1 equivalent instruction, lowering the average cycle count.

Where can I learn about techniques like that? Any recommendation would be very appreciated!

Re: Write Your Own Virtual Machine

#14

Post by zeusk »

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…

and what happens on an undefined instruction?

Re: Write Your Own Virtual Machine

#15

Post by vkazanov »

tonyjstark wrote: post #13
toolslive wrote: post #6

Earlier quoted context omitted.

indeed. I think the second optimization on the list is super-instructions: frequent combinations of 2 (or even 3) instructions are transformed into 1 equivalent instruction, lowering the average cycle count.

Where can I learn about techniques like that? Any recommendation would be very appreciated!

Those techniques are a relatively niche thing. People don't write bytecode interpreters daily. Couple of months ago I wrote a few articles on the topic. Unfortunately, they are in Russian. I'll probably translate 'em at some but for now...

the repo and performance measurements are on Github[1]. It includes a couple of dispatch techniques, register caching, etc.

[1]: https://github.com/vkazanov/bytecode-interpreters-post

Re: Write Your Own Virtual Machine

#16

Post by sebcat »

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 googled and found a test[1]. Running this test with a few modifications (like removing unused variables and using PRIu64 instead of %llu) and disregarding the last two prints, I get:

switch = 5589926 goto = 5752079 goto_opt = 5618938

with -O0, and

switch = 2234105 goto = 2013742 goto_opt = 2016200

with -O2.

EDIT:

Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz

gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516

[1] https://gist.github.com/mmozeiko/7cc858985b57df30eebbf8c6e75...

Re: Write Your Own Virtual Machine

#17

Post by vardump »

sebcat wrote: post #16
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 googled and found a test[1]. Running this test with a few modifications (like removing unused variables and using PRIu64 instead of %llu) and disregarding the last two prints, I get: switch = 5589926 goto = 5752079 goto_opt = 5618938 with -O0, and switch = 2234105 goto = 2013742 goto_opt = 2016200 with -O2. EDIT: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516 [1] https://gist.gi…

Wow, you were quick.

Mentioning compiler name + version and exact CPU model would be nice. The difference is small enough that those details can tip the scales.

Re: Write Your Own Virtual Machine

#18

Post by sebcat »

vardump wrote: post #17
sebcat wrote: post #16

Earlier quoted context omitted.

I googled and found a test[1]. Running this test with a few modifications (like removing unused variables and using PRIu64 instead of %llu) and disregarding the last two prints, I get: switch = 5589926 goto = 5752079 goto_opt = 5618938 with -O0, and switch = 2234105 goto = 2013742 goto_opt = 2016200 with -O2. EDIT: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516 [1] https://gist.gi…

Wow, you were quick. Mentioning compiler name + version and exact CPU model would be nice. The difference is small enough that those details can tip the scales.

Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz

gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516

Re: Write Your Own Virtual Machine

#19

Post by toolslive »

tonyjstark wrote: post #13
toolslive wrote: post #6

Earlier quoted context omitted.

indeed. I think the second optimization on the list is super-instructions: frequent combinations of 2 (or even 3) instructions are transformed into 1 equivalent instruction, lowering the average cycle count.

Where can I learn about techniques like that? Any recommendation would be very appreciated!

article below contains an overview and more pointers.

http://realityforge.org/code/virtual-machines/2011/05/19/int...

Re: Write Your Own Virtual Machine

#20

Post by tom_mellior »

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.

Yes, but that is not the optimization discussed here. The optimization discussed here is looking ahead to the next bytecode instruction's opcode, using it as a key into a different jump table, and jumping to that target. No C compiler I'm aware of does that.

C compilers could try to match on common patterns in interpreter implementation (a switch within a loop, keyed on certain bits of a piece of data read mostly linearly from an array) and heroically generating a dispatch table, but that would still fail in the cases of branches where you don't want to call DISPATCH because execution does not necessarily proceed to the next instruction in the array.

Post reply on HN