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

21–30 of 79 posts

Re: Write Your Own Virtual Machine

#21

Post by tom_mellior »

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…

If you're looking for a bigger and more "real-world" test, the Python interpreter can be built with or without computed gotos for dispatch. It suffices to arrange to define USE_COMPUTED_GOTOS to 0 in Python/ceval.c. You can just change the file by hand, but I vaguely remember there also being a configure flag for setting USE_COMPUTED_GOTOS or HAVE_COMPUTED_GOTOS.

Then run your favorite Python benchmark. For reasonable results, it must be one that spends almost all of its time in Python code, which excludes calls to native code libraries, but also Python programs that mostly do list manipulation like the popular fannkuch benchmark. (The list operations are implemented in C, and fannkuch, although looking like a Python program, spends most of its time in this C library.)

Re: Write Your Own Virtual Machine

#22

Post by tom_mellior »

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!

Look up work by Stefan Brunthaler, like this overview paper ("Virtual-Machine Abstraction and Optimization Techniques"): https://www.sba-research.org/wp-content/uploads/publications...

Make sure to check out the references. I especially like "Ertl, M. A. and D. Gregg, The structure and performance of efficient interpreters, Journal of Instruction-Level Parallelism 5 (2003)"

Re: Write Your Own Virtual Machine

#23

Post by tom_mellior »

zeusk wrote: post #14
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?

Typically an undefined instruction "can't happen" because the interpreter assumes that it gets its code from a trusted frontend that validated all the invariants assumed by the interpreter. The most important being that, for any instruction that might use DISPATCH, there actually is a next instruction at the following address. This means that every block of code must end in an unconditional branch and that unconditional branches must not dispatch using DISPATCH (which would not make sense anyway).

Re: Write Your Own Virtual Machine

#24

Post by sifoobar »

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 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. And as an added bonus the code is much nicer to deal with and more extendable, since the set of operations isn't hardcoded any more.

Comparing language performance is tricky business, but it mostly runs faster than Python3 from my tests so far. My point is that computed goto is not the end of the story.

I'll just add that there are many different ways to write a VM; the one posted here is very low level, the one linked below reasonably high level. Using physical CPUs as inspiration is all good, but there's nothing gained from pretending in itself unless you're compiling to native code at some point.

[0] http://www.emulators.com/docs/nx25_nostradamus.htm

[1] https://gitlab.com/sifoo/snigl

Re: Write Your Own Virtual Machine

#25

Post by jonathanstrange »

I once implemented a VM in Ada and just used a large switch. I extensively benchmarked it and it was blazingly fast at -O3.

However, it was only fast when I used packages very sparingly. In contrast to the usual advice given in the Ada community, splitting up the implementation into several packages slowed down the main loop tremendously. I suspect this wouldn't happen with whole-program optimization in C, but believe that the version of gcc I was using didn't support that for Ada. Also, my Green Threads were slower than a single thread, no matter which tricks I tried.

It's an abandoned project now, since the accompanying assembler was hacked together in Racket and at some point I simply lost track of what was going on where :O

Re: Write Your Own Virtual Machine

#26

Post by JustSomeNobody »

techno_modus wrote: post #7

I like this tutorial but it should be mentioned that before implementing a virtual machine one should understand that there are many computing models and many alternative mechanisms within each of them. Implementing VM for sequential program execution is relatively easy. What is more (conceptually) difficult is concurrency, asynchronous processes etc.

> What is more (conceptually) difficult is concurrency, asynchronous processes etc.

Know any good resources for these?

Re: Write Your Own Virtual Machine

#27

Post by henrikeh »

jonathanstrange wrote: post #25

I once implemented a VM in Ada and just used a large switch. I extensively benchmarked it and it was blazingly fast at -O3. However, it was only fast when I used packages very sparingly. In contrast to the usual advice given in the Ada community, splitting up the implementation into several packages slowed down the main loop tremendously. I suspect this wouldn't happen with whole-program optimization in C, but believ…

FYI: I believe you have to use the flag -gnatn or -gnatN to inline packages with GNAT.

Optimizing your project: https://www.pegasoft.ca/resources/boblap/7.html

GNAT: Alphabetical list of all switches: https://gcc.gnu.org/onlinedocs/gcc-8.2.0/gnat_ugn/Alphabetic...

Re: Write Your Own Virtual Machine

#28

Post by dana321 »

techno_modus wrote: post #7

I like this tutorial but it should be mentioned that before implementing a virtual machine one should understand that there are many computing models and many alternative mechanisms within each of them. Implementing VM for sequential program execution is relatively easy. What is more (conceptually) difficult is concurrency, asynchronous processes etc.

Thats one of the main reasons i implemented my VM in go.

Its fairly rudimentary, a map for instructions to function pointers but.. I can quickly duplicate a subtree of code and execute it within a different goroutine, and wrap that section of code in an instruction that sets the output to a channel, and have another goroutine select the different channels from different goroutines.

At each node within the tree of code, i store the variables within a map instead of using a stack-based system; if the data is not in the current node, look down the tree until i find it.

Re: Write Your Own Virtual Machine

#29

Post by remcob »

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 it easy to do some peephole optimizations and combine multiple bytecodes into a single label. The above example also does a lot of that.

Brainfuck is actually a great language to built a VM for. You have a simple interpreter up in no time, but you can go really far in optimizing it. LC3 looks comparatively messy (more state, more instructions, etc), but more representative of real CPUs.

Re: Write Your Own Virtual Machine

#30

Post by sifoobar »

JustSomeNobody wrote: post #26
techno_modus wrote: post #7

I like this tutorial but it should be mentioned that before implementing a virtual machine one should understand that there are many computing models and many alternative mechanisms within each of them. Implementing VM for sequential program execution is relatively easy. What is more (conceptually) difficult is concurrency, asynchronous processes etc.

> What is more (conceptually) difficult is concurrency, asynchronous processes etc. Know any good resources for these?

My own baby, Snigl [0], does always-on cooperative concurrency and asynchronous IO.

Just ask if you need help finding your way around.

https://gitlab.com/sifoo/snigl

Post reply on HN