15
$\begingroup$

What are the pros and cons of choosing a register or stack based VM for a language implementation?

For example Python has stack-based virtual machine, while Lua has register-based VM.

What makes a language suitable for one or another representation? Stack VMs for example usually have value-swapping operations which are required for functions that involve more than a couple of values. Does this make them less optimized for algorithms that involve many values?

OTOH, the stack is (at least apparently) infinite, while there are usually a finite amount of registers, requiring the move of values to heap (or ironically, a stack).

$\endgroup$
2
  • $\begingroup$ Good question! :) $\endgroup$ Jun 9, 2023 at 7:23
  • 1
    $\begingroup$ Since stack VM's underlie the JVM, the .NET CIL, Forth and Factor, I know that stack-based VM's are efficient, well-tested, and a good foundation. In addition, the simplicity assists optimization. No time now for a real answer. $\endgroup$ Jul 11, 2023 at 1:09

3 Answers 3

11
$\begingroup$

Register VMs actually store their virtual registers in the heap. They do use a stack after all! This is a common source of confusion, because it's natural to assume that that if one kind of VM is called a stack VM, the other kind must not use a stack.

The difference between the two VM models has to do with how they represent their instruction set (bytecodes). In a stack VM, the arguments to operations are always taken from the top of the stack, and the results are always placed back on the top of the stack. For example, to compute x=10+(x+20) a typical stack VM might use the following instructions: NUMBER pushes a constant to the top of the stack. LOAD fetches a local variable and pushes it to the top of the stack. ADD pops two numbers from the top and pushes their sum. STORE pops the top of the stack and sets the value of a local variable.

NUMBER 10
LOAD "x"
NUMBER 20
ADD
ADD
STORE "x"

In a register VM, we have a stack frame where the lower-numbered slots are for local variables and the higher-numbered slots are for temporary values. The instructions can read and write to any stack slot, which means that they must encode both the operation name and the slot numbers. NUMBER r2 10 says to store the number 10 in the second slot of the stack frame. ADD ra rb rc means take the sum of the rb and rc stack slots and store the result in the ra stack slot. We don't need LOAD or STORE instructions, because the ADD and NUMBER instructions can directly reference the stack slot for the local variable. In the program below, the x variable lives in stack slot r1.

NUMBER r2 10
NUMBER r3 20
ADD r3 r1 r3
ADD r1 r2 r3

Stack machine pros: They're simpler than a register VM. The individual instructions and the total size of the bytecode program is smaller. This is extra important if you're sending programs over the network.

Register machine pros: Although the instructions themselves are larger, they might need fewer instructions overall. That might lead to faster execution times, because of fewer iterations of the instruction-dispatch loop.


For a more in-depth comparison a good starting point is the work of Shi et al[1], and Shi's PhD thesis[2]. In their experiment they compared a register VM to a stack VM and found that the register VM programs were 26% larger, but executed 46% fewer instructions.

[1] Yunhe Shi, Kevin Casey, M. Anton Ertl, and David Gregg. 2008. Virtual machine showdown: Stack versus registers. ACM Trans. Archit. Code Optim. https://doi.org/10.1145/1328195.1328197

[2] Yunhe Shi, 'Virtual machine showdown: stack versus registers', Trinity College (Dublin, Ireland). School of Computer Science & Statistics, 2007. http://www.tara.tcd.ie/handle/2262/77662

$\endgroup$
3
  • $\begingroup$ Is the number of registers available in a register-based VM open ended such that no register allocation would be required? Register allocation would represent a complicated design. $\endgroup$ Nov 23, 2023 at 11:56
  • 1
    $\begingroup$ Usually it's a big enough number (e.g. Lua has 256 registers) $\endgroup$
    – hugomg
    Nov 23, 2023 at 13:11
  • $\begingroup$ A couple of relevant Youtube videos from someone who investigated the performance consequences in depth for a personal language implementation: why my scripting language is already faster than python and are stack based vms really slower? $\endgroup$ Nov 24, 2023 at 4:37
5
$\begingroup$

One significant advantage of a stack-based VM that was not mentioned yet is that most instructions in stack VMs do not have arguments, and it allows to use some nice implementation techniques, such as threaded code.

In case if your VM is just an intermediate representation for some further compilation, of course, it's not that important, but can still help if you have some mixed mode execution, with a direct interpretation and a few tiers of JIT for hot spots.

$\endgroup$
2
  • $\begingroup$ Why is threaded code specific to stack VMs? $\endgroup$
    – G. Sliepen
    Nov 22, 2023 at 12:38
  • $\begingroup$ @G.Sliepen because most (if not all) opcodes for a stack VM do not need arguments, so it's very easy to replace them with direct or indirect jumps. For, say, a register VM it's not as easy, for each instruction have arguments that need to be passed somehow. $\endgroup$
    – SK-logic
    Nov 22, 2023 at 16:18
-5
$\begingroup$

Generally speed, if you have program 5 5 add or add 5 5 first one needs to push numbers to stack before applying add, that can be three loops through lookup table. Register based one on other hand is only one loop for add instruction as the arguments can be read directly from code.

Stack is usually simpler to implement and can be easy to reason.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .