Programming language interpreters represent the executing program as an abstract machine. The major representation for Java is an abstract stack machine called Java bytecodes. The alternative representation is an abstract register machine. This paper is a thorough comparison of the benefits of each representation. It comes to the conclusion that the stack machine is more space efficient, while the register machine provides faster interpretation.

The paper is remarkable. This subject is usually hotly contested, frequently with emotional zeal. The authors implement both representations and perform a careful analysis, taking care to make the comparison as honest as possible.

The abstract stack machine contains instructions that load operands onto an execution stack. The computational and comparison operations take values from the top of the stack and return results on top of the stack. This representation is space efficient, since the operands are not encoded in the individual instructions; however, the representation uses more instructions, since values must be loaded onto the stack before use and redundant expressions elimination is less effective.

The register machine looks much like a modern processor, with each instruction taking register numbers to indicate the registers holding the operands. Each instruction is larger than in the stack machine; however, there are fewer instructions, since most of the load operations can be eliminated.

The difference in interpreter performance can be attributed to the cost of dispatching the instructions for execution and the retrieval of operands from the stack. The paper analyzes a number of different techniques for dispatching instructions, ranging from using a C-style switch statement to machine-dependent techniques that minimize the cost of dispatch. The C-style switch statement is the most costly and gives the register machine the biggest advantage. As the dispatch mechanisms become more efficient, the performance advantage for the register machine decreases.

This is an excellent example of performing a difficult comparison. Shi et al. anticipate the questions that the reader might raise and carefully study them. I expect that some of the results surprised the authors themselves. The paper is well worth reading, both for the information and the comparison methodology.