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

61–70 of 79 posts

Re: Write Your Own Virtual Machine

#61

Post by grawprog »

sifoobar wrote: post #24
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…

For the longest time, I swore by computed goto as well. But it has its share of problems; it's not very portable; it forces the code into a rigid, non-extendable format; and it's not as efficient as commonly assumed. I'm far from the first person to notice [0], so don't bother shooting the messenger. My latest project [1] simply calls into a struct via a function pointer for each instruction. With a twist. Since it r…

The way I ended up structuring my opcodes was similar to your way but a little different still. I ended up using function pointers but an array of them. Each opcode is defined in an enum and will be assigned to each funtion pointer based on it's corresponding array index. When the virtual CPU reads an opcode it just calls the function pointed to by the pointer at that index.

I found doing it this way makes it easy to change or add opcodes without needing to go back through a giant switch statement to find and rearrange everything. As a bonus too, the assembler just uses the same enum and basically just works through it the opposite way the CPU does. Translating keywords to the matching opcode index in the array then writing the index to the correct memory address in the binary. This also means any time I update an opcode or add one in the virtual machine all I have to do is add it to the enum and both the assembler and virtual machine will be updated without having to do anything else.

Re: Write Your Own Virtual Machine

#62

Post by chubot »

morazow wrote: post #31

Off-topic. Does anyone know how I can convert AST into stream of bytecodes? Are there any good example language implementations to learn?

If you want to play with the algorithms at a high level [1], there are two Python AST -> bytecode implementations I've seen, and one that I'm using.

(1) The 'compiler' module from Python 2. I'm using this to build my shell project Oil, so it works.

See Building Oil with the OPy Bytecode Compiler: http://www.oilshell.org/blog/2018/03/04.html . The heavily refactored source is in the opy/compiler2 directory of the repo on Github.

(This module was removed in Python 3 due to its redundancy with the C implementation. But there's no conceptual difference between Python 2 and 3. Some small details have changed.)

(2) tailbiter, which I mentioned here: http://www.oilshell.org/blog/2018/03/27.html

They are written in very different styles. Tailbiter reads like Lisp code, which may or may not be what you want.

The generated bytecode is different in the sense that the values it operates on aren't just ints and floats (which hardware deals with), but they are dynamically typed objects. But this doesn't change the overall algorithm to generate bytecode from an AST.

[1] which I recommend over doing it in C or C++, because ASTs are somewhat annoying in those languages

Re: Write Your Own Virtual Machine

#63

Post by sifoobar »

grawprog wrote: post #61
sifoobar wrote: post #24

Earlier quoted context omitted.

For the longest time, I swore by computed goto as well. But it has its share of problems; it's not very portable; it forces the code into a rigid, non-extendable format; and it's not as efficient as commonly assumed. I'm far from the first person to notice [0], so don't bother shooting the messenger. My latest project [1] simply calls into a struct via a function pointer for each instruction. With a twist. Since it r…

The way I ended up structuring my opcodes was similar to your way but a little different still. I ended up using function pointers but an array of them. Each opcode is defined in an enum and will be assigned to each funtion pointer based on it's corresponding array index. When the virtual CPU reads an opcode it just calls the function pointed to by the pointer at that index. I found doing it this way makes it easy to…

Nice to hear! That's what I try to tell people who are asking for the right type theory book or the right dispatch method or whatever before even having a look. It's the same old problem solving; and here are always multiple solutions, each with it's own set of compromises. Claiming the one true way of doing anything related to software is delusional. We're barely scratching the surface.

Edit: While we're here; may I ask how you break out of the dispatch loop? Do you test an end-condition on each iteration? If that's the case, the longjmp trick might be worth trying. The condition will mostly be false, so it might make sense to pay more when it happens instead. You may find the essence of it in sgl_run at the bottom of sgl.c [0].

[0] https://gitlab.com/sifoo/snigl/blob/master/src/snigl/sgl.c#L...

Re: Write Your Own Virtual Machine

#65

Post by carapace »

morazow wrote: post #31

Off-topic. Does anyone know how I can convert AST into stream of bytecodes? Are there any good example language implementations to learn?

A little tangential, but check out "Prolog as Description and Implementation Language in Computer Science Teaching"by Henning Christiansen

http://www.ep.liu.se/ecp/012/004/ecp012004.pdf

> ... Definitional interpreters, compilers, and other models of computation are defined in a systematic way as Prolog programs, and as a result, formal descriptions become running prototypes that can be tested and modified ... These programs can be extended in straightforward ways into tools such as analyzers, tracers and debuggers.

Also "Logic Programming and Compiler Writing" By David Warren (and the work that followed on.)

Re: Write Your Own Virtual Machine

#66

Post by rurban »

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…

The only difference between the computed goto and the switch is that the computed goto leaves out the initial range check. But are doing simple and costly indirect jumps.

Much better is to keep the ops small (16bit in this case which is the best I've seen, lua/luajit/chez have 32bit, worse languages 3-5 words) to have much more ops in the icache, and to pass around the ptr to the next op, best if relative. Easy with a small jit. This ptr will be prefetched, which is not possible with those indirect jumps, from cgo or switch.

Re: Write Your Own Virtual Machine

#67

Post by acqq »

kazinator wrote: post #58
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…

> the break statement branches to the bottom, and then there is third branch to get back to the top of the while loop That suggests your C compiler isn't doing jump threading: replacing the jump to an unconditional jump instruction with a direct jump to that instruction's destination. That's a very basic optimization I might expect even from a C compiler written in 1980.

> That suggests your C compiler isn't doing jump threading

And even if he has such a compiler (which is doubtful) he doesn't have to put the "break" in the switch! He can write continues, e.g. this:

        switch ( i ) {
        case 3:
            i = 7; continue;
        default:
            continue;
        }
is valid C, and specifies explicitly that the next loop pass is expected.

Re: Write Your Own Virtual Machine

#68

Post by vardump »

sifoobar wrote: post #63
grawprog wrote: post #61

Earlier quoted context omitted.

The way I ended up structuring my opcodes was similar to your way but a little different still. I ended up using function pointers but an array of them. Each opcode is defined in an enum and will be assigned to each funtion pointer based on it's corresponding array index. When the virtual CPU reads an opcode it just calls the function pointed to by the pointer at that index. I found doing it this way makes it easy to…

Nice to hear! That's what I try to tell people who are asking for the right type theory book or the right dispatch method or whatever before even having a look. It's the same old problem solving; and here are always multiple solutions, each with it's own set of compromises. Claiming the one true way of doing anything related to software is delusional. We're barely scratching the surface. Edit: While we're here; may I…

> Edit: While we're here; may I ask how you break out of the dispatch loop? Do you test an end-condition on each iteration? ...

For what it is worth my JITter uses mprotect from other thread to change page permissions to generate an exception to break out of JITted code. Same would work for dispatcher as well.

The advantage is it's completely free performance wise while the code is running. The need for signal handler is less awesome.

Re: Write Your Own Virtual Machine

#69

Post by wahern »

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…

It'll be even faster without indirecting through dispatch_table at runtime. Exporting your label addresses without introducing a conditional initialization block is tricky but doable. For C++ you can (IIRC) smuggle dispatch_table out of the routine using a constructor on a statically-scoped object. For C code I've successfully used GCC's nested function and __attribute__((constructor, used)) extensions, though that was with 4.7 (may not work with current GCC).

I mostly use computed gotos for implementing poor-man's coroutines in C, where the addresses only need to be visible within the routine. For VMs I use the obvious method (i.e. dispatch_table) to keep the code sane, but it does incur a non-negligible performance cost, which may matter in some contexts.

Re: Write Your Own Virtual Machine

#70

Post by wahern »

sifoobar wrote: post #24
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…

For the longest time, I swore by computed goto as well. But it has its share of problems; it's not very portable; it forces the code into a rigid, non-extendable format; and it's not as efficient as commonly assumed. I'm far from the first person to notice [0], so don't bother shooting the messenger. My latest project [1] simply calls into a struct via a function pointer for each instruction. With a twist. Since it r…

> Since it returns the pointer to the next operation and uses longjmp to stop the program, which means I can get away without lookups and without a loop condition.

That threaded approach would be even faster using computed gotos. The loop conditional is a huge performance killer. Removing it claws back cycles from using function pointers, but it would benefit the computed goto approach at least much.

Personally I find using function pointers make for difficult to read code. Dispatching opcodes with a compact switch statement (or equivalent computed goto construction) makes it easier for me to see the meat of the engine and how it works. If the logic for an opcode is complex it can be easily pushed into a static function (which may or not be inlined, but at such a juncture readability is the primary concern). But for simple operations I prefer it inline, textually, so it's easier to see all the moving parts at once.

Post reply on HN