4 ms·

TinyVM 1.0 released; adds 16 lines of code, registers, a VM stack and more

121 points by davedx 15y ago

joeyespo 15y ago
This is one of those projects I've always wanted to do myself, but never actually spent the time to get it right. Looks good.
jws 15y ago
Most files have a last commit message of: Nothing left can be taken away. That pretty much sums up the target for this VM. Instruction dispatching and malloc handling were discussed here last month in http://news.ycombinator.com/item?id=2722383 http://news.ycombinator.com/item?id=2722383 (Instruction dispatch is now a switch† instead of chain of if statements, malloc() results are still unchecked.) ␄ † The switch was slower in my benchmarks last time, I don't have time to check this time.
- jsherer 15y ago
  How many of the previous discussion points / issues have been changed in this release? Just the switch?
sitkack 15y ago
TVM has 9 registers, modeled after x86 registers
- maaku 15y ago
  But in hardware at least, the x86 registers have been found quite limiting on software and performance. That's why AMD64 doubles the number of general purpose registers. Does anyone know if there is research into the effects of register counts on VMs?
  - carbonica 15y ago
    > But in hardware at least, the x86 registers have been found quite limiting on software and performance. While the doubled register count makes a big difference - especially with the new x86-64 calling convention - register renaming and hidden registers do a lot on x86 to mitigate the lack of general purpose registers. You don't need more than 8 registers to get the benefits of having more than 8.
    - maaku 15y ago
      Which basically amounts to the same thing. "x86" processors today are actually RISC(-like) processors with large register spaces and three-operand instructions, because that hardware can be made faster, even with the necessary silicon x86->RISC translator so software sees an x86 processor. But to my knowledge, compatibility with legacy compiled software is not a practical issue for VM's. And even if it were, this isn't a compatible implementation of x86 anyway. So what then is the reasoning for this choice?
      - carbonica 15y ago
        It's close to the same thing, but having more named registers does provide more optimization opportunities. It shouldn't be completely ignored as a good thing. I mentioned function calls because that's a boundary when an optimizer - either in-processor or in-compiler - is often forced to use memory and not registers. The big-N-register "register window" of RISC processors kicks this problem's ass. But with aggressive inlining already common, these boundaries don't come up as often as you'd think. So the x86-64 calling convention does a pretty damn good job too. Edit: by the way, I guess I haven't really commenting on TinyVM one way or the other when I responded to you. You're absolutely right and the compatibility is not necessary at all. I think the register count limitation especially is just silly. I pointed out in a different thread that they could double their register count and they'd still fit in a single cache line... they even already have a naming convention (r08-r15) they can hijack.
  - Someone 15y ago
    If you can map all VM registers to CPU registers, the interpreter will be way simpler. If you have more VM registers than CPU registers, you have to write code to load and store your VM registers. If you have more CPU registers than VM registers, you will have to write code to undo some of the register spilling done by the compiler (if you want your VM to use the hardware to the fullest.) So, the optimum (from a viewpoint of 'makes implementation easier') depends on the target architecture. Of course, a generic VM cannot know how many registers (and what kinds; uniform register files are not universally present) the target CPU will have. That is a reason that choosing either zero (i.e. a stack machine) or infinitely many (i.e. SSA) are popular choices fo VMs: for the first, you know for sure your target will not have fewer registers than your VM, for the second, that it will not have more. If you choose any other number of VM registers, a fast generic VM will have to handle both cases. Alternatively, of course, one can target a specific architecture, and have the VM be fairly close to the target; Google's NaCl is (was? I think they changed things a bit) an extreme example. I have not checked the code, but this, I think, is similar.
maaku 15y ago
This appears to be very heavily influenced by x86. Why would a VM built in 2011 use an ISA stuck in the 80's? EDIT: I'm not trolling, I'm seriously wondering. There's plenty of literature out there on the advantages of three-operand instructions, large register spaces, and RISC-type instructions. Was there a reason that x86 was used as a basis?
- aninteger 15y ago
  I'm not the author but I guess there would be a few reasons: 1. Familiarity with x86 assembly. It's probably the assembly language that the majority of people who write assembly language know. 6502 probably being 2nd place 2. Easier to port small x86 assembly programs 3. Even if it's stuck in the 80's it's the most widely used assembly language and there are dedicated online communities of people still writing x86 asm today in 2011.
  - xyzzyz 15y ago
    2. Easier to port small x86 assembly programs I seriously doubt that people will do it. If people write assembly, they mostly do it either because of speed, or because it's impossible to do in any other way. None of the reason is relevant in context of VM assembly, which is usually meant to be a compiler's target.
    - carbonica 15y ago
      Yeah - the vast majority of x86 assembly written today is written to take advantage of specialized instructions that aren't available in this VM.
- carbonica 15y ago
  The instruction set is vastly simpler than x86, but it does inherit some limitations for no reason. x86 had 8 named registers for so long because the mod_rm byte in x86 only has 3 bits for each operand. Adding the REX prefix byte in x86=64 complicates things a bit, but isn't too tough. This VM doesn't have a particularly compact in-memory encoding - it uses an entire `int` for each argument! They could double the number of registers and the entire register set would fit in a cache line (except for EIP) at 4 bytes apiece. I guess it is nice that all 9 fit in one line now, but I doubt that was considered.
diminish 15y ago
i ll make a de-pull request, to remove more.
- swah 15y ago
  I enjoyed your comment, but will downvote you because I was downvoted when doing similar jokes.
RodgerTheGreat 15y ago
If you find TinyVM interesting, one of my own projects might be worth checking out: https://github.com/JohnEarnest/Mako/blob/master/MakoVM.java https://github.com/JohnEarnest/Mako/blob/master/MakoVM.java It's a stack-oriented VM, similarly designed to be as simple as possible, but my goal was to create something like an idealized game console. Thus, I have basic graphics support and gamepad input. The project includes a compiler for a dialect of Forth and a big pile of example code.
- chrisb 15y ago
  In a slightly similar vein, you might enjoy looking at my Dot Net Anywhere project: https://github.com/chrisdunelm/DotNetAnywhere/tree/master/dna https://github.com/chrisdunelm/DotNetAnywhere/tree/master/dn... (or http://www.dotnetanywhere.org http://www.dotnetanywhere.org for an easy to use zip download that will load and compile directly on Windows) It is an almost complete .NET2.0 CIL interpreter, so it can run your exe's compiled from C#/VB/etc... I'm not sure it has much practical application, but it was certainly fun to write, and I learnt a huge amount about interpreters and how .NET works. PS Lots of bugs, a memory leak, an incomplete base class library, etc... so don't try to use this for anything serious!
DanielHimmelein 15y ago
Some more resources about virtual machines and a little TinyVM overview: http://himmele.blogspot.com/2011/08/virtual-machines.html http://himmele.blogspot.com/2011/08/virtual-machines.html
deleted 15y ago
[deleted]
hiker 15y ago
Is this solving the same problem that LLVM has solved already better (by supporting both interpretation and JIT)?
spitfire 15y ago
It's nice to see the huge if/then waterfall has been replaced with a switch statement. That was quite the code smell there. I'm still as impressed as when I first saw it. Small, simple and elegant. Neat little project.
parbo 15y ago
If you want to program a VM and have some fun at the same time, do the 2006 ICFP contest: http://www.boundvariable.org/task.shtml http://www.boundvariable.org/task.shtml You have to implement a VM and run the provided program. This will give you access to the actual problem set.

121 points by davedx 15y ago

This is one of those projects I've always wanted to do myself, but never actually spent the time to get it right. Looks good.

jws 15y ago

Most files have a last commit message of: Nothing left can be taken away. That pretty much sums up the target for this VM. Instruction dispatching and malloc handling were discussed here last month in http://news.ycombinator.com/item?id=2722383 http://news.ycombinator.com/item?id=2722383 (Instruction dispatch is now a switch† instead of chain of if statements, malloc() results are still unchecked.) ␄ † The switch was slower in my benchmarks last time, I don't have time to check this time.

jsherer 15y ago
How many of the previous discussion points / issues have been changed in this release? Just the switch?

sitkack 15y ago

TVM has 9 registers, modeled after x86 registers

maaku 15y ago
But in hardware at least, the x86 registers have been found quite limiting on software and performance. That's why AMD64 doubles the number of general purpose registers. Does anyone know if there is research into the effects of register counts on VMs?
- carbonica 15y ago
  > But in hardware at least, the x86 registers have been found quite limiting on software and performance. While the doubled register count makes a big difference - especially with the new x86-64 calling convention - register renaming and hidden registers do a lot on x86 to mitigate the lack of general purpose registers. You don't need more than 8 registers to get the benefits of having more than 8.
  - maaku 15y ago
    Which basically amounts to the same thing. "x86" processors today are actually RISC(-like) processors with large register spaces and three-operand instructions, because that hardware can be made faster, even with the necessary silicon x86->RISC translator so software sees an x86 processor. But to my knowledge, compatibility with legacy compiled software is not a practical issue for VM's. And even if it were, this isn't a compatible implementation of x86 anyway. So what then is the reasoning for this choice?
    - carbonica 15y ago
      It's close to the same thing, but having more named registers does provide more optimization opportunities. It shouldn't be completely ignored as a good thing. I mentioned function calls because that's a boundary when an optimizer - either in-processor or in-compiler - is often forced to use memory and not registers. The big-N-register "register window" of RISC processors kicks this problem's ass. But with aggressive inlining already common, these boundaries don't come up as often as you'd think. So the x86-64 calling convention does a pretty damn good job too. Edit: by the way, I guess I haven't really commenting on TinyVM one way or the other when I responded to you. You're absolutely right and the compatibility is not necessary at all. I think the register count limitation especially is just silly. I pointed out in a different thread that they could double their register count and they'd still fit in a single cache line... they even already have a naming convention (r08-r15) they can hijack.
- Someone 15y ago
  If you can map all VM registers to CPU registers, the interpreter will be way simpler. If you have more VM registers than CPU registers, you have to write code to load and store your VM registers. If you have more CPU registers than VM registers, you will have to write code to undo some of the register spilling done by the compiler (if you want your VM to use the hardware to the fullest.) So, the optimum (from a viewpoint of 'makes implementation easier') depends on the target architecture. Of course, a generic VM cannot know how many registers (and what kinds; uniform register files are not universally present) the target CPU will have. That is a reason that choosing either zero (i.e. a stack machine) or infinitely many (i.e. SSA) are popular choices fo VMs: for the first, you know for sure your target will not have fewer registers than your VM, for the second, that it will not have more. If you choose any other number of VM registers, a fast generic VM will have to handle both cases. Alternatively, of course, one can target a specific architecture, and have the VM be fairly close to the target; Google's NaCl is (was? I think they changed things a bit) an extreme example. I have not checked the code, but this, I think, is similar.

maaku 15y ago

This appears to be very heavily influenced by x86. Why would a VM built in 2011 use an ISA stuck in the 80's? EDIT: I'm not trolling, I'm seriously wondering. There's plenty of literature out there on the advantages of three-operand instructions, large register spaces, and RISC-type instructions. Was there a reason that x86 was used as a basis?

aninteger 15y ago
I'm not the author but I guess there would be a few reasons: 1. Familiarity with x86 assembly. It's probably the assembly language that the majority of people who write assembly language know. 6502 probably being 2nd place 2. Easier to port small x86 assembly programs 3. Even if it's stuck in the 80's it's the most widely used assembly language and there are dedicated online communities of people still writing x86 asm today in 2011.
- xyzzyz 15y ago
  2. Easier to port small x86 assembly programs I seriously doubt that people will do it. If people write assembly, they mostly do it either because of speed, or because it's impossible to do in any other way. None of the reason is relevant in context of VM assembly, which is usually meant to be a compiler's target.
  - carbonica 15y ago
    Yeah - the vast majority of x86 assembly written today is written to take advantage of specialized instructions that aren't available in this VM.
carbonica 15y ago
The instruction set is vastly simpler than x86, but it does inherit some limitations for no reason. x86 had 8 named registers for so long because the mod_rm byte in x86 only has 3 bits for each operand. Adding the REX prefix byte in x86=64 complicates things a bit, but isn't too tough. This VM doesn't have a particularly compact in-memory encoding - it uses an entire `int` for each argument! They could double the number of registers and the entire register set would fit in a cache line (except for EIP) at 4 bytes apiece. I guess it is nice that all 9 fit in one line now, but I doubt that was considered.

diminish 15y ago

i ll make a de-pull request, to remove more.

swah 15y ago
I enjoyed your comment, but will downvote you because I was downvoted when doing similar jokes.

RodgerTheGreat 15y ago

If you find TinyVM interesting, one of my own projects might be worth checking out: https://github.com/JohnEarnest/Mako/blob/master/MakoVM.java https://github.com/JohnEarnest/Mako/blob/master/MakoVM.java It's a stack-oriented VM, similarly designed to be as simple as possible, but my goal was to create something like an idealized game console. Thus, I have basic graphics support and gamepad input. The project includes a compiler for a dialect of Forth and a big pile of example code.

chrisb 15y ago
In a slightly similar vein, you might enjoy looking at my Dot Net Anywhere project: https://github.com/chrisdunelm/DotNetAnywhere/tree/master/dna https://github.com/chrisdunelm/DotNetAnywhere/tree/master/dn... (or http://www.dotnetanywhere.org http://www.dotnetanywhere.org for an easy to use zip download that will load and compile directly on Windows) It is an almost complete .NET2.0 CIL interpreter, so it can run your exe's compiled from C#/VB/etc... I'm not sure it has much practical application, but it was certainly fun to write, and I learnt a huge amount about interpreters and how .NET works. PS Lots of bugs, a memory leak, an incomplete base class library, etc... so don't try to use this for anything serious!

DanielHimmelein 15y ago

Some more resources about virtual machines and a little TinyVM overview: http://himmele.blogspot.com/2011/08/virtual-machines.html http://himmele.blogspot.com/2011/08/virtual-machines.html

deleted 15y ago

[deleted]

hiker 15y ago

Is this solving the same problem that LLVM has solved already better (by supporting both interpretation and JIT)?

spitfire 15y ago

It's nice to see the huge if/then waterfall has been replaced with a switch statement. That was quite the code smell there. I'm still as impressed as when I first saw it. Small, simple and elegant. Neat little project.

parbo 15y ago

If you want to program a VM and have some fun at the same time, do the 2006 ICFP contest: http://www.boundvariable.org/task.shtml http://www.boundvariable.org/task.shtml You have to implement a VM and run the provided program. This will give you access to the actual problem set.