Re: Register versus stack based VMs

[David Olofson <david@...>]

On Sunday 09 December 2007, Duck wrote:
[...]
> I can see why "registers better than stack" for most modern CPUs and 
> chipsets...
> 
> ...but would someone like to explain why this holds for bytecode
> VMs?
[...]

Register based machines - virtual or real - tend to need fewer 
instructions to get the job done, than do stack based machines. As 
the instructions can access registers explicitly, no extra 
instructions are needed to get things in the right place before 
each "real" instruction.

There *is* indeed more logic "inside" each instruction in a register 
based design, but hardware does that in parallel, and in the VM case, 
that logic is a lot faster than using extra VM instructions.

What probably makes this matter even more to VMs than to hardware is 
that a bytecode VM has rather high instruction decoding overhead. 
About 99% of the instructions decoded cause a branch misprediction 
for a switch() based VM. (Your average CPU actually only has a chance 
of getting it right when you use the exact same instruction several 
times in a row.) The figure is about 50% for computed gotos, which is 
still pretty bad news on a modern CPU.

So, for speed, we need to reduce the number of VM instructions needed 
to get the job done, and switching from stack based to register based 
is one way of doing that.

Another way is to go "extreme CISC"; ie have lots of smart 
instructions with many operands. One way of doing that is by merging 
commonly used sequences of VM instructions into "macro" instructions. 
The next step is doing that "live", based on code analysis - though 
that borders to JIT, obviously. This could have some advantages over 
JIT, though... But let's not go there now! :-D


//David Olofson - Programmer, Composer, Open Source Advocate

.-------  http://olofson.net - Games, SDL examples  -------.
|        http://zeespace.net - 2.5D rendering engine       |
|       http://audiality.org - Music/audio engine          |
|     http://eel.olofson.net - Real time scripting         |
'--  http://www.reologica.se - Rheology instrumentation  --'