Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Advantages of stack-based architecture of the JVM's instruction

Tags:

java

Why the Java virtual machine was designed with no registers to hold intermediate data values? Instead every thing works on stack. is there any specific advantage of having a stack-based architecture instead of register?

like image 399
gpuguy Avatar asked May 09 '12 11:05

gpuguy


People also ask

What is the purpose of stack based architecture?

The use of a stack significantly reduces the required number of processor registers. Stack machines extend push-down automata with additional load/store operations or multiple stacks and hence are Turing-complete.

What is stack based architecture?

The computers which use Stack-based CPU Organization are based on a data structure called a stack. The stack is a list of data words. It uses the Last In First Out (LIFO) access method which is the most popular access method in most of the CPU.

What is a stack based virtual machine?

What's a stack based virtual machine then? It's an abstraction of a computer, that emulates a real machine. Generally it is built as an interpreter of a special bytecode, that translates its in real time for execution on the CPU.

Why JVM is stack based?

The JVM is a stack-based VM where all the arithmetic and logic operations are carried out via push and pop operands and results are stored on the stack. The stack is also the data structure to store methods.


2 Answers

I have to respectfully disagree with the previous answers.

The assumption of existence of an expression stack is no better an assumption than the existence of registers. Typically register machines can't directly execute stack opcodes, and stack machines can't directly execute register opcodes. They have to be mapped.

EJP says "If the host machine has a stack, as they all do, there is nothing to do". This is a false statement. Proposing that all machines have stacks capable of executing computation shows confusion about what a stack machine really is.

  1. A stack based machine has an instruction set with implicit operands on the top of an "expression stack". Not a general purpose stack. A general purpose stack does not a stack machine make. They can save/restore values. All platforms have that. But they can't execute computations.
  2. A register based machine executes typical opcodes with operands that are explicit, virtual registers, encoded in the instruction stream. Those VMs still have general purpose stacks and opcodes to save and restore registers. You can't map stack calculation ops to a data stack. The core instruction set's operands are registers, memory addresses or immediates (encoded within opcode).

So there is certainly more than "nothing to do" to map opcodes of one machine architecture to another. Unless you are on a chip with native Java opcode acceleration, you better not assume that.

I don't argue the point that a stack machine is a good choice for portability. I am saying that there is "something to do" to map instructions from stack-to-register or register-to-stack. Both are possible.

However, a lot of talk is academic. In practice, in 2014, the prevalent platform is register. Even stack based "processors" are often soft chips implemented in top of a register chip. See the Java Card 3 spec and look at the implementations and find out which processors are actually used. I'll leave that as an exercise.

Unless we are designing a VM for a very specific platform (such as we've been asked to design a JVM that will only ever run on a GreenSpaces processor, which I don't see happening), then I assume the context is general application, embedded applications, set top box, firmware controllers, toys, even smart cards. For all these, I see 8-32 bit processors like ARM, either used or available. The mainstream JVM is written in C. C makes it possible to design an interpreter with either virtual stack or virtual register opcodes. In the 90s there was a lot of discussion of stack based Java processors that directly support JVM opcodes. In 2014, we see these implementations on register based hardware, or as supplementary instructions like Jazelle (Java acceleration) on the ARM926EJ-S where there are also registers and support for the ARM instruction set.

For general application, stack based VMs certainly don't map to stacks in practice. These machines all use register based primary instructions; and the stack ops are for saving and restoring registers or call stack, not doing calculations, logic or branching. The stack VMs JIT to the machine's native instruction set, whether it is a stack or register instruction set. Since 1980, virtually every new processor architecture has been register, according to Hennessy And Patterson - "Computer Architecture A Quantitative Approach". That means register-register, register-memory, or register-immediate instruction sets. You can't add 2 values on the stack on a machine that doesn't have a stack based add. On x86, your stack based opcodes for an ADD operation might translate from:

push a
push b
add

to native register code:

mov eax, [addra]
mov ebx, [addrb]
add eax, ebx

Secondly, regardless of whether the opcode stream is stack or register, a JIT can compile it to native code. So the choice of VM model is simply a software model. Register machines are just as virtual. They don't encode any native register information, the registers in the opcodes are virtual symbols.

Now when Java was designed, the thoughts were toward small opcodes and 8-bit processor compatibility. Stack based opcodes are smaller than register opcodes. So it made sense. I'm sure I read somewhere that it was one of the primary reasons that James Gosling chose that for Oak (original name for Java), besides simplicity. I just have no reference a hand. In that, I agree with Péter Török.

  • There are observable benefits to stack opcode. The codestreams are often smaller / denser. Regarding the JVM and CLR, observed stackbased bytecodes can be 15-20% smaller than other machines. Stack bytecodes can be easily encoded in <= 8 bits. (Forth machines can have as few as 20 or so opcodes). The opstream is easier to encode/decode. Try writing an assembler or disassembler for Java then for x86.
  • There are observable benefits to register opcode. Fewer opcodes to encode an expression = better IPC = less high level branching in the interpreter. It can also directly map a small number of registers (8 to 16) to virtually every modern processor. Use of registers achieves much higher throughput due to better cache locality of reference. On the contrary, stack machines use a lot of memory bandwidth.

In VMs, the register bytecodes often use a large virtual register set, requiring larger bytecodes. On most real hardware, registers are typically encoded with approx 3bits (Intel x86) to 5 bits (Sparc), so the density may differ from VM to VM or CPU to CPU or VM to CPU. Dalvik uses 4 to 16 bits to represent registers, whereas Parrot used 8 bits per register on all opcodes (at least the v2 bytecode format I used). Dalvik achieves better average density. Based on my experience with building them, it is hard to build a general purpose register machine within 8 bit bytecode unless you strictly stick to primitives and use a small register file. This may seem unintuitive, but typically a single opcode actually has several encodings with different register types.

One last point: A lot of the soft-core optimization potentially goes out the window when the JIT comes into the picture.

The primary exception I take with argument that stack machines map better to hardware is that it ignores where the JVM runs and/or where technology is heading. Outside of Chuck Moore, I don't know of anyone designing stack based processors (the IGNITE and the GreenSpaces GA144), and most new development is register machine. The arguments for stack machines are predominantly academic. For every 8-bit stack processor argument I can show you several register machines (Hitachi H8 with registers, ARM926 with registers, Intel 8051) with a C compiler. You may be more likely to be writing in Forth on a pure stack processor, than Java. For a new platform, it makes more sense to go with a cheap ARM processor where there are C compilers, full JVM, etc. These run register instruction sets.

  • ARM926 / ARM926EJ-S - http://www.arm.com/products/processors/classic/arm9/arm926.php
  • H8 - http://en.wikipedia.org/wiki/H8_Family

So, if thats true? Does it matter? My opinion, based on my experience, is "not as much as people think". Remember, bytecode is just an intermediate representation. A machine's pure interpreted core is often a stepping stone, a bridge, a default fail-safe core. The final destination is the eventual version 2 with a JITter to native performance. So the point of view held by many who have done it once or twice is that it makes sense to keep the core as simple as possible and move on to the JIT, spending 90% of the optimization there. Any wasted effort tuning the interpeted core could be viewed as premature optimization. If, on the other hand, you don't plan a JITter, or JIT is impractical due to memory constraints, then optimize away on the virtual core, or implement the VM on a chip.

like image 99
codenheim Avatar answered Oct 19 '22 23:10

codenheim


Java was designed to be portable from the ground up. But how can you keep your bytecode portable if it depends on certain registers being present on the platform you are running it on? Especially taking into account that originally it was intended to run (also) on set-top boxes, which have a very different processor architecture from mainstream PCs.

It is only runtime that the JVM actually knows the available registers and other hardware specific stuff. Then the JIT compiler can (and will) optimize for these as applicable.

like image 34
Péter Török Avatar answered Oct 20 '22 01:10

Péter Török