4 ms·

To be fair, just about all of the most widely used bytecode VMs are stack-based. The JVM, CLR, CPython and YARV are all stack based. You're basically describing

To be fair, just about all of the most widely used bytecode VMs are stack-based. The JVM, CLR, CPython and YARV are all stack based. You're basically describing the exceptions

wolfgke 9y ago
> To be fair, just about all of the most widely used bytecode VMs are stack-based. The JVM, CLR, CPython and YARV are all stack based. You're basically describing the exceptions Be very cautious with this kind of statement. Dalvik (that is used on Android), LLVM (Low Level Virtual Machine) and Erlang's virtual machine are also register-based (I just forgot about them when writing the above post). So I would rather claim it is a 50-50. I could write something about the advantages and disadvantages of both approaches (stack-based vs register-based), but this would become off-topic.
- exikyut 9y ago
  > I could write something about the advantages and disadvantages of both approaches (stack-based vs register-based), but this would become off-topic. But still very interesting. And this subthread has been discussing Forth, so I argue that at least an overview discussion isn't out of order. As I understand it, stack-based software and hardware architectures have been shown to have poor performance when compared to traditional register-based approaches (I specifically read somewhere that even hardware has been shown to be suboptimal, but I unfortunately don't remember where, and the source didn't qualify if the stack architecture in question was pipelined or had other enhancements or if it was just a dumb basic 70s/80s design). In any case, modern (pipelined) register hardware doesn't particularly like the L1/L2/Letc thrashing that stack dancing creates. Obviously with registers you have a bunch of switches that have theoretically O(0) access time regardless of execution machine state. At least that's how I mentally model it, at least superficially; I presume 0 becomes 0.nnnnnnnn for fluctuating values of nnnn depending on pipeline filled-ness and other implementation details. (And I use floating-point here just as an aesthetic representation of hard-to-quantify derivations from theoretical perfect efficiency.) I feel like there's gotta be some kind of cool middle ground between stack-like architectures and register architectures that nobody's found yet, but I do wonder if I'm just barking up an impossible tree. Or is there any research being done in these areas? The main problem I see with stack architectures is that it's effectively impossible to optimize (ie build a pipeline) for. Because if all you're dealing with is the top $however_many_things_the_current_word_pops_and_pushes items on the stack (which, to clarify, the hardware can't even know because that information is locked away in the implementation of the currently-executing word), well... you're in an impossible situation. For want of a better way to express it, the attention span of the implementation is inefficiently small. Anyway, this is some of how I see it. What are your thoughts?
  - wolfgke 9y ago
    > > I could write something about the advantages and disadvantages of both approaches (stack-based vs register-based), but this would become off-topic. > But still very interesting. And this subthread has been discussing Forth, so I argue that at least an overview discussion isn't out of order. I think this whole topic is more complicated than the points you gave. I start with an example: The JVM takes the stack-based instructions and JIT-compiles (in principle AOT-compiling is also possible) them into (register-based) native instructions of the CPU. For this of course lots of transformations etc. have to be done. So executing the stack-based VM instructions naively one after each other fits the CPU badly, but this does not matter - thanks to modern JIT compilers, which transform the code completely. One clear advantage of stack-based VM instruction sets is that there are much less "parameters to decide about". If you work register-based: - How many registers? 8? 16? 32? 256 (i.e. a large number that can nevertheless be reached by real, though artificial programs)? "Near infinite" (say 2^31 or 2^32)? - What register sizes? ARM has only 32 bit (and in AArch64 64 bit) integer registers. x86 has 8, 16, 32 and 64 bit registers. - Should one allow to interprete the lower bits of some large register as a smaller one? What shall happen if we load some constant into such a subregister: Will the upper bits be unchanged (if done on a real CPU this can lead to a pipeline stall), zero-extended or sign-extended? - What about floating point registers: Should one be able to interprete them as integers (encouraged on SSE/AVX (x86), but dicouraged on ARM)? - If we consider SIMD registers to be useful: What size? - Do we want 2-operand or 3-operand instructions: 2-operand instructions have the advantage that the graph coloring problem that is used for allocating CPU registers can be solved in polynomial time, since the graph is chordal. This is also (before AVX) the preferred instruction format for x86. 3-operand instructions have the disadvantage that the graph coloring problem is NP-hard so that in practise often heuristics are used. 3-operand instructions are common on RISC and RISC-inspired processors (e.g. ARM A32, A64 instruction set; note however that I think T32 uses 2-operand instructions). As I pointed out this really large design space forces you to make lots of inconvenient decisions. I think this was a problem of Parrot VM who introduced lots and lots of different instructions to their VM. So if you want to keep the VM portable over lots of architectures, a stack-based approach is more convenient (I don't claim "better"). This was - I believe - one reason why the Java Bytecode was designed stack-based. On the other hand, if you do it the right way, register-based code tends to be be more compact and is simpler to transform into machine code. These are surely central reasons why a register-based implementation was chosen for Dalvik (Android) and the Lua VM. On the other hand to run stack-based code fast, you typically have to do a lot more transformations to the code - which one would love to avoid, in particular for embedded/small systems. So in some sense one can argue that a register-instruction based VM is the more low-level approach for designing VMs - much more decisions to do (which are the best one tend to depend on the primary CPUs that you want to target), but less code transformations to do in the runtime.
- monocasa 9y ago
  I said non-native, sort of thinking of LLVM. And to be fair, Dalvik bytecode is compiled from JVM bytecode, so a stack based language was used as an IR in that language stack.

To be fair, just about all of the most widely used bytecode VMs are stack-based. The JVM, CLR, CPython and YARV are all stack based. You're basically describing the exceptions

wolfgke 9y ago

> To be fair, just about all of the most widely used bytecode VMs are stack-based. The JVM, CLR, CPython and YARV are all stack based. You're basically describing the exceptions Be very cautious with this kind of statement. Dalvik (that is used on Android), LLVM (Low Level Virtual Machine) and Erlang's virtual machine are also register-based (I just forgot about them when writing the above post). So I would rather claim it is a 50-50. I could write something about the advantages and disadvantages of both approaches (stack-based vs register-based), but this would become off-topic.

exikyut 9y ago
> I could write something about the advantages and disadvantages of both approaches (stack-based vs register-based), but this would become off-topic. But still very interesting. And this subthread has been discussing Forth, so I argue that at least an overview discussion isn't out of order. As I understand it, stack-based software and hardware architectures have been shown to have poor performance when compared to traditional register-based approaches (I specifically read somewhere that even hardware has been shown to be suboptimal, but I unfortunately don't remember where, and the source didn't qualify if the stack architecture in question was pipelined or had other enhancements or if it was just a dumb basic 70s/80s design). In any case, modern (pipelined) register hardware doesn't particularly like the L1/L2/Letc thrashing that stack dancing creates. Obviously with registers you have a bunch of switches that have theoretically O(0) access time regardless of execution machine state. At least that's how I mentally model it, at least superficially; I presume 0 becomes 0.nnnnnnnn for fluctuating values of nnnn depending on pipeline filled-ness and other implementation details. (And I use floating-point here just as an aesthetic representation of hard-to-quantify derivations from theoretical perfect efficiency.) I feel like there's gotta be some kind of cool middle ground between stack-like architectures and register architectures that nobody's found yet, but I do wonder if I'm just barking up an impossible tree. Or is there any research being done in these areas? The main problem I see with stack architectures is that it's effectively impossible to optimize (ie build a pipeline) for. Because if all you're dealing with is the top $however_many_things_the_current_word_pops_and_pushes items on the stack (which, to clarify, the hardware can't even know because that information is locked away in the implementation of the currently-executing word), well... you're in an impossible situation. For want of a better way to express it, the attention span of the implementation is inefficiently small. Anyway, this is some of how I see it. What are your thoughts?
- wolfgke 9y ago
  > > I could write something about the advantages and disadvantages of both approaches (stack-based vs register-based), but this would become off-topic. > But still very interesting. And this subthread has been discussing Forth, so I argue that at least an overview discussion isn't out of order. I think this whole topic is more complicated than the points you gave. I start with an example: The JVM takes the stack-based instructions and JIT-compiles (in principle AOT-compiling is also possible) them into (register-based) native instructions of the CPU. For this of course lots of transformations etc. have to be done. So executing the stack-based VM instructions naively one after each other fits the CPU badly, but this does not matter - thanks to modern JIT compilers, which transform the code completely. One clear advantage of stack-based VM instruction sets is that there are much less "parameters to decide about". If you work register-based: - How many registers? 8? 16? 32? 256 (i.e. a large number that can nevertheless be reached by real, though artificial programs)? "Near infinite" (say 2^31 or 2^32)? - What register sizes? ARM has only 32 bit (and in AArch64 64 bit) integer registers. x86 has 8, 16, 32 and 64 bit registers. - Should one allow to interprete the lower bits of some large register as a smaller one? What shall happen if we load some constant into such a subregister: Will the upper bits be unchanged (if done on a real CPU this can lead to a pipeline stall), zero-extended or sign-extended? - What about floating point registers: Should one be able to interprete them as integers (encouraged on SSE/AVX (x86), but dicouraged on ARM)? - If we consider SIMD registers to be useful: What size? - Do we want 2-operand or 3-operand instructions: 2-operand instructions have the advantage that the graph coloring problem that is used for allocating CPU registers can be solved in polynomial time, since the graph is chordal. This is also (before AVX) the preferred instruction format for x86. 3-operand instructions have the disadvantage that the graph coloring problem is NP-hard so that in practise often heuristics are used. 3-operand instructions are common on RISC and RISC-inspired processors (e.g. ARM A32, A64 instruction set; note however that I think T32 uses 2-operand instructions). As I pointed out this really large design space forces you to make lots of inconvenient decisions. I think this was a problem of Parrot VM who introduced lots and lots of different instructions to their VM. So if you want to keep the VM portable over lots of architectures, a stack-based approach is more convenient (I don't claim "better"). This was - I believe - one reason why the Java Bytecode was designed stack-based. On the other hand, if you do it the right way, register-based code tends to be be more compact and is simpler to transform into machine code. These are surely central reasons why a register-based implementation was chosen for Dalvik (Android) and the Lua VM. On the other hand to run stack-based code fast, you typically have to do a lot more transformations to the code - which one would love to avoid, in particular for embedded/small systems. So in some sense one can argue that a register-instruction based VM is the more low-level approach for designing VMs - much more decisions to do (which are the best one tend to depend on the primary CPUs that you want to target), but less code transformations to do in the runtime.
monocasa 9y ago
I said non-native, sort of thinking of LLVM. And to be fair, Dalvik bytecode is compiled from JVM bytecode, so a stack based language was used as an IR in that language stack.