4 ms·

I'd like to see such an article on a register based VM. Pawn and Lua are nice examples. Most VMs are stack based but this is mainly because they are conceptuall

I'd like to see such an article on a register based VM. Pawn and Lua are nice examples. Most VMs are stack based but this is mainly because they are conceptually easier to understand. Register based machines have some real advantages, like requiring far fewer instructions inside tight loops.

bch 12y ago
You can see a project switch from a stack-based VM to a register-based VM here[0] [1]. For [1], search page for "vdbe" (virtual database engine). Hopefully you find interesting things. [0] https://www.sqlite.org/vdbe.html https://www.sqlite.org/vdbe.html [1] http://www.sqlite.org/src/timeline?c=2007-11-11&n=400 http://www.sqlite.org/src/timeline?c=2007-11-11&n=400
ddfreyne 12y ago
I created a register-based VM named RCPU, for educational purposes. You can find it at https://github.com/ddfreyne/rcpu https://github.com/ddfreyne/rcpu. It has most of what you’d expect from a register-based VM, and even has video output (rcpu-assemble samples/video.rcs and then rcpu-emulate the resulting file with --video). I intend to write up my findings, but haven’t gotten around to it yet. I do have slides for a talk for this project though: https://speakerdeck.com/ddfreyne/simulating-a-cpu-with-ruby https://speakerdeck.com/ddfreyne/simulating-a-cpu-with-ruby
voidiac 12y ago
Register based VMs are not more complex than stack based VMs. You can even have a stack and the only difference is that your instructions operate on registers and not directly on the stack. I only consider generating code more complex with a register based VM. If you are interested here is a toy vm I wrote myself: https://github.com/byo3rn/ire https://github.com/byo3rn/ire PS: I suck at documentation.
tptacek 12y ago
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
- crzwdjk 12y ago
  Registers are stored in memory, but ideally "memory" means L1 cache, and it seems to me like register VMs would have better cache locality. This might be why they're getting more popular relative to stack VMs as the speed advantage of cache increases.
  - barrkel 12y ago
    Stack machines are constantly using the same absolute offsets into the stack when evaluating in a loop, or evaluating different branches of a big expression. In fact, one of the simplest register allocators you can use in an expression code generator is a stack; pop to allocate, push to deallocate, and spill if you run out. On a CPU, this will have benefits, but in a VM, it's just a relabeling scheme for the same memory slots a stack VM would use. What you potentially gain with a register VM is reduced accounting overhead; a stack machine will be constantly adjusting the stack pointer on every operation. It's a tradeoff for less complexity at codegen time. It's swings and roundabouts in the lowlands of performance, though; no loop and switch VM will be super-fast.
- userbinator 12y ago
  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.
  - gsg 11y ago
    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 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.
rednovae 12y ago
Not an article, but this is a register-based VM that should be simple and straight-forward to understand. Also comes with an assembler, disassembler and debugger. https://github.com/endeav0r/hsvm https://github.com/endeav0r/hsvm

bch 12y ago

You can see a project switch from a stack-based VM to a register-based VM here[0] [1]. For [1], search page for "vdbe" (virtual database engine). Hopefully you find interesting things. [0] https://www.sqlite.org/vdbe.html https://www.sqlite.org/vdbe.html [1] http://www.sqlite.org/src/timeline?c=2007-11-11&n=400 http://www.sqlite.org/src/timeline?c=2007-11-11&n=400

ddfreyne 12y ago

I created a register-based VM named RCPU, for educational purposes. You can find it at https://github.com/ddfreyne/rcpu https://github.com/ddfreyne/rcpu. It has most of what you’d expect from a register-based VM, and even has video output (rcpu-assemble samples/video.rcs and then rcpu-emulate the resulting file with --video). I intend to write up my findings, but haven’t gotten around to it yet. I do have slides for a talk for this project though: https://speakerdeck.com/ddfreyne/simulating-a-cpu-with-ruby https://speakerdeck.com/ddfreyne/simulating-a-cpu-with-ruby

voidiac 12y ago

Register based VMs are not more complex than stack based VMs. You can even have a stack and the only difference is that your instructions operate on registers and not directly on the stack. I only consider generating code more complex with a register based VM. If you are interested here is a toy vm I wrote myself: https://github.com/byo3rn/ire https://github.com/byo3rn/ire PS: I suck at documentation.

tptacek 12y ago

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

crzwdjk 12y ago
Registers are stored in memory, but ideally "memory" means L1 cache, and it seems to me like register VMs would have better cache locality. This might be why they're getting more popular relative to stack VMs as the speed advantage of cache increases.
- barrkel 12y ago
  Stack machines are constantly using the same absolute offsets into the stack when evaluating in a loop, or evaluating different branches of a big expression. In fact, one of the simplest register allocators you can use in an expression code generator is a stack; pop to allocate, push to deallocate, and spill if you run out. On a CPU, this will have benefits, but in a VM, it's just a relabeling scheme for the same memory slots a stack VM would use. What you potentially gain with a register VM is reduced accounting overhead; a stack machine will be constantly adjusting the stack pointer on every operation. It's a tradeoff for less complexity at codegen time. It's swings and roundabouts in the lowlands of performance, though; no loop and switch VM will be super-fast.
userbinator 12y ago
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.
- gsg 11y ago
  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 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.

rednovae 12y ago

Not an article, but this is a register-based VM that should be simple and straight-forward to understand. Also comes with an assembler, disassembler and debugger. https://github.com/endeav0r/hsvm https://github.com/endeav0r/hsvm