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

Implementing a Virtual Machine in C

blog.felixangell.com

Post reply on HN
Print view View original

41–50 of 54 posts

Re: Implementing a Virtual Machine in C

#41

Post by ternaryoperator »

dandrews wrote: post #23
ternaryoperator wrote: post #15

I find these kinds of very basic intro articles frustrating. They till the same ground over and over: a tiny instruction set implemented with a switch statement. None of the more difficult issues are addressed: exception handling, linking to libraries or other programs written for the same VM, portability of programs across architectures, accessing the OS for services like file I/O, time, etc.-- All the things that m…

That's a little ungenerous of you. The toy VM has presented an aha! moment to all of us at one time - or more than once, when you learn about Turing equivalence and the rabbit hole that leads from that. Skip the articles beneath your skill level and move along.

Agreed, it was a bit ungenerous, esp. b/c I didn't realize til someone mentioned it below that the author was a teenager.

My objection, though, is not what's above/below me, it's that given the title, I was expecting a deeper article only to find one that has appeared numerous times. It was frustration I was expressing more than condescension. But you're quite right in using the term "ungenerous." I appreciate the gentle reproof.

Re: Implementing a Virtual Machine in C

#42

Post by gsg »

rdc12 wrote: post #40
tptacek wrote: post #20

Earlier quoted context omitted.

Stack VMs aren't used just because they're easier to understand: * In interpreted environments, registers are stored in memory anyways, so the advantage of simulating them isn't as great * It is easier to generate code for stack machines, because you don't need to run register allocation * There's a tradeoff in instruction complexity versus number of instructions between stack and register machines

This paper [1] (thou it is a tad old now) shows that the register machine approach does still outperform the stack machine by a fair margin. Largely from the reduction of needed instructions. Wonder which is a better source represntation for a JIT thou. [1] https://www.usenix.org/legacy/events/vee05/full_papers/p153-...

JIT compilers aren't really an argument either way, as you can do tracing or transform to an SSA graph from either representation quite easily. All the real complexity is further down the compilation pipeline.

I (half) wrote a toy trace compiler based on a register bytecode a while back. Writing the front end was quite pleasant - the difficult parts were back end stuff like figuring out how to support trace exit information. (The difficulty there is that you might want to perform stores, materialize objects etc as you go off trace as part of store and allocation sinking.)

Re: Implementing a Virtual Machine in C

#44

Post by rounak »

vbezhenar wrote: post #35

For those who want to implement a VM as an exercise, I recommend to implement a simple JIT-compiler after that. You'll probably be impressed at performance improvements and it's funny exercise to do. I used GNU lightning to generate machine code.

Any pointers/links/tutorials for this? Thanks.

Re: Implementing a Virtual Machine in C

#45

Post by rounak »

ternaryoperator wrote: post #15

I find these kinds of very basic intro articles frustrating. They till the same ground over and over: a tiny instruction set implemented with a switch statement. None of the more difficult issues are addressed: exception handling, linking to libraries or other programs written for the same VM, portability of programs across architectures, accessing the OS for services like file I/O, time, etc.-- All the things that m…

You're being unnecessarily harsh. If you got frustrated means it wasn't targeted towards you.

Would appreciate if you did an advanced version of this writeup :)

Re: Implementing a Virtual Machine in C

#46

Post by rurban »

gsg wrote: post #38
userbinator wrote: post #37

Earlier quoted context omitted.

In interpreted environments, registers are stored in memory anyways, so the advantage of simulating them isn't as great ...unless the interpreter maps VM registers directly onto machine registers. With some VMs it's possible, and then you can get very good performance.

That would be very inefficient, because registers cannot be indexed. The dispatch you have to introduce to jump to code that references the right physical regs would murder you with mispredictions. Also, register VMs typically have three operands. Specialising each instruction for each possible register for three operands would result in a ridiculous volume of code. Special purpose instructions that access fixed regi…

> Also, register VMs typically have three operands.

Wrong. Only SSA VMs (with an optimizing compiler) need three operands. Simple register VMs as well as hardware CPUs have two operands only, and you can easily fit them into one word then.

You cannot do better SSA based optimizations then, but the VM speed is much faster than with two or multi word ops, which blow up your instruction cache. lua has to use shorter ranges to get 3 operands into one word.

Writing a JIT with two-address ops is also trivial. It's a straightforward conversion using fixed registers.

Sample: https://github.com/perl11/potion

> Specialising each instruction for each possible register for three operands would result in a ridiculous volume of code.

Nobody does that, it's not needed.

> Special purpose instructions that access fixed registers would be fine, but general purpose operand references cannot be sanely implemented in this way. Existing register VMs use memory because it's faster.

No. You need general purpose operand insns for only one or two fixed registers (eax, edx typically). Nobody implements all possible combinations. And you use the stack to shuffle values around, not memory.

Re: Implementing a Virtual Machine in C

#47

Post by gsg »

rurban wrote: post #46
gsg wrote: post #38

Earlier quoted context omitted.

That would be very inefficient, because registers cannot be indexed. The dispatch you have to introduce to jump to code that references the right physical regs would murder you with mispredictions. Also, register VMs typically have three operands. Specialising each instruction for each possible register for three operands would result in a ridiculous volume of code. Special purpose instructions that access fixed regi…

> Also, register VMs typically have three operands. Wrong. Only SSA VMs (with an optimizing compiler) need three operands. Simple register VMs as well as hardware CPUs have two operands only, and you can easily fit them into one word then. You cannot do better SSA based optimizations then, but the VM speed is much faster than with two or multi word ops, which blow up your instruction cache. lua has to use shorter ran…

Multiple real implementations of register VMs have three operand instructions. Lua, Luajit and Guile are examples that I'm familiar with. For that matter, many ISAs feature three operand instructions. Even some of the recent extensions to x86-64 are three operand versions of (some of) the vector instructions.

If you think three-operand instructions aren't common in both hardware and interpreter design, you are simply misinformed.

None of this has anything to do with SSA. SSA IR can be reasonably constructed from any of stack, accumulator, two-operand register or three operand register bytecode. All of the usual optimizations follow from that.

> the VM speed is much faster than with two or multi word ops

While variable length encodings are best avoided, that doesn't rule out three operand instructions. For a good example of an extremely fast interpreter that uses such instructions, have a look at luajit.

> Nobody does that, it's not needed.

That's what the OP was suggesting, so that's what I was discussing.

Re: Implementing a Virtual Machine in C

#49

Post by sdoering »

aikah wrote: post #30
neverartful wrote: post #13

Contrary to the naysayers, I like seeing stuff like this. Why? Because it's a simple, gentle introduction. It's easily digestible for the newcomer. And it might be easy enough to encourage a newcomer to start building their own VM that goes on to be something real. For those that criticize it and find faults with it -- I'm sure the author would consider pull requests. Or you could provide your own fork with all the i…

Calling people who criticize that blog post "naysayers" is childish, at best. Once something is out there on the web it's going to get some criticism, that's normal.There is nothing wrong with that.

The question (and OP made that clear) is how you criticize. Trolling is not the right way, I believe.

Cosplaying Captain Obvious neither.

Re: Implementing a Virtual Machine in C

#50

Post by amelius »

This project is nice for educational purposes, but I wouldn't call it a VM, but instead a "bytecode interpreter".

I think nowadays it is kind of a minimum requirement to have the intermediate code JIT-compiled (or at least compiled).

I'm also missing a garbage collector, although that is not necessarily part of a VM (but often is). See NaCl for a counterexample. By the way, a project that I'd like to see is an efficient garbage collector implemented inside the VM, instead of as being part of the VM.

Post reply on HN