4 ms·

Then why are stack based VMs so much more common than register based ones? A bit of an appeal to authority here I know, but Eric Lippert felt stack machines we

Then why are stack based VMs so much more common than register based ones? A bit of an appeal to authority here I know, but Eric Lippert felt stack machines were easier to generate code for: A stack machine is a very simple way to describe a complex computation; by being able to write code for such a simple machine, it lowers the cost of making a compiler. And not only is it easier to write compilers and jitters that target simple stack machines, it is easier to write other code analysis tools as well. https://learn.microsoft.com/en-us/archive/blogs/ericlippert/why-have-a-stack https://learn.microsoft.com/en-us/archive/blogs/ericlippert/...

Someone 4y ago
If you aim to ship your VM on machines with varying number of registers, and you pick a VM with R registers, you have to write code to make it run on machines with fewer than R registers and code to make it run on machines with more than R registers. Both are simple if you’re willing to give up performance (map VM registers to memory for the first case, don’t use more than R registers for the second case), but that means giving away a lot of performance. So, you’ll essentially be working on two different optimizers, with each only affecting some of your target CPUs. If, on the other hand, your VM has zero registers, you only have to write the code for running efficiently on machines with more than zero registers. That’s conceptually easier, and (loosely) means every improvement you make will improve things on all target CPUs. Also note that single static assignment as used in LLVM (not really a VM) somewhat uses the opposite approach: it assumes there are infinitely many registers, and then adds code to map that down to whatever is available on the target hardware. Going back to the question: I think stack-based CPUs lost because all their instructions contend on access to the stack, making it hard for the hardware to pipeline instructions and/or execute them out of order.
eatonphil 4y ago
As a hobbyist I agree that generating code for stack machines is much easier than for register machines. Because you get to ignore register allocation entirely! I hate register allocation (implementing it I mean). But it's normally agreed to be less efficient. See Y Shi's 2005 paper Virtual Machine Showdown: > We found that a register architecture requires an average of 47% fewer executed VM instructions, and that the re- sulting register code is 25% larger than the correpsonding stack code. The increased cost of fetching more VM code due to larger code size involves only 1.07% extra real ma- chine loads per VM instruction eliminated. On a Pentium 4 machine, the register machine required 32.3% less time to execute standard benchmarks if dispatch is performed using a C switch statement. Even if more efficient threaded dis- patch is available (which requires labels as first class values), the reduction in running time is still around 26.5% for the register architecture.
- LAC-Tech 4y ago
  Is that the paper where they pop twice for a 2 -- 1 operation?

Someone 4y ago

If you aim to ship your VM on machines with varying number of registers, and you pick a VM with R registers, you have to write code to make it run on machines with fewer than R registers and code to make it run on machines with more than R registers. Both are simple if you’re willing to give up performance (map VM registers to memory for the first case, don’t use more than R registers for the second case), but that means giving away a lot of performance. So, you’ll essentially be working on two different optimizers, with each only affecting some of your target CPUs. If, on the other hand, your VM has zero registers, you only have to write the code for running efficiently on machines with more than zero registers. That’s conceptually easier, and (loosely) means every improvement you make will improve things on all target CPUs. Also note that single static assignment as used in LLVM (not really a VM) somewhat uses the opposite approach: it assumes there are infinitely many registers, and then adds code to map that down to whatever is available on the target hardware. Going back to the question: I think stack-based CPUs lost because all their instructions contend on access to the stack, making it hard for the hardware to pipeline instructions and/or execute them out of order.

eatonphil 4y ago

As a hobbyist I agree that generating code for stack machines is much easier than for register machines. Because you get to ignore register allocation entirely! I hate register allocation (implementing it I mean). But it's normally agreed to be less efficient. See Y Shi's 2005 paper Virtual Machine Showdown: > We found that a register architecture requires an average of 47% fewer executed VM instructions, and that the re- sulting register code is 25% larger than the correpsonding stack code. The increased cost of fetching more VM code due to larger code size involves only 1.07% extra real ma- chine loads per VM instruction eliminated. On a Pentium 4 machine, the register machine required 32.3% less time to execute standard benchmarks if dispatch is performed using a C switch statement. Even if more efficient threaded dis- patch is available (which requires labels as first class values), the reduction in running time is still around 26.5% for the register architecture.

LAC-Tech 4y ago
Is that the paper where they pop twice for a 2 -- 1 operation?