Optimizing direct threaded code by selective inlining.
Achieving good performance in bytecoded language interpreters is difficult without sacrificing both simplicity and portability. This is due to the complexity of dynamic translation ("just-in-time compilation") of bytecodes into native code, which is the mechanism employed universally by high-performance interpreters.We demonstrate that a few simple techniques make it possible to create highly-portable dynamic translators that can attain as much as 70% the performance of optimized C for certain numerical computations. Translators based on such techniques can offer respectable performance without sacrificing either the simplicity or portability of much slower "pure" bytecode interpreters.
Introduction
Bytecoded languages such as Smalltalk [Gol83], Caml
[Ler97] and Java [Arn96, Lin97] offer significant engineering
advantages over more conventional languages: higher
levels of abstraction, dynamic execution environments with
incremental debugging and code modification, compact representation
of executable code, and (in most cases) platform
independence.
The success of Java is due largely to its promise of platform
independence and compactness of code. The compactness
of bytecodes has important advantages for net-work
computing where code must downloaded "on-demand"
for execution on an arbitrary platform and operating system
while keeping bandwidth requirements to a minimum.
The disadvantage is that bytecode interpreters typically offer
lower performance than compiled code, and can consume
significantly more resources.
Most modern virtual machines perform some degree of
dynamic translation to improve program performance
[Deu84]. Such techniques significantly increase the complexity
of the virtual machine, which must be tailored for
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage
and that copies bear this notice and the full citation on the first page.
To copy otherwise, to republish, to post on servers or to
redistribute to lists, requires prior specific permission and/or a fee.
SIGPLAN '98 Montreal Canada
c
each hardware architecture in much the same way as a conventional
compiler's back-end. This increases development
costs (requiring specific knowledge about the target architecture
and the time for writing specific code), and reduces
reliability (by introducing more code to debug and support).
Some of these languages (Caml for example) also have
more traditional compilers that produce high-performance
native code, but this defeats the advantages that come with
platform independence and compactness.
We propose a novel dynamic retranslation technique that
can be applied to a certain class of virtual machines. This
technique delivers high performance, up to 70% that of optimized
C. It is easy to "retrofit" to existing virtual machines,
and requires almost no effort to port to a new architecture.
This paper continues as follows. The next section gives
a brief survey of bytecode interpretation mechanisms, providing
a context for the remainder of the paper. Our novel
dynamic retranslation technique is explained in Section 3.
Section 4 presents the results of applying the technique to
two interpreters: the small RISC-like interpreter that inspired
this work, and a "production" virtual machine for
Objective Caml. The last two sections contrast our technique
with related work and present some concluding remarks

Background
Interpreter performance can depend heavily on the representation
chosen for executable code, and the mechanism
used to dispatch opcodes. This section describes some of
the common techniques.
2.1 Pure bytecode interpreters
The inner loop of a pure bytecode interpreter is very simple:
fetch the next bytecode and dispatch to the implementation
using a switch statement. Figure 1 shows a typical pure
bytecode interpreter loop, and an array of bytecodes that
calculate will use this as a running example).
The interpreter is an infinite loop containing a switch
statement to dispatch successive bytecodes. Each case in
the body of the switch implements one bytecode, and passes
control to the next bytecode by breaking out of the switch
to pass control back to the start of the infinite loop.
Assuming the compiler optimizes the jump chains from
the breaks through the implicit jump at the end of the for
body back to its beginning, the overheads associated with
this approach are as follows:
compiled code:
unsigned char
bytecode-add, . -;
bytecode implementations:
unsigned char
for
unsigned char
switch (bytecode) -
case bytecode-push3:
break;
case bytecode-push4:
break;
case bytecode-add:
*stackPointer += stackPointer[1];
break;

Figure

1: Pure bytecode interpreter.
ffl increment the instructionPointer;
ffl fetch the next bytecode from memory;
ffl a redundant range check on the argument to switch;
ffl fetch the address of the destination case label from a
table;
ffl jump to that address;
and then at the end of each bytecode:
ffl jump back to the start of the for body to fetch the
next bytecode.
Eleven machine instructions must be executed on the PowerPC
to perform the push3 bytecode. Nine of these instructions
are dedicated to the dispatch mechanism, including
two memory references and two jumps (among the most expensive
instructions on modern architectures).
Pure bytecoded interpreters are easy to write and under-
stand, and are highly portable - but rather slow. In the
case where most bytecodes perform simple operations (as in
the push3 example) the majority of execution time is wasted
in performing the dispatch.
2.2 Threaded code interpreters
Threaded code [Bel73] was popularized by the Forth programming
language [Moo70]. There are various kinds of
threaded code, the most efficient of which is generally direct
threading [Ert93].
Bytecodes are simply integers: dispatch involves fetching
the next opcode (bytecode), looking up the address of
the associated implementation (either in an explicit table,
or implicitly using switch) and then transferring control to
that address. Direct threaded code improves performance
by eliminating this table lookup: executable code is represented
as a sequence of opcode implementation addresses,
and dispatch involves fetching the next opcode (implemen-
tation address) and jumping directly to that address.
An additional optimization eliminates the centralized dis-
patch. Instead of returning to a central dispatch loop, each
compiled code:
void
&&opcode-add, . -;
opcode implementations:
dispatch next instruction */
#define NEXT() goto *++instructionPointer
void
/* start execution: dispatch first opcode */
/* opcode implementations. */
opcode-push3:
opcode-push4:
opcode-add:
*stackPointer += stackPointer[1];

Figure

2: Direct threaded code.
direct threaded opcode's implementation ends with the code
required to dispatch the next opcode. The direct threaded
version of our '3 example is shown in Figure 2. 1
Execution begins by fetching the address of the first op-
code's implementation from the compiled code and then
jumping to that address. Each opcode performs its own
work, and then dispatches to the next opcode implied by
the compiled code. (Hence the name: control flow "threads"
its way through the opcodes in the order implied by the
compiled code, without ever returning to a central dispatch
loop.)
The overheads associated with threaded code are much
lower than those associated with a pure bytecode inter-
preter. For each opcode executed, the only additional overhead
is dispatching to the next opcode:
ffl increment the instructionPointer;
ffl fetch the next opcode address from memory;
ffl jump to that address.
Five machine instructions are required to implement push3
on the PowerPC. Three of these are associated with opcode
dispatch, with only one memory reference and one jump.
We have saved six instructions over the "pure bytecode"
approach. Most importantly we have saved one memory
reference and one jump instruction (both of which are ex-
pensive).
2.3 Dynamic translation to threaded code
The benefits of direct threaded code can easily be obtained
in a bytecoded language by translating the bytecodes into
1 The threaded code examples are written using the first-class labels
provided by GNU C. The expression "void assigns
the address (of type "void *") of the statement attached to the
given label to addr. Control can be transferred to this location using
a goto that dereferences the address: "goto *addr". Note that gcc's
first-class labels are not required to implement these techniques: the
same effects can be achieved with a couple of macros containing a few
lines of asm.
translation table:
void *opcodes[];
dynamic translator:
unsigned char *bytecodePointer = firstBytecode;
void
while (moreBytecodesToTranslate)

Figure

3: Dynamic translation of bytecodes into threaded
code.
direct threaded code before execution. This is illustrated in

Figure

3. The translation loop reads each bytecode, looks
up the address of its implementation in a table, and then
writes this address into the direct threaded code.
The only complication is that most bytecode sets have
extension bytes. These provide additional information that
cannot be encoded within the bytecode itself: branch offsets,
indices into literal tables or environments, and so on. These
extension bytes are normally placed inline in the translated
threaded code by the translator, immediately after the threaded
opcode corresponding to the bytecode.
Translation to threaded code permits other kinds of op-
timization. For example, Smalltalk provides four bytecodes
for pushing an implicit integer constant (between -1 and
onto the stack. The translator loop could easily translate
these as a single pushInteger opcode followed by the
constant to be pushed as an inline operand. The same treatment
can be applied to other kinds of literal quantity, relative
branch offsets, and so on. Another possibility is "partial
decoding", where the translator loop examines an "over-
loaded" bytecode at translation time, and translates it into
one of several threaded opcodes.
The translator loop must be aware of the kind of operand
that it is copying. A relative offset, for example, might
require modification or scaling during the translation loop.
It is possible to make an approximate evaluation of this
approach in a realistic system. Squeak [Ing97] is a portable
"pure bytecode" implementation of Smalltalk-80; it performs
numerical computations at approximately 3.7% the
speed of optimized C. BrouHaHa [Mir87] is a portable Smalltalk
virtual machine that is very similar to the Squeak VM,
except that it dynamically translates bytecodes into direct
threaded code for execution [Mir91]. BrouHaHa performs
the same numerical computations at about 15% the speed
of optimized C. Both implementations have been carefully
hand-tuned for performance; the essential difference between
them is the use of dynamic translation to direct threaded
code in BrouHaHa.
2.4 Optimizing common bytecode sequences
Bytecodes can typically only represent Threaded
opcodes can represent many more, since they are encoded
as pointers. Translating bytecodes into threaded code
therefore gives us the opportunity to make arbitrary transformations
on the executable code. One such transformation
is to detect common sequences of bytecodes and translate
them as a single threaded "macro" opcode; this macro op-code
performs the work of the entire sequence of original
bytecodes. For example, the bytecodes "push literal, push
variable, add, store variable" can be translated into a single
"add-literal-to-variable" opcode in the threaded code.
Such optimizations are effective because they avoid the
overhead of the multiple dispatches that are implied by the
original bytecodes (but elided within the macro opcode).
A single macro opcode that is translated from a sequence
of N original bytecodes avoids dispatches at
execution time.
This technique is particularly important in cases where
the bytecodes are simple (as in the '3
the implementation of each bytecode can be as short as
a single register-register machine instruction. The cost of
threading can often be significantly larger than the cost of
"useful" execution. If three instructions must be executed to
dispatch to the next opcode then the overhead for this threading
instructions executed
and 12 instructions for dispatching the threaded opcodes).
This overhead drops to 43% when the operation is optimized
into a single macro opcode (four useful instructions and 3
instructions for threading). 2
Dispatching to opcode implementations at non-contiguous
addresses also undermines code locality, causing un-necessary
processor pipeline stalls and inefficient utilization
of the instruction cache and TLBs. Combining common sequences
of bytecodes into a single macro opcode considerably
reduces these effects. The compiler will also have a chance to
make inter-bytecode optimizations (within the implementation
of the single macro opcode) that are impossible to make
between the implementations of the individual bytecodes.
Determining an appropriate set of common bytecode sequences
is not difficult. The virtual machine can be instrumented
to record execution traces, and a simple offline analysis
will reveal the likely candidates. The corresponding pattern
matching and macro opcode implementations can then
be incorporated manually into the VM. For example, such
analysis has been applied to an earlier version of the Objective
Caml bytecode set, resulting in a new set of bytecodes
that includes several "macro-style" operations.
2.5 Problems with static optimization
The most significant problem with this static approach
is that the number of possible permutations of even the
shortest common sequences of consecutive bytecodes is pro-
hibitive. For example, Smalltalk provides 4 bytecodes to
push the most popular integer constants (minus one through
two), and bytecodes to load and store 32 temporary and 256
"receiver" variables. Manually optimizing the possible permutations
for incrementing and decrementing a variable by
a small constant would require the translator to implement
2304 explicit special cases. This is clearly unreasonable.
The problem is made more acute since different applications
running on the same virtual machine will favor different
sequences of bytecodes. Statically chosing a single
"optimal" set of common sequences is therefore impossible.
Our technique focuses on making this choice at runtime,
which allows the set of common sequences to be nearly optimal
for the particular application being run.
"Instruction counting" is not a very accurate way to estimate the
savings, since the instructions that we avoid are some of the most
expensive to execute.
dynamic-opcode-push3-push4-add:
stackPointer-;
*stackPointer += stackPointer[1];
goto

Figure

4: Equivalent macro opcode for push3, push4, add.
int nfibs(int n)
return (n ! 2)

Figure

5: Benchmark function in C.
Dynamically rewriting opcode sequences
We generate implementations for common bytecode sequences
dynamically. These implementations are available as
new macro opcodes, where a single such macro opcode replaces
the several threaded opcodes generated from the original
common bytecode sequence. These dynamically generated
macro opcodes are executed in precisely the same
manner as the interpreter's predefined opcodes; the original
execution mechanism (direct threading) requires no modification
at all. The transformation can be performed either
during bytecode-to-threaded code translation, or as a separate
pass over already threaded code.

Figure

4 shows the equivalent C for a dynamically generated
threaded opcode for the sequence of three bytecodes
needed to evaluate the '3 + 4' example.
The translator concatenates the compiled C implementations
for several intrinsic threaded opcodes, each one corresponding
to a bytecode in the sequence being optimized.
Since this involves relocating code, it is only safe to perform
this concatenation for threaded opcodes whose implementation
is position independent. In general there are three cases
to consider when concatenating opcode implementations:
ffl A threaded opcode cannot be inlined if its implementation
contains a call to a C function, where the destination
address is relative to the processor's PC. Such
destination addresses would be invalidated as they are
copied to form the new macro opcode's implementation

ffl Any threaded opcode that changes the flow of control
through the threaded code must only appear at the
end of a translated sequence. This is because different
paths through the sequence might consume different
numbers of inline arguments.
ffl Any threaded opcode that is a branch destination can
only appear at the beginning of a macro opcode, since
incorporating it into the middle of a macro opcode
would delete the branch destination in the final threaded
code.
The above can be simplified to the following rule: we
only consider basic blocks for inlining, where a basic block
begins with a jump destination and ends with either a jump
nfibs: push r1 ; r1 saved during call
move
jge r0 r1 @
=cont
pop r1 ; restore r1
return
cont: move r0 r1 ; else arg -? r1
call @
=nfibs
call @
=nfibs
add
add
pop r1 ; restore r1
return
start: move #32 r0 ; call nfibs(32)
call @
=nfibs
print

Figure

Threaded code for nfibs benchmark, before inlining.
destination or a change of control flow. For inlining pur-
poses, opcodes that contain a C function call are considered
to be single-opcode basic blocks. (This restriction can be
relaxed if the target architecture and/or the compiler used
to build the VM uses absolute addresses for function call
destinations.)
Our technique was designed for (and works best with)
fine-grained opcodes, where the implementations are short
(typically a few machine instructions) and therefore the cost
of opcode dispatch dominates. The next section presents an
example in such a context.
3.1 Simple example
We will illustrate our technique by applying it to a simple
"RISC-like" virtual machine executing the "nfibs" func-
tion, as shown in Figure 5. 3
Our example interpreter implements a register-based execution
model. It has a handful of "registers" for performing
arithmetic, and a stack that is used for saving return addresses
and the contents of clobbered registers during subroutine
calls. The direct threaded code has two kinds of in-line
operand: instruction pointer-relative offsets for branch
destinations, and absolute addresses for function call destinations

The interpreter translates bytecodes into threaded code
in two passes. It makes a first pass over the bytecodes,
expanding them into threaded opcodes with no inlining, exactly
as explained in Section 2.3. Figure 6 shows a symbolic
listing of the nfibs function, implemented for our example
interpreter's opcode set, after this initial translation into
threaded code.
Bytecode operands are placed inline in the threaded code
during translation. For example, the offset for the jge op-code
and the call destinations are placed directly in the
opcode stream, immediately after the associated opcode.
These are represented as the pseudo-operand '@' in the fig-
3 This doubly-recursive function has the interesting property that
its result is the number of function calls required to calculate the
result.
nfibs:
=cont
=nfibs
=nfibs

Figure

7: Threaded code for nfibs benchmark, after
inlining. The implementations of the new macro
opcodes are shown on the right.
ure, and appear on a separate line in the code prefixed with
'='.
After this initial translation to threaded code, a second
pass performs inlining on the threaded code: basic blocks
are identified, used to dynamically generate new threaded
macro opcodes, and the corresponding original sequences of
threaded opcodes are replaced with single macro opcodes.
The rewriting of the threaded code can be performed in-situ,
since optimizing an opcode sequence will always result in a
shorter sequence of optimized code; there is no possibility of
overwriting an opcode that has not yet been considered for
inlining.

Figure

7 shows the code for the nfibs function after in-lining
has taken place. The function has been reduced to
five threaded macro opcodes (shown as '%1' through `%5'),
each replacing a basic block in the original code. The implementation
of each new macro opcode is the concatenation of
the implementations of the opcodes that it replaces. These
new implementations are written in a separate area of memory
called the macro cache. Five such implementations are
required for nfibs, and are shown within curly braces in the
figure. Each one ends with a copy of the implementation of
the pseudo-opcode !thr?, which is the threading operation
to dispatch the next opcode.
Inline arguments are copied verbatim, except for cont (a
jump offset) which is adjusted appropriately by the transla-
tor. (These inline arguments are used by the macro opcode
implementations at the points marked with '@' in the figure.)
To help with the identification of basic blocks, we divide
our threaded opcodes into four classes, as follows:
INLINE - the opcode's implementation can be inlined
into a macro opcode without restriction (the arithmetic
opcodes belong to this class);
PROTECT - the implementation contains a C function
call and therefore cannot be inlined (the print opcode
belongs to this class);
FINAL - the opcode changes the flow of control and
therefore defines the end of a basic block (e.g. the call
RELATIVE - the opcode changes the flow of control
and therefore defines the end of a basic block (e.g. the
conditional branch jge).
The only difference between FINAL and RELATIVE is the way
in which the opcode's inline operand is treated. In the first
case the operand is absolute, and can be copied directly into
the final translated code. In the second case the operand is
relative to the current threaded program counter, and so
must be adjusted appropriately in the final translated code.

Figure

8 shows the translator code that initializes the
threaded opcode table, along with representative implementations
of several of our threaded opcodes (each of the four
classes of threaded opcode is represented).
#define
#define POP() (*sp-)
#define GET() ((long)(*++ip)) /* read inline operand */
#define NEXT() goto *++ip /* dispatch next opcode */
#define PROTECT (0x00) /* never expanded */
#define INLINE (1!!0) /* expanded */
#define FINAL (1!!1) /* expanded, ends a basic block */
#define RELATIVE (1!!2) /* expanded, ends a basic block,
offset follows */
#define OP(NAME, NARGS, FLAGS) "
case
if (!initialIP) break; "
start-#NAME:
/* opcode body */
#define
/* initialize rather than execute (see macro 'OP') */
for (int
switch (op) -
OP(jge-r0-r1, 1, RELATIVE) - register long
if (r0 ?= r1) ip += offset;
OP(call, 1, FINAL) - register long dest = GET();
*)dest -
default:
fprintf(stderr, "panic: op %d is undefined!"n", op);
abort();

Figure

8: Opcode table initialization.
The translator's inlining loop is shown in Figure 9. It is
not as complex as it might first appear. code is a pointer to
the translated threaded code, which is rewritten in-situ. in
and out are indices into code pointing to the next opcode
to be copied (or inlined) and the location to which it will be
copied, respectively (in ?= out at all times).
The loop considers each in opcode for inlining: the inlining
loop is entered only if both the current opcode and the
opcode following it can be inlined. If this is not the case,
the opcode at in is copied (along with any inline arguments)
directly to out.
nextMacro is a pointer to the next unused location in
the macro cache. The inlining loop first writes this address
to out (it represents the threaded opcode for the macro
implementation that is about to be generated), and then
copies the compiled implementations of opcodes from in
into the macro cache. The inlined threaded opcodes are not
copied, although any inline arguments that are encountered
are copied directly to out.
The inlining loop continues until it copies the implementation
of an opcode that explicitly ends a basic block
or RELATIVE), or until the next opcode is either non-inlinable
int
while
int nextIn = in
long
if (info[thisOp].flags == INLINE &&
info[nextOp].flags != PROTECT &&
/* CAN INLINE: create new macro opcode at nextMacro */
void
new macro opcode */
while (info[thisOp].flags != PROTECT) -
icopy(info[thisOp].addr, ep, info[thisOp].size);
if (info[thisOp].flags == RELATIVE) -
locn of offset */
for (int
if (info[thisOp].flags == FINAL -
info[thisOp].flags == RELATIVE -
destination[in])
break; /* end of basic block */
/* copy threading operation */
icopy(info[thr].addr, ep, info[thr].size);
/* CAN'T INLINE: copy opcode and inline arguments */
if (info[thisOp].flags == RELATIVE) -
/* copy literal arguments */
for (int

Figure

9: Dynamic translator loop.
(PROTECTED) or a branch destination (implicitly ending the
current basic block). The translator then appends the implementation
of the pseudo-opcode thr, which is the "thre-
ading" operation itself. Finally, the nextMacro location is
updated ready for the next inlining operation.
The translator loop uses an array of flags "destination"
to identify branch destinations within the threaded code.
This array is easily constructed during the translator's first
pass, when bytecodes are expanded into non-inlined threaded
code. The loop also creates two arrays, relocations
and patchList, that are used to recalculate relative branch
offsets. 4
The inlining loop concatenates opcode implementations
using the icopy function, shown in Figure 10. This function
is similar to bcopy except that it also synchronizes the pro-
cessor's instruction and data caches to ensure that the new
macro opcode's implementation is executable. It contains
the only line of platform-dependent code in our interpreter.
4 The branch destination identification and relative offset recalculation
are not shown here. These can be seen in the full source code
for the example interpreter (see the Appendix).
static inline void icopy(void *source, void *dest, size-t size)
bcopy(source, dest, size);
while (size ?
asm ("dcbst 0,%0; sync; icbi 0,%0; isync" :: "r"(p));
#elif defined(-sparc)
asm ("flush %0; stbar" :: "r"(p));
/* no-op */
#elif defined(.)
#endif
dest += 4; size -= 4;

Figure

10: The icopy function, containing the single
line of platform-dependent code.
3.2 Saving space
Translating multiple copies of the same opcode sequences
would waste space. We therefore keep a cache of dynamically
generated macro opcodes, keyed by a hash value computed
from the incoming (unoptimized) opcodes during
translation. In the case of a cache hit we reuse the existing
macro opcode in the translated code, and immediately
reclaim the macro cache space occupied by the newly
translated version. In the case of a cache miss, the newly
generated macro opcode is used in the translated code and
the hash table updated to include the new opcode. This
ensures that we never have more than one macro opcode
corresponding to a given sequence of unoptimized opcodes.
4 Experimental results
We are particularly interested in the performance benefits
when dynamic inlining is applied to interpreters with fine-grain
instruction sets. Nevertheless, we were also curious to
see how the technique would perform when applied to an
interpreter having a more coarse-grained bytecode set. We
took measurements in both of these contexts, using our own
RISC-like interpreter and the widely-used (but less suited)
interpreter for the Objective Caml language.
4.1 Fine-grained opcodes
Our RISC-like interpreter has an opcode set similar to that
presented in Section 3.1. It can be configured (at compile
time) to use bytecodes, direct threaded code, or direct threaded
code with dynamically-generated macro opcodes. The
performance of two benchmarks was measured using this in-
terpreter: the function-call intensive Fibonacci benchmark
presented earlier (nfibs), and a memory intensive, function
call free, prime number generator (sieve).

Table

1 shows the number of seconds required to execute
these benchmarks on several architectures (133MHz
Pentium, SparcStation 20, and 200MHz PowerPC 603ev).
The figures shown are for a simple bytecode interpreter, the
same interpreter performing translation into direct threaded
code, direct threaded code with dynamic inlining of common
opcode sequences, and the benchmark written in C
and compiled with the same optimization options (-O2) as
our interpreter. The final column shows the performance of
the inlined threaded code compared to optimized C.
nfibs
machine bytecode threaded inlined C inlined/C
Pentium 63.2 37.1 22.3 11.1 49.8%
sieve
machine bytecode threaded inlined C inlined/C
Pentium 25.1 17.6 13.2 4.6 34.8%

Table

1: nfibs and sieve benchmark results for the
three architectures tested. The final column shows
the speed of the inlined threaded code relative to optimized
C.
Pentium
Pentium
bytecode direct threaded inlined

Figure

11: Benchmark performance relative to optimized C.
nfibs spends much of its time performing arithmetic between
registers. Memory (stack) operations are performed
only during function call and return.
Our interpreter allocates the first few VM registers in
physical machine registers whenever possible. The opcodes
that perform arithmetic are therefore typically compiled into
a single machine instruction on the Sparc and PowerPC.
These two architectures show a marked improvement in performance
when common sequences are inlined into single
macro opcodes, due to the significantly reduced ratio of op-code
dispatch to "real" work. The effect is less pronounced
on the Pentium, which has so few machine registers that
all the VM registers must be kept in memory. Each arithmetic
opcode compiles into several Pentium instructions,
and therefore the ratio of dispatch overhead to real work
is lower than for the RISC architectures.
We observe a marked improvement (approximately a factor
of two) between successive versions of the interpreter for
nfibs.
sieve shows a less pronounced improvement because it
spends the majority of its time performing memory opera-
tions. The contribution of opcode dispatch to the overall
execution time is therefore smaller than with nfibs.
It is also interesting to observe the performance of each
version of the interpreter relative to that of optimized C.

Figure

11 shows that nfibs gains approximately 14% the
speed of optimized C when moving from a bytecoded representation
to threaded code. The gain when moving from
threaded to inlined threaded code is more dependent on the
architecture: approximately 20% for the Pentium, and 38%
for the Sparc. The gains for sieve are both smaller and less
dependent on the architecture: approximately 9% at each
step, for all three architectures.
4.2 Objective Caml
We also applied our technique to the Objective Caml byte-code
interpreter, in order to obtain realistic measurements
of its performance and overheads in a less favorable environment

Objective Caml was chosen because the design and implementation
of the interpreter's core is clean and simple,
and so understanding it before making the required modifications
did not present a significant challenge. Furthermore
it is a fully-fledged system that includes a bytecode com-
piler, a benchmark suite, and some large applications. This
made it easier to collect meaningful statistics.
The interpreter is also equipped with a mechanism to
bulk-translate the bytecodes into threaded code at startup
(on those platforms that support it). 5 We needed only to
extend this initial translation phase to perform the analysis
of opcode sequences, generate macro opcode implementa-
tions, and rewrite the threaded code in-situ to use these
dynamically-generated macro opcodes. Implementing our
technique for the Caml virtual machine took one day. There
were only two small details that required careful attention.
The first was the presence of the SWITCH opcode. This
performs a multi-way branch, and is followed in the threaded
code by an inline table mapping values onto branch offsets.
We added a special case to our translator loop to handle this
opcode.
The second was the existence of a handful of opcodes
that consume two inline arguments (a literal and a relative
offset). We introduced a new opcode class RELATIVE2
for these, which differs from RELATIVE only by copying an
additional inline literal argument before the offset in the
translator loop.
Our translation algorithm was identical in all other respects
to the one presented in Section 3.
We ran the standard Objective Caml benchmark suite 6
with our modified VM (see Table 2). The VM was instrumented
to gather statistics relating to execution speed,
5 It uses gcc's first-class labels to do this portably.ftp://ftp.inria.fr/INRIA/Projects/cristal/Xavier.Leroy/
benchmarks/objcaml.tar.gz
boyer
fib
genlex
qsort
qsort*
sieve
soli
soli*
takc
taku
speed (inlined/non-inlined)
Pentium Sparc PowerPC

Figure

12: Objective-Caml benchmark results for the three architectures tested. The vertical axis shows the performance
relative to the original (non-inlining) interpreter. Asterisks indicate versions of the benchmarks compiled with array bounds
checking disabled.
boyer term processing, function calls
fib integer arithmetic, function calls (1 arg)
genlex lexing, parsing, symbolic processing
kb term processing, function calls, functionals
qsort integer arrays, loops
sieve integer arithmetic, list processing, functionals
soli puzzle solving, arrays, loops
takc integer arithmetic, function calls (3 args, curried)
taku integer arithmetic, function calls (3 args, tuplified)

Table

2: Objective Caml benchmarks.
memory usage, and the characteristics of dynamically generated
macro opcodes.

Figure

12 shows the performance of the benchmarks after
inlining, relative to the original performance without inlining

It is important to note that the Objective Caml byte-code
set has already been optimized statically, as described
in Section 2.4 [Ler98]. Any further improvements are therefore
due mainly to the elimination of dispatch overhead in
common sequences that are particular to each application.
Virtual machines whose bytecode sets have not been "stat-
ically" optimized in this way would benefit more from our
technique.
We can see from the figure that the majority of benchmarks
benefit from a significant performance advantage after
inlining. In most cases the inlined version runs more than
50% faster than the original, with two of the benchmarks
running twice as fast as the original non-inlined version on
the Sparc.
It is clear that the improvements are related to the processor
architecture. This is probably due to differences in
the cost of the threading operation. On the Sparc, for ex-
ample, avoiding the pipeline stalls associated with threading
seems to make a significant difference.

Figure

13 shows the final size of the macro cache for
each benchmark on the Sparc, plotted as a factor of the size
of the original (unoptimized) code. The final macro cache135
cache
size
original
code
size
original code size (kbytes)

Figure

13: Macro cache size (diamonds) and optimized
threaded code size (crosses), plotted as a factor
of the original code size.
sizes vary slightly for each architecture, since they depend
on the size of the bytecode implementations. However, the
shape is the same in each case. The average ratios of original
bytecode size to the macro cache size show that the cost is
between three and four times the size of the original code on
the Sparc. (The ratio is almost identical for the PowerPC,
and slightly smaller for the Pentium.)
We observe that this ratio decreases gradually as the
original code size increases. This is to be expected, since
larger bodies of code will tend to reuse macro opcodes rather
than generating new ones. We tested this by translating the
bytecoded version of the Objective Caml compiler: 421,532
bytes of original code generated 941,008 bytes of macro op-code
implementation on the Sparc. This is approximately
2.2 times the size of the original code, and is shown as the
rightmost point in the graph.
Inlined threaded code is always smaller than the original
code from which is generated. Figure 13 also shows the final
optimized code size for each benchmark. We observe that
the ratio is independent of the size of the benchmark. This is
also to be expected, since the reduction in size is dependent
on the average number of opcodes in a common sequence
and the density of the corresponding macro opcodes in the
final code. These depend mainly on the characteristics of
the language and its opcode set.
Some systems have a long-lived object memory, and generate
new executable code at runtime. A realistic implementation
for such systems would recycle the macro cache space,
and possibly use profiling to optimize only popular areas of
the program. For example, the 68040LC emulator found on
Macintosh systems performs dynamic translation of 68040
into PowerPC code; it normally requires only 250Kb of cache
in which the most commonly used translated code sequences
are stored [Tho95]. A similar (fixed) cache size is effective
in the BrouHaHa Smalltalk system [Mir97].
Translation speed is also an important factor. To measure
this we ran the Object Caml bytecode compiler (a much
larger program than any of the benchmarks) with our modified
interpreter. The 105,383 opcodes of the Objective Caml
compiler are translated in 0.22 seconds on the Sparc, a rate
of 480,000 opcodes per second. The inlining interpreter executes
the compiler at a rate of 2.4 million opcodes per sec-
ond. Translation is therefore approximately five times slower
than execution. 7
5 Related work
BrouHaHa and Objective Caml have both demonstrated the
benefits of creating specialized macro opcodes that perform
the work of a sequence of common opcodes. In Objective
Caml this led to a new bytecode set. In BrouHaHa the
standard Smalltalk-80 bytecodes are translated into threaded
code for execution; the detection of a limited number
of pre-determined common bytecode sequences is performed
during translation, and a specialized opcode is substituted
in the executable code. Our contribution is the extension of
this technique to dynamically analyze and generate implementations
for new macro opcodes at runtime.
Several systems use concatenation of pre-compiled sequences
of code at runtime [Aus96, Noe98], but in a completely
different context. Their precompiled code sequences
are generic "templates" that can be parameterized at run-time
with particular constant values.
A template-based approach is also used in some commercial
Smalltalk virtual machines that perform dynamic
compilation to native code [Mir97]. However, this technique
is complex and requires a significant effort to implement the
templates for a new architecture.
An interesting system for portable dynamic code generation
is vcode [Eng96], an architecture-neutral runtime as-
sembler. It generates code that approaches the performance
of C on some architectures. Its main disadvantage is that
retrofitting it to an existing virtual machine requires a significant
amount of effort - certainly more than the single day
that was required to implement our technique in a production
virtual machine. (Our simple nfibs benchmark runs
about 40% faster using vcode, compared to our RISC-like
inlined threaded code virtual machine.)
Superoperators [Pro95] are a technique for specializing
a bytecoded C interpreter according to the program that
it is to execute. This is possible because the specialized
7 Since translation is performed only once for each opcode, the
"break-even" point is passed in any program that executes more than
six times the number of opcodes that it contains.
interpreter is generated at the same time as the compiled
(bytecoded) representation of the program. A compile-time
analysis of the program chooses likely candidates for super-
operators, which are then implemented as new interpreter
bytecodes.
Superoperators are similar to our macro opcodes. One
advantage is that their corresponding synthesized bytecodes
can benefit from some of the inter-opcode optimizations that
our simple concatenation of implementations fails to exploit.
However, superoperators require bytecodes corresponding
precisely with the nodes used to build parse trees - which
might not always be the best choice of bytecode set. It would
also be tricky to use superoperators in an incremental system
such as Smalltalk, where new executable code is generated at
runtime. Nevertheless, an investigation of merging some of
the techniques of superoperators and dynamically-generated
macro opcodes might be very worthwhile.
6 Conclusions
This work was inspired by the need to create an interpreter
with a very fine-grain RISC-like opcode set, that is both
general (not tied to any particular high-level language) and
amenable to traditional compiler optimizations. The cost
of opcode dispatch is more significant in such a context,
compared to more abstract interpreters whose bytecodes are
carefully matched to the language semantics.
The expected benefits of our technique are related to the
average semantic content of a bytecode. We would expect
languages such as Tcl and Perl, which have relatively high-level
opcodes, to benefit less from macroization. Interpreters
with a more RISC-like opcode set will benefit more - since
the cost of dispatch is more significant when compared to the
cost of executing the body of each bytecode. The Objective
Caml bytecode set is positioned between these two extremes,
containing both simple and complex opcodes. 8
Vcode has better performance than our technique because
its instruction set matches very closely the underlying
architecture. It can exert very fine control over the code that
is generated, such as performing some degree of reordering
for better instruction scheduling. We believe that similar results
can be achieved with our RISC-like inlining threaded
code interpreter, but in a more portable manner.
The performance of macro opcodes is limited by the inability
of the compiler to perform the inter-opcode optimizations
that are possible when a static analysis is performed
and new macro opcodes implemented manually in the in-
terpreter. We believe that these limitations are less important
when using a very fine-grain opcode set, corresponding
more closely to a traditional RISC architecture. Most op-codes
will be implemented as a single machine instruction,
and new opportunities for inter-opcode optimization will be
available to the translator's code generator.
Our technique is portable, simple to implement, and orthogonal
to the implementation of the virtual machine's op-
codes. In reducing the overhead of opcode dispatch, it helps
to bring the performance of fine-grained bytecodes to the
same level as that of more abstract, language-dependent op-code
sets.
8 Significant overheads are associated with the technique used to
check for stack overflow and pending signals in Objective Caml, but
a discussion of these is beyond the scope of this paper.
speed (seconds) space (bytes)
Pentium Sparc PowerPC Sparc
benchmark original inlined original inlined original inlined original inlined cache
boyer 2.0 1.81 (111%) 2.3 1.50 (154%) 1.4 1.19 (113%) 13800 8324 42012
fib 2.0 1.44 (140%) 4.0 2.47 (163%) 1.6 1.12 (139%) 5288 3320 20160
genlex 1.0 0.93 (110%) 1.1 0.84 (127%) 0.7 0.59 (118%) 45696 26856 156892
kb 10.3 8.15 (126%) 16.9 7.71 (219%) 6.3 5.36 (118%) 20968 13048 75868
qsort 5.8 3.95 (146%) 9.5 5.39 (175%) 4.1 2.98 (137%) 6676 3932 26416
qsort* 4.8 3.04 (158%) 8.0 4.26 (188%) 3.3 2.27 (147%) 6532 3884 25280
sieve 3.0 2.79 (107%) 2.5 2.22 (110%) 1.9 1.86 (100%) 5200 3312 20124
soli 3.1 2.18 (144%) 5.1 2.98 (170%) 2.1 1.50 (142%) 6644 3952 25516
soli* 2.4 1.38 (172%) 4.0 2.00 (202%) 1.6 0.93 (168%) 6544 3908 24548
takc 2.8 1.91 (144%) 5.0 3.26 (152%) 2.1 1.47 (142%) 4784 3012 18652
taku 4.9 3.20 (152%) 7.0 4.14 (170%) 3.2 2.33 (139%) 4812 3036 18296

Table

3: Raw results for the Objective-Caml benchmarks.

Acknowledgements

The authors would like to thank Xavier Leroy, John Mal-
oney, Eliot Miranda, Dave Ungar, Mario Wolczko and the
anonymous referees, for their helpful comments on a draft
of this paper.



--R

The Java Programming Lan- guage

Communications of the ACM
Efficient Implementation of the Smalltalk-80 System
Engler, vcode: A Retargetable
A Portable Forth Engine

Back to the Future: the Story of Squeak
The Objective Caml system release 1.05

The Java Virtual Machine Specification

Fast Direct



Optimizing an ANSI C Interpreter with Superoperators
Building the Better Virtual CPU
--TR
Smalltalk-80: the language and its implementation
BrouHaHa- A portable Smalltalk interpreter
Fast, effective dynamic compilation
Back to the future
The Java programming language (2nd ed.)
Java Virtual Machine Specification
Efficient implementation of the smalltalk-80 system

--CTR
Alex Iliasov, Templates-based portable just-in-time compiler, ACM SIGPLAN Notices, v.38 n.8, August
Fabrice Bellard, QEMU, a fast and portable dynamic translator, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.41-41, April 10-15, 2005, Anaheim, CA
Jinzhan Peng , Gansha Wu , Guei-Yuan Lueh, Code sharing among states for stack-caching interpreter, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C.
Ben Stephenson , Wade Holst, Multicodes: optimizing virtual machines using bytecode sequences, Companion of the 18th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 26-30, 2003, Anaheim, CA, USA
Brian Davis , John Waldron, A survey of optimisations for the Java Virtual Machine, Proceedings of the 2nd international conference on Principles and practice of programming in Java, June 16-18, 2003, Kilkenny City, Ireland
M. Anton Ertl , David Gregg, Combining stack caching with dynamic superinstructions, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C.
Andrew Beatty , Kevin Casey , David Gregg , Andrew Nisbet, An optimized Java interpreter for connected devices and embedded systems, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Bertil Folliot , Ian Piumarta , Fabio Riccardi, A dynamically configurable, multi-language execution platform, Proceedings of the 8th ACM SIGOPS European workshop on Support for composing distributed applications, p.175-181, September 1998, Sintra, Portugal
Marc Berndl , Laurie Hendren, Dynamic profiling and trace cache generation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
Brian Davis , Andrew Beatty , Kevin Casey , David Gregg , John Waldron, The case for virtual register machines, Proceedings of the workshop on Interpreters, virtual machines and emulators, p.41-49, June 12-12, 2003, San Diego, California
M. Anton Ertl , David Gregg, Retargeting JIT Compilers by using C-Compiler Generated Executable Code, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.41-50, September 29-October 03, 2004
Henrik Nssn , Mats Carlsson , Konstantinos Sagonas, Instruction merging and specialization in the SICStus Prolog virtual machine, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.49-60, September 05-07, 2001, Florence, Italy
Mourad Debbabi , Abdelouahed Gherbi , Lamia Ketari , Chamseddine Talhi , Hamdi Yahyaoui , Sami Zhioua, a synergy between efficient interpretation and fast selective dynamic compilation for the acceleration of embedded Java virtual machines, Proceedings of the 3rd international symposium on Principles and practice of programming in Java, June 16-18, 2004, Las Vegas, Nevada
Mathew Zaleski , Marc Berndl , Angela Demke Brown, Mixed mode execution with context threading, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.305-319, October 17-20, 2005, Toranto, Ontario, Canada
M. Anton Ertl , David Gregg, Optimizing indirect branch prediction accuracy in virtual machine interpreters, ACM SIGPLAN Notices, v.38 n.5, May
Yunhe Shi , David Gregg , Andrew Beatty , M. Anton Ertl, Virtual machine showdown: stack versus registers, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA
Marc Berndl , Benjamin Vitale , Mathew Zaleski , Angela Demke Brown, Context Threading: A Flexible and Efficient Dispatch Technique for Virtual Machine Interpreters, Proceedings of the international symposium on Code generation and optimization, p.15-26, March 20-23, 2005
Benjamin Vitale , Tarek S. Abdelrahman, Catenation and specialization for Tcl virtual machine performance, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C.
K. S. Venugopal , Geetha Manjunath , Venkatesh Krishnan, sEc: A Portable Interpreter Optimizing Technique for Embedded Java Virtual Machine, Proceedings of the 2nd Java Virtual Machine Research and Technology Symposium, p.127-138, August 01-02, 2002
M. Anton Ertl , David Gregg , Andreas Krall , Bernd Paysan, Vmgen: a generator of efficient virtual machine interpreters, SoftwarePractice & Experience, v.32 n.3, p.265-294, March 2002
Jeffery von Ronne , Ning Wang , Michael Franz, Interpreting programs in static single assignment form, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C.
Mathew Zaleski , Angela Demke Brown , Kevin Stoodley, YETI: a graduallY extensible trace interpreter, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA
Mourad Debbabi , Abdelouahed Gherbi , Azzam Mourad , Hamdi Yahyaoui, A selective dynamic compiler for embedded Java virtual machines targeting ARM processors, Science of Computer Programming, v.59 n.1-2, p.38-63, January 2006
Arun Kejariwal , Xinmin Tian , Milind Girkar , Wei Li , Sergey Kozhukhov , Utpal Banerjee , Alexander Nicolau , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, Tight analysis of the performance potential of thread speculation using spec CPU 2006, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
David Gregg , Andrew Beatty , Kevin Casey , Brain Davis , Andy Nisbet, The case for virtual register machines, Science of Computer Programming, v.57 n.3, p.319-338, September 2005
Etienne M. Gagnon , Laurie J. Hendren, SableVM: a research framework for the efficient execution of java bytecode, Proceedings of the JavaTM Virtual Machine Research and Technology Symposium on JavaTM Virtual Machine Research and Technology Symposium, p.3-3, April 23-24, 2001, Monterey, California
Gregory T. Sullivan , Derek L. Bruening , Iris Baron , Timothy Garnett , Saman Amarasinghe, Dynamic native optimization of interpreters, Proceedings of the workshop on Interpreters, virtual machines and emulators, p.50-57, June 12-12, 2003, San Diego, California
Ana Azevedo , Arun Kejariwal , Alex Veidenbaum , Alexandru Nicolau, High performance annotation-aware JVM for Java cards, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA
Scott Thibault , Charles Consel , Julia L. Lawall , Renaud Marlet , Gilles Muller, Static and Dynamic Program Compilation by Interpreter Specialization, Higher-Order and Symbolic Computation, v.13 n.3, p.161-178, Sept. 2000
Mahmut Taylan Kandemir, Improving whole-program locality using intra-procedural and inter-procedural transformations, Journal of Parallel and Distributed Computing, v.65 n.5, p.564-582, May 2005
John Aycock, A brief history of just-in-time, ACM Computing Surveys (CSUR), v.35 n.2, p.97-113, June
threaded code;bytecode interpretation;dynamic translation;inlining;just-in-time compilation