<p>What are the pros and cons of choosing a register or stack based VM for a language implementation?</p>
<p>For example Python has stack-based virtual machine, while Lua has register-based VM.</p>
<p>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?</p>
<p>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).</p>

<stack><virtual-machine><registers>
What are the pros and cons of register-based VMs and stack-based VMs?
CC BY-SA 4.0
2023-06-09T07:23:17.070Z
Good question! :)
чистов_n
CC BY-SA 4.0
2023-07-11T01:09:24.633Z
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.
MicroservicesOnDDD
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-13T12:55:08.920Z
2023-06-13T12:55:08.920Z
SK-logic
CC BY-SA 4.0
2023-11-22T12:38:42.833Z
Why is threaded code specific to stack VMs?
G. Sliepen
CC BY-SA 4.0
2023-11-22T16:18:49.983Z
@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.
SK-logic
<p>Generally speed, if you have program <code>5 5 add</code> or <code>add 5 5</code> 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.</p>
<p>Stack is usually simpler to implement and can be easy to reason.</p>

CC BY-SA 4.0
2023-06-09T05:39:13.187Z
2023-06-09T05:39:13.187Z
Viola
<p>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.</p>
<p>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 <code>x=10+(x+20)</code> 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.</p>
<pre><code>NUMBER 10
LOAD &quot;x&quot;
NUMBER 20
ADD
ADD
STORE &quot;x&quot;
</code></pre>
<p>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. <code>NUMBER r2 10</code> says to store the number 10 in the second slot of the stack frame. <code>ADD ra rb rc</code> 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 <code>x</code> variable lives in stack slot r1.</p>
<pre><code>NUMBER r2 10
NUMBER r3 20
ADD r3 r1 r3
ADD r1 r2 r3
</code></pre>
<p><strong>Stack machine pros</strong>: 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.</p>
<p><strong>Register machine pros</strong>: 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.</p>
<hr />
<p>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.</p>
<p>[1] Yunhe Shi, Kevin Casey, M. Anton Ertl, and David Gregg. 2008. Virtual machine showdown: Stack versus registers. ACM Trans. Archit. Code Optim. <a href="https://doi.org/10.1145/1328195.1328197" rel="noreferrer">https://doi.org/10.1145/1328195.1328197</a></p>
<p>[2] Yunhe Shi, 'Virtual machine showdown: stack versus registers', Trinity College (Dublin, Ireland). School of Computer Science &amp; Statistics, 2007. <a href="http://www.tara.tcd.ie/handle/2262/77662" rel="noreferrer">http://www.tara.tcd.ie/handle/2262/77662</a></p>

CC BY-SA 4.0
2023-06-09T16:40:53.520Z
2023-06-09T17:46:50.403Z
2023-06-09T17:46:50.403Z
hugomg
CC BY-SA 4.0
2023-11-23T11:56:12.153Z
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.
Christian Lindig
CC BY-SA 4.0
2023-11-23T13:11:07.293Z
Usually it's a big enough number (e.g. Lua has 256 registers)
hugomg
CC BY-SA 4.0
2023-11-24T04:37:35.153Z
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](https://www.youtube.com/watch?v=14CPI1qBd7o) and [are stack based vms really slower?](https://www.youtube.com/watch?v=cMMAGIefZuM)
Karl Knechtel
# What are the pros and cons of register-based VMs and stack-based VMs?
Posted by: username_0 on 2023-06-09
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).
**Tags:** stack virtual-machine registers
> **Comments:**
> **username_1**: Good question! :)  
> **username_2**: 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.  
---
## 3 answers
### Answer by username_6 on 2023-06-09. Score: 13 | Accepted answer
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
> **Comments:**
> **username_7** (2023-11-23): 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.  
> **username_6** (2023-11-23): Usually it's a big enough number (e.g. Lua has 256 registers)  
> **username_8** (2023-11-24): 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](https://www.youtube.com/watch?v=14CPI1qBd7o) and [are stack based vms really slower?](https://www.youtube.com/watch?v=cMMAGIefZuM)  
---
### Answer by username_3 on 2023-06-13. Score: 6
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.
> **Comments:**
> **username_4** (2023-11-22): Why is threaded code specific to stack VMs?  
> **username_3** (2023-11-22): @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.  
---
### Answer by username_5 on 2023-06-09. Score: -4
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.
---
