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

41–50 of 79 posts

Re: Write Your Own Virtual Machine

#41

Post by tom_mellior »

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…

> so don't bother shooting the messenger

OK, let's shoot the original source: It only found that a certain unnamed version of GCC ten years ago performed tail merging, which does indeed defeat the purpose of the optimization. Without the author bothering to turn off tail merging in this case (as Python does), this doesn't mean much.

> Comparing language performance is tricky business, but it mostly runs faster than Python3 from my tests so far.

Presumably you not only have a different interpretation approach, but also a different object model, approach to boxing numbers, and garbage collector. "Tricky business" is a bit of an understatement ;-)

Re: Write Your Own Virtual Machine

#42

Post by tombert »

I love these kinds of tutorials, and really any tutorial that makes me think of stuff that was previously "magic" and makes me feel stupid for not previously understanding it after I read it (I honestly mean that in a positive way).

This will be a fun weekend project for me...I have had an idea of a lambda-calculus-based VM that I've wanted to build for a few months ago, and I think this will be a good start for me to understand it.

Re: Write Your Own Virtual Machine

#43

Post by sifoobar »

tom_mellior wrote: post #41
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…

> so don't bother shooting the messenger OK, let's shoot the original source: It only found that a certain unnamed version of GCC ten years ago performed tail merging, which does indeed defeat the purpose of the optimization. Without the author bothering to turn off tail merging in this case (as Python does), this doesn't mean much. > Comparing language performance is tricky business, but it mostly runs faster than P…

Better him than me. I wouldn't be so quick to dismiss relevant coding experience, it doesn't get old. Much of his reasoning about locality still holds, to an even greater degree today.

I've implemented more or less the same interpreter using computed goto and various variations on dispatch loops; and this is the fastest solution I've managed to come up with, and the nicest code to work with. Still too many parameters, my point is that I have plenty of experience pointing in that direction which is better than nothing. It's not a mystery to me. Using computed goto will involve some kind of lookup to get the relevant labels, I'm using pointers to actual instructions as jump targets. And since I'm longjmp'ing out, which means I don't need a loop condition; the loop is reduced to a single regular goto.

Like I said, better than nothing. There is no such thing as perfection in this world. I've spent quite some time [0] micro benchmarking different features to get a fair comparison.

[0] https://gitlab.com/sifoo/snigl/tree/master/bench

Re: Write Your Own Virtual Machine

#44

Post by TimJYoung »

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…

Object Pascal (Delphi) also optimizes case statements, depending upon the nature of the statement:

https://stackoverflow.com/a/2548425

I tested this recently (Delphi XE6), and it definitely is as-described: you get straight jump instructions with enough case statement branches, and it is very fast.

Barry Kelly worked on the Delphi compiler, and I believe he comments here on Hacker News occasionally.

Re: Write Your Own Virtual Machine

#45

Post by lukego »

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…

I’m writing a C port of the LuaJIT VM at the moment. I’m hoping that will help people to understand the overall design and make it easier to interpret the asm code (amongst other things). Link: https://github.com/raptorjit/raptorjit/pull/199

Re: Write Your Own Virtual Machine

#46

Post by vardump »

TimJYoung wrote: post #44
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…

Object Pascal (Delphi) also optimizes case statements, depending upon the nature of the statement: https://stackoverflow.com/a/2548425 I tested this recently (Delphi XE6), and it definitely is as-described: you get straight jump instructions with enough case statement branches, and it is very fast. Barry Kelly worked on the Delphi compiler, and I believe he comments here on Hacker News occasionally.

> you get straight jump instructions with enough case statement branches, and it is very fast

That's what pretty much any half-decent compiler does nowadays. It'd be much more surprising if it didn't.

Re: Write Your Own Virtual Machine

#47

Post by JustSomeNobody »

sifoobar wrote: post #30
JustSomeNobody wrote: post #26

Earlier quoted context omitted.

> 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

Thank you. I’ll check it out over the holidays.

Re: Write Your Own Virtual Machine

#48

Post by tom_mellior »

sifoobar wrote: post #43
tom_mellior wrote: post #41

Earlier quoted context omitted.

> so don't bother shooting the messenger OK, let's shoot the original source: It only found that a certain unnamed version of GCC ten years ago performed tail merging, which does indeed defeat the purpose of the optimization. Without the author bothering to turn off tail merging in this case (as Python does), this doesn't mean much. > Comparing language performance is tricky business, but it mostly runs faster than P…

Better him than me. I wouldn't be so quick to dismiss relevant coding experience, it doesn't get old. Much of his reasoning about locality still holds, to an even greater degree today. I've implemented more or less the same interpreter using computed goto and various variations on dispatch loops; and this is the fastest solution I've managed to come up with, and the nicest code to work with. Still too many parameters…

Oh, I wasn't dismissing experience in general, nor was I questioning your experiences. I would love to see your numbers on the different dispatch methods you tried.

I was only questioning that one blog post you linked that lazily said (paraphrasing) "computed-goto dispatch will be undone by the compiler, so don't bother". Others have posted numbers in this thread (https://news.ycombinator.com/item?id=18679477) showing that this information is at best outdated.

Re: Write Your Own Virtual Machine

#49

Post by TimJYoung »

vardump wrote: post #46
TimJYoung wrote: post #44

Earlier quoted context omitted.

Object Pascal (Delphi) also optimizes case statements, depending upon the nature of the statement: https://stackoverflow.com/a/2548425 I tested this recently (Delphi XE6), and it definitely is as-described: you get straight jump instructions with enough case statement branches, and it is very fast. Barry Kelly worked on the Delphi compiler, and I believe he comments here on Hacker News occasionally.

> you get straight jump instructions with enough case statement branches, and it is very fast That's what pretty much any half-decent compiler does nowadays. It'd be much more surprising if it didn't.

The interesting part to me was the variations in the emitted instructions, based upon the source. IOW, it would be easy to mistakenly think that you weren't going to get jumps if you only used a few case branches to test things out.

Re: Write Your Own Virtual Machine

#50

Post by astrobe_ »

banachtarski wrote: post #5
sgillen wrote: post #3

Earlier quoted context omitted.

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

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, branch prediction, even unaligned memory fetch tax on odd targets, all these details can make a different king-of-the-hill on a different processor. Compilers can also deal with a technique better than another.

You can gain far more by working on your instruction set. Making it easily extendable is better, making it easy to transpose interpreted code into native code is better, because you can easily benchmark and optimize as you have a more and more clear idea of what will be idiomatic code. For the DTC technique, a bonus is that there's normally no difference between instructions and library bindings.

Post reply on HN