Registers against stacks

Question

What are the advantages and disadvantages of using a registry-based virtual machine compared to using a stack-based virtual machine?

It would seem to me that a register-based machine would be more straightforward for programming and more efficient. So why are all JVMs, CLRs, and Python VMs stack-based?

Answer 1

This has already been answered at a certain level in the Parrot VM FAQ and related documents: Parrot Overview The relevant text from this document is as follows:

Parrot VM will have a register architecture, not a stack architecture. It will also have extremely low-level operations more similar to Java than mid-level Perl and Python operators, etc.

The reason for this decision is primarily that, to some extent, similar to the basic equipment, it is possible to compile Parrot bytecode for an effective native machine language.

In addition, many programs in high-level languages ​​consist of nested calls to functions and methods, sometimes with lexical variables for storing intermediate results. In parameters other than JIT, a stack-based virtual machine will be displayed, and then the same operands will be pressed repeatedly, while a registry-based virtual machine will simply allocate the necessary number of registers and work on them, which can significantly reduce the number of operations and processor time.

You can also read the following: Registers vs stacks for interpreter design I quote a little:

There is no real doubt, it’s easier to generate code for the stack. Most beginner compiler students can do this. Generating code for a registration machine is a bit tougher, unless you see it as a stacked machine with a battery. (This is doable, although somewhat less ideal in terms of performance). The ease of targeting isn’t such a big deal, at least not for me, partly because few people really are going to direct it directly to the target - I mean, come on, how many people do you know who really trying to write a compiler for something, about anything you care about? The rooms are small. Another problem is that many of the people with knowledge of the compiler are already convenient targeting registration systems, as well as the fact that all the used hardware processors are used.

Answer 2

Implemented at the hardware level, a register-based machine will be more efficient, simply because access to slower RAM is less. However, in software, even based on register architecture, there will most likely be “registers” in RAM. In this case, a stack-based machine will be just as efficient.

In addition, a stack-based virtual machine will make it much easier to write compilers. You do not need to deal with register allocation strategies. You have, in fact, an unlimited number of registers to work with.

Update: I wrote this answer assuming an interpreted virtual machine. This may not correspond to the VM JIT compilation. I came across this article , which apparently indicates that a compiled JIT virtual machine can be more efficient using the register architecture.

Answer 3

Traditionally, virtual machine developers prefer stack-based architectures over the registry because of the "ease of VM deployment", the ease of writing a counter-compiler - most virtual machines were originally designed to accommodate a single language and code density and executable files for the stack architecture are invariably less than executables for register architectures. Simplicity and code density is the cost of execution.

Studies have shown that a registered architecture requires an average of 47% less executed VM instructions than a stack-based architecture, and a register code is 25% more than the corresponding stack code, but this increases the cost of receiving additional VM commands to a larger code size only 1.07% of additional real machine downloads per VM instruction, which is negligible. The overall performance of a register-based virtual machine is that there is an average of 32.3% less time to complete standard benchmarks.

Answer 4

One of the reasons for creating virtual machines based on stacks is that the actual VM operation codes can be smaller and simpler (there is no need to encode / decode operands). This makes the generated code smaller and also simplifies the VM code.

Answer 5

How many registers do you need?

I probably need at least one more.

Answer 6

It’s not obvious to me that a register-based virtual machine will be “more straightforward for programming” or “more efficient”. Perhaps you think that virtual registers will provide a short-term reduction during the JIT compilation phase? This, of course, is not so, since a real processor can have more or fewer registers than a virtual machine, and these registers can be used in different ways. (Example: values ​​that will decrease are best placed in the ECX register on x86 processors.) If the real machine has more registers than the virtual machine, then you are wasting resources, less and gaining nothing using "register based".

Answer 7

Virtual virtual machines on the stack are simpler, and the code is much more compact. As an example in the real world, a friend built (about 30 years ago) a data logging system from a homebrew Forth VM on Cosmac. Forth VM was 30 bytes of code on a machine with 2k ROM and 256 bytes of RAM.

Answer 8

For stack-based virtual machines, it is easier to create code for.

In virtual machines with registration, it is easier to create fast implementations and it is easier to generate highly optimized code for.

For your first attempt, I recommend starting with a stack-based virtual machine.