Speculative Staging for Interpreter Optimization
Stefan Brunthaler
University of California, Irvine
s.brunthaler@uci.edu

arXiv:1310.2300v1 [] 8 Oct 2013

Abstract

many problems, e.g., a lot of tricky details, hard to debug,
and substantial implementation effort. An alternative route
is to explore the area of purely interpretative optimization
instead. These are optimizations that preserve innate interpreter characteristics, such as ease-of-implementation and
portability, while offering important speedups. Prior work in
this area already reports the potential of doubling the execution performance [7, 8]. As a result, investigating a general
and principled strategy for optimizing high abstraction-level
interpreters is particularly warranted.
Interpreting a dynamically typed programming language,
such as JavaScript, Python, or Ruby, has its own challenges.
Frequently, these interpreters use one or a combination of the
following features:

Interpreters have a bad reputation for having lower performance than just-in-time compilers. We present a new way
of building high performance interpreters that is particularly
effective for executing dynamically typed programming languages. The key idea is to combine speculative staging of
optimized interpreter instructions with a novel technique of
incrementally and iteratively concerting them at run-time.
This paper introduces the concepts behind deriving optimized instructions from existing interpreter instructions—
incrementally peeling off layers of complexity. When compiling the interpreter, these optimized derivatives will be compiled along with the original interpreter instructions. Therefore, our technique is portable by construction since it leverages the existing compiler’s backend. At run-time we use
instruction substitution from the interpreter’s original and
expensive instructions to optimized instruction derivatives to
speed up execution.
Our technique unites high performance with the simplicity
and portability of interpreters—we report that our optimization makes the CPython interpreter up to more than four
times faster, where our interpreter closes the gap between and
sometimes even outperforms PyPy’s just-in-time compiler.

• dynamic typing to select type-specific operations,
• reference counting for memory management, and
• modifying boxed data object representations.

To cope with these features, interpreter instructions naturally
become expensive in terms of assembly instructions required
to implement their semantics. Looking at successful research
in just-in-time compilation, we know that in order to achieve
substantial performance improvements, we need to reduce the
complexity of the interpreter instructions’ implementation.
Put differently, we need to remove the overhead introduced by
dynamic typing, reference counting, and operating on boxed
data objects.
In this paper we combine ideas from staged compilation
with partial evaluation and interpreter optimization to devise a
general framework for interpreter optimization. From staged
compilation, we take the idea that optimizations can spread
out across several stages. From partial evaluation, we take
inspiration from the Futamura projections to optimize programs. From interpreter optimization, we model a general
theory of continuous optimization based on rewriting instructions. These ideas form the core of our framework, which
is purely interpretative, i.e., it offers ease-of-implementation
and portability while avoiding dynamic code generation, and
delivers high performance. As a result, close to three decades
after Deutsch and Schiffman [16] described the ideas of what
would eventually become the major field of just-in-time compilation, our framework presents itself as an alternative to
implementing JIT compilers.

General Terms Design, Languages, Performance
Keywords Interpreter, Optimization, Speculative Staging,
Partial Evaluation, Quickening, Python

1.

Introduction

The problem with interpreters for dynamically typed programming languages is that they are slow. The fundamental
lack of performance is due to following reasons. First, their
implementation is simple and does not perform known interpreter optimizations, such as threaded code [3, 4, 14] or
superinstructions [19, 20, 39]. Second, even if the interpreters
apply these known techniques, their performance potential
is severely constrained by expensive interpreter instruction
implementations [6].
Unfortunately, performance-conscious implementers suffer from having only a limited set of options at their disposal
to solve this problem. For peak performance, the current bestpractice is to leverage results from dynamic compilation. But,
implementing a just-in-time, or JIT, compiler is riddled with
1

2013/07/12

Summing up, this paper makes the following contributions.

work at compile time, link-time, load-time, or finally at runtime. The problem with staged optimizations for high-level
languages such as JavaScript, Python, and Ruby is that they
require at least partial knowledge about the program. But, as
the example of the sum function illustrates, only at run-time
we will actually identify the concrete type τ for parameters a
and b.
For our target high-level languages and their interpreters,
staged compilation is not possible, primarily due to two
reasons. First, none of these interpreters have a JIT compiler,
i.e., preventing staged partial optimizations. Second, the
stages of staged compilation and interpreters are separate.
The traditional stages listed above need to be partitioned into
stages that we need to assemble the interpreter (viz. compiletime, link-time, and load-time), and separate stages of running
the program: at interpreter run-time, it compiles, potentially
links, loads and runs hosted programs.

• We introduce a general theory for optimizing interpreter

instructions that relies on speculatively staging of optimized interpreter instructions at interpreter compile-time
and subsequent concerting at run-time (see Section 3).
• We present a principled procedure to derive optimized

interpreter instructions via partial evaluation. Here, speculation allows us to remove previous approaches’ requirement to specialize towards a specific program (see Section 3.2).
• We apply the general theory to the Python interpreter

and describe the relevant implementation details (see Section 4).
• We provide results of a careful and detailed evaluation

of our Python based implementation (see Section 5), and
report substantial speedups of up to more than four times
faster than the CPython implementation for the spectralnorm benchmark. For this benchmark our technique outperforms the current state-of-the-art JIT compiler, PyPy
1.9, by 14%.

2.

3.

The previous section sketches the problem of performing traditional staged optimizations for interpreters. In this section
we are first going to dissect interpreter performance to identify bottlenecks. Next, we are going to describe which steps
are necessary to formalize the problem, and subsequently use
speculative staged interpreter optimizations to conquer them
and achieve high performance.

Example

In this section we walk through a simple example that
illustrates how interpreters address—or rather fail to address—
the challenge of efficiently executing a high-level language.
The following listing shows a Python function sum that “adds”
its parameters and returns the result of this operation.
1
2

Speculative Staged Interpreter
Optimization

3.1

Dissecting Example Performance Obstacles

Python’s compiler will emit the following sequence of interpreter instructions, often called bytecodes, when compiling
the sum function (ignoring argument bytes for the LOAD_FAST instructions):

def sum (a , b ):
return a + b

In fact, this code does not merely “add” its operands:
depending on the actual types of the parameters a and b,
the interpreter will select a matching operation. In Python,
this means that it will either concatenate strings, or perform
arithmetic addition on either integers, floating point numbers,
or complex numbers; or the interpreter could even invoke
custom Python code—which is possible due to Python’s
support for ad-hoc polymorphism.
In 1984, Deutsch and Schiffman [16] report that there
exists a “dynamic locality of type usage,” which enables speculative optimization of code for any arbitrary but fixed and
observed type τ . Subsequent research into dynamic compilation capitalizes on this observed locality by speculatively
optimizing code using type feedback [26, 27]. From their very
beginning, these dynamic compilers—or just-in-time compilers as they are referred to frequently—had to operate within a
superimposed latency time. Put differently, dynamic compilers traditionally sacrifice known complex optimizations for
predictable compilation times.
Staged compilation provides a solution to the latency
problem of JIT compilers by distributing work needed to
assemble optimized code among separate stages. For example,
a staged compiler might break up an optimization to perform

LOAD
FAST

LOAD
FAST

BINARY RETURN
ADD
VALUE

We see that the interpreter emits untyped, polymorphic
instructions that rely on dynamic typing to actually select the
operation. Furthermore, we see that Python’s virtual machine
interpreter implements a stack to pass operand data between
instructions.
Let us consider the application sum(3, 4), i.e., sum is
used with the specific type Int×Int → Int. In this case, the
BINARY_ADD instruction will check operand types and select
the proper operation for the types. More precisely, assuming absence of ad-hoc polymorphism, the Python interpreter
will identify that both Int operands are represented by a C
struct called PyLong_Type. Next, the interpreter will determine that the operation to invoke is PyLong_Type->tp_as_number->nb_add, which points to the long_add function. This operation implementation function will then unbox
operand data, perform the actual integer arithmetic addition,
and box the result. In addition, necessary reference counting
operations enclose these operations, i.e., we need to decrease
2

2013/07/12

the reference count of the arguments, and increase the reference count of the result. Both, (un-)boxing and adjusting
reference count operations add to the execution overhead of
the interpreter.
Contrary to the interpreter, a state-of-the-art JIT compiler
would generate something like this
1
2
3
4

exercises the compiler’s backend to have portable code generation and furthermore allows the interpreter implementation
to remain simple. The whole process is, however, speculative:
only by actually interpreting a program, we know for sure
which optimized interpreter instructions are required. As a
result, we restrict ourselves to generate optimized code only
for instructions that have a high likelihood of being used.
To assemble optimized instruction sequences at run-time,
we rely on a technique known as quickening [34]. Quickening
means that we replace instructions with optimized derivatives
of the exact same instruction at run-time. Prior work focuses
on using only one level of quickening, i.e., replacing one
instruction with another instruction derivative. In this work,
we introduce multi-level quickening, i.e., the process of
iteratively and incrementally rewriting interpreter instructions
to ever more specialized derivatives of the generic instruction.

movq % rax , -8(% rsp )
movq % rbx , -16(% rsp )
addq % rax , % rbx
ret

The first two lines assume a certain stack layout to where
to find operands a and b, both of which we assume to be
unboxed. Hence, we can use the native machine addition
operation (line 3) to perform arithmetic addition and return
the operation result in %rax.
Bridging the gap between the high abstraction-level representation of computation in Python bytecodes and the low
abstraction-level representation of native machine assembly
instructions holds the key for improving interpreter performance. To that end, we classify both separate instruction sets
accordingly:

3.2.1

In this section we present a simplified substrate of a dynamically typed programming language interpreter, where we
illustrate each of the required optimization steps.

• Python’s instruction set is untyped and operates exclu1

sively on boxed objects.

2

• Native-machine assembly instructions are typed and di-

3

rectly modify native machine data.

4

LOAD
INT

INT
ADD

6
7

VBool Bool
VInt Int
VFloat Float
VString String

type Stack = [Value]
type Instr = Stack → Stack

We use Value to model a small set of types for our interpreter. The operand stack Stack holds intermediate values,
and an instruction Instr is a function modifying the operand
stack Stack. Consequently, the following implementation
of the interpreter keeps evaluating instructions until the list
of instructions is empty, whereupon it returns the top of the
operand stack element as its result:

RETURN
INT

In this lower-level instruction set the instructions are typed,
which allows using a different operand data passing convention, and directly modifying unboxed data—essentially operating at the same semantic level as the assembly instructions
shown above; disregarding the different architectures, i.e.,
register vs. stack.
3.2

data Value =
|
|
|

5

An efficient, low-level interpreter instruction set allows us
to represent the sum function’s computation for our assumed
type in the following way:
LOAD
INT

Prerequisites

1
2
3

Systematic Derivation

4

The previous section informally discusses the goal of our
speculatively staged interpreter optimization: optimizing
from high to low abstraction-level instructions. This section
systematically derives required components for enabling
interpreters to use this optimization technique. In contrast
with staged compilation, staged interpreter optimization is
purely interpretative, i.e., it avoids dynamic code generation
altogether. The key idea is that we:

5
6
7

interp :: Stack → [Instr] → Value
interp (x:xs) [] = x
interp s (i:is) =
let
s’= i s
in
eval s’ is

Using interp as the interpreter, we can turn our attention
to the actual interpreter instructions. The following example
illustrates a generic implementation of a binary interpreter
instruction, which we can instantiate, for example for an
arithmetic add operation:

• stage and compile new interpreter instructions at inter-

1

preter compile-time,
• concert optimized instruction sequences at run-time by

2
3

the interpreter.

4

The staging process involves the ahead-of-time compiler
that is used to compile the interpreter. Therefore, this process

5
6

3

binaryOp :: (Value → Value → Value) → Stack →
Stack
binaryOp f s =
let
(x, s’) = pop s
(y, s’’) = pop s’
in

2013/07/12

7

That means that for all instructions I of an interpreter interp,
we derive an optimized instruction derivative I 0 specialized to
a type τ by partially evaluating an instruction I with the type
τ . Hence, we speculate on the likelihood of the interpreter
operating on data of type τ but do eliminate the need to have
a priori knowledge about the program Π.
To preserve semantics, we need to add a guard statement
to I 0 that ensures that the actual operand types match up with
the specialized ones. If the operand types do not match, we
need to take corrective measures and redirect control back
to I. For example, we get the optimized derivative intAdd
from dtAdd by fixing the operand type to VInt:

(f x y):s’’

8
9
10

addOp :: Stack → Stack
addOp = binaryOp dtAdd

11
12
13
14
15
16
17

dtAdd
dtAdd
dtAdd
dtAdd
dtAdd
...

:: Value → Value → Value
(VInt x) (VInt y) = (VInt (x + y))
(VFloat x) (VFloat y) = (VFloat (x + y))
(VString x) (VString y) = (VString (x ++ y))
(VBool x) (VBool y) = (VBool (x && y))

The generic implementation binaryOp shows the operand
stack modifications all binary operations need to follow. The
addOp function implements the actual resolving logic of the
dynamic types of Values via pattern matching starting on
line 13 in function dtAdd.

intAdd := JmixKL [dtAdd, VInt]
1

3.2.2

First-level Quickening: Type Feedback

2
3

Definition 1 (Instruction Derivative). An instruction I 0 is
an instruction derivative of an instruction I, if and only if it
implements the identical semantics for an arbitrary but fixed
subset of I’s functionality.

(Π)[I 0 /Ip ]

1
2
3

(1)

4
5

In our scenario, this is not particularly helpful, because we
do not know program Π a priori. The second Futamura
projection tells us how to derive a compiler by applying
mix to itself with the interpreter as its input:

∀

Iτ0 := JmixKL [I, τ ]

quicken :: [ Instr ] → Int → Instr → [ Instr ]
quicken Π p derivative =
let
(x, y:ys)= splitAt p Π
r= x ++ derivative : ys

Using this derivation step, we effectively create a typed
interpreter instruction set for an instruction set originally only
consisting of untyped interpreter instructions.
3.2.3

(2)

Second-level Quickening: Type Propagation

Taking a second look at the optimized derivative instruction
intAdd shows that it still contains residual overhead: unboxing the VInt operands and boxing the VInt result (cf. line
three). It turns out that we can do substantially better by identifying complete expressions that operate on the same type
and subsequently optimizing the whole sequence.
For identifying a sequence of instructions that operate on
the same type, we leverage the type information collected at
run-time via the first-level quickening step described in the
previous section. During interpretation, the interpreter will
optimize programs it executes on the fly and single instruction occurrences will carry type information. To expand this

By using the interpreter interp as its input program, the
second Futamura projection eliminates the dependency on
the input program Π. However, for a dynamically typed
programming language, a compiler derived by applying the
second Futamura projection without further optimizations is
unlikely to emit efficient code—because it lacks information
on the types [43].
Our idea is to combine these two Futamura projections in
a novel way:
I∈interp

(5)

It is worth noting that this rewriting, or quickening as it
is commonly known, is purely interpretative, i.e., it does not
require any dynamic code generation—simply updating the
interpreted program suffices:

To obtain all possible instruction derivatives I 0 for any
given interpreter instruction I, we rely on insights obtained
by partial evaluation [30]. The first Futamura projection [23]
states that we can derive a compiled version of an interpreted
program Π by partially evaluating its corresponding interpreter interp written in language L:

compiler := JmixKL [mix, interp]

intAdd :: Value → Value → Value
intAdd (VInt x) (VInt y) = (VInt (x + y))
intAdd x y = dtAdd x y

The last line in our code example acts as a guard statement,
since it enables the interpreter to execute the type-generic
dtAdd instruction whenever the speculation of intAdd fails.
The interpreter can now capitalize on the “dynamic locality
of type usage” [16] and speculatively eliminate the overhead
of dynamic typing by rewriting an instruction I at position p
of a program Π to its optimized derivative I 0 :

Example 1. In our example interpreter interp, the addOp
instruction has type Value×Value → Value. An instruction
derivative intAdd would implement the subset case of integer
arithmetic addition only, i.e., where operands have type VInt.
Analogous cases are for all combinations of possible types,
e.g., for string concatenation (VString).

compiledΠ := JmixKL [interp, Π]

(4)

(3)

4

2013/07/12

Abstract Interpretation Taking inspiration from Leroy’s
description of Java bytecode verification [33], we also use
an abstract interpreter that operates over types instead of
values. Using the type information captured in the previous
step, for example from quickening from the type generic
addOp to the optimized instruction derivative intAdd, we
can propagate type information from operation instructions
to the instructions generating its operands.
For example, we know that the intAdd instruction expects
its operands to have type Int and produces an operand of
type Int:

information to bigger sequences, we use an abstract interpreter that propagates the collected type information. Once
we have identified a complete sequence of instructions operating on the same type, we then quicken the complete sequence
to another set of optimized derivatives that directly modify
unboxed data. Since these instructions operate directly on
unboxed data, we need to take care of several pending issues.
First, operating on unboxed data requires modifying the
operand stack data passing convention. The original instruction set, as well as the optimized typed instruction set, operates on boxed objects, i.e., all elements on the operand stack
are just pointers to the heap, having the type of one machine
word (uint64 on modern 64-bit architectures). If we use
unboxed data elements, such as native machine integers and
floats, we need to ensure that all instructions follow the same
operand passing convention.

intAdd : (VInt.VInt.S) → (VInt.S)
Similar to our actual interpreter, the abstract interpreter uses
a transition relation i : S → S 0 to represent an instruction
i’s effect on the operand stack. All interpreter instructions
of the original instruction set are denoted by type-generic
rules that correspond to the top element of the type lattice,
i.e., in our case Value. The following rules exemplify the
representation, where we only separate instructions by their
arity:

Definition 2 (Operand Stack Passing Convention). All instructions operating on untyped data need to follow the same
operand stack data passing convention. Therefore, we define
a conversion function c to map data to and from at least one
native machine word:
cτ : τ → uint64+
c−1
τ

+

: uint64 → τ

(6)

unaryOp : (Value.S) → (Value.S)

(7)

binaryOp : (Value.Value.S) → (Value.S)

Second, we need to provide and specify dedicated (un)boxing operations to unbox data upon entering a sequence
of optimized interpreter instructions, and box results when
leaving an optimized sequence.

The set of types our abstract interpreter operates on corresponds to the set of types we generated instruction derivatives for in the first-level quickening step, i.e., (Int, Bool,
Float, String). For simplicity, our abstract interpreter ignores branches in the code, which limits our scope to propagate types along straight-line code, but on the other hand
avoids data-flow analysis and requires only one linear pass
to complete. This is important insofar as we perform this
abstract interpretation at run-time and therefore are interested
to keep latency introduced by this step at a minimum.
Type propagation proceeds as follows. The following
example shows an original example program representation
as emitted by some other program, e.g., another compiler:

Definition 3 (Boxing and Unboxing of Objects). We define
a function m to map objects to at least one machine word and
conversely from at least one machine word back to proper
language objects of type π.
mπ : π → τ +
m−1
π

:τ

+

→π

(8)
(9)

Third, this optimization is speculative, i.e., we need to take
precautions to preserve semantics and recover from misspeculation. Preserving semantics of operating on unboxed data
usually requires to use a tagged data format representation,
where we reserve a set of bits to hold type information. But,
we restrict ourselves to sequences where we know the types a
priori, which allows us to remove the restrictions imposed by
using a tagged data format, i.e., additional checking code and
decreasing range of representable data. In general, whenever
our speculation fails we need to generalize specialized instruction occurrences back to their more generic instructions
and resume regular interpretation.
In all definitions, we use the + notation to indicate that
a concrete instantiation of either c or m is able to project
data onto multiple native machine words. For example, the
following implementation section will detail one such case
where we represent Python’s complex numbers by two native
machine words.

[· · · , push0 , push1 , addOp2 , push3 , addOp4 , pop5 , · · · ]
After executing this example program, the first-level quickening captures types encountered during execution:
[· · · , push0 , push1 , intAdd2 , push3 , intAdd4 , pop5 , · · · ]
Now, we propagate the type information by abstract interpretation. Since intAdd expects operands of type Int, we can
infer that the first two push instructions must push operands
of type Int onto the operand stack. Analogously, the second
occurrence of intAdd allows us to infer that the result of
the first intAdd has type Int, as does the third occurrence
of the push instruction. Finally, by inspecting the type stack
when the abstract interpreter reaches the pop instruction, we
know that it must pop an operand of type Int off the stack.
5

2013/07/12

Therefore, after type propagation our abstract interpreter will
have identified that the complete sequence of instructions
actually operate exclusively on data of type Int:

3
4
5
6

[· · · , push0Int , push1Int , intAdd2 , push3Int , intAdd4 , pop5Int , · · ·7 ]
8

We denote the start and end instructions of a candidate
sequence by S and E, respectively. In our example, the six
element sequence starts with the first push instruction, and
terminates with the pop instruction terminates:

9

Finally, we need to make sure that once we leave an optimized sequence of instructions, the higher level instruction
sets continue to function properly. Hence, we need to box all
objects the sequence computes at the end of the optimized
sequence. For example, if we have a store instruction that
saves a result into the environment, we need to add boxing to
its implementation:

S := push0Int
E := pop5Int
Unboxed Instruction Derivatives Analogous to the previous partial evaluation step we use to obtain the typed instructions operating exclusively on boxed objects, we can use the
same strategy to derive the even more optimized derivatives.
For regular operations, such as our intAdd example, this
is simple and straightforward, as we just replace the boxed
object representation Value by its native machine equivalent
Int:
1
2

1
2
3
4
5
6
7

intAdd’ :: Int → Int → Int
intAdd’ x y = x + y

2
3
4
5
6
7
8

pushInt :: Value → S →S
pushInt v s =
let
unboxConvert= cint64 · mVInt
in
case v of
VInt value → (unboxConvert value) : s
_
→ -- misspeculation, generalize

Since the operand passing convention is type dependent,
we cannot use the previous implementation of binaryOp
anymore, and need a typed version of it:
1
2

storeIntOp :: S →Env → String → S
storeIntOp s e ident =
let
−1
boxPopInt = m−1
VInt · cint64 · pop
(obj, s’) = boxPopInt s
in
(λx (update e ident obj)) → s’

Generalizing When Speculation Fails In our example of
the pushInt interpreter instruction, we see on the last line
that there is a case when speculation fails. A specific occurrence of pushInt verifies that the operand matches an
expected type such that subsequent instructions can modify
on its unboxed representation. Therefore, once the interpreter
detects the misspeculation, we know that we have to invalidate all subsequent instructions that speculate on that specific
type.
The interpreter can back out of the misspeculation and
resume sound interpretation by i) finding the start of the
speculatively optimized sequence, and ii) generalizing all
specialized instructions up by at least one level. Both of
these steps are trivial to implement, particularly since the
instruction derivation steps result in having three separate
instruction sets. Hence, the first step requires to identify
the first instruction i that does not belong to the current
instruction set, which corresponds to the predecessor of the
start instruction S identified by our abstract interpreter. The
second step requires that we map each instruction starting at
offset i + 1 back to its more general parent instruction—a
mapping we can create and save when we create the initial
mapping from an instruction I to its derivative I 0 .
To be sound, this procedure requires that we further restrict
our abstract interpreter to identify only sequences that have
no side-effects. As a result, we eliminate candidate sequences
that have call instructions in between. This is however only
an implementation limitation and not an approach limitation,
since all non-local side-effects possible through function
calls do not interfere with the current execution. Therefore,
we would need to ensure that we do not re-execute already
executed functions and instead push the boxed representation
of a function call’s result onto the operand stack.

As a result, the compiler will generate an efficient native
machine addition instruction and completely sidestep the
resolving of dynamic types, as well as (un-)boxing and
reference counting operations.
The problem with this intAdd’ instruction derivative is,
however, that we cannot perform a type check on the operands
anymore, as the implementation only allows operands of
type Int. In consequence, for preserving semantics of the
original interpreter instructions, we need a new strategy for
type checking. Our solution to this problem is to bundle
type checks and unboxing operations together via function
composition and move them to the load instructions which
push unboxed operands onto the stack. Assuming that we
modify the declaration of Stack to contain heterogeneous
data elements (i.e., not only a list of Value, but also unboxed
native machine words, denoted by S), pushing an unboxed
integer value onto the operand stack looks like this:
1

let
popInt = c−1
int64 · pop
pushInt = cint64 · f
(x, s’) = popInt s
(y, s’’) = popInt s’
in
(pushInt x y) : s’’

binaryIntOp :: (Int → Int → Int) → S →S
binaryIntOp f s =

6

2013/07/12

···

Ii

Ij

In

··· 0

Ii

0
Ij:π

In

1

1st -level: Type Feedback

E

2

Abstract Interpretation

S

m−1
π

mπ
S 00

Start Instr.
LOAD_CONST
LOAD_FAST

Original Instructions

cτ
c−1
τ

E 00

3

Table 1: Valid start and end instructions used for abstract
interpretation.

nd

2 -level: Unboxed Data

Python instructions to illustrate both the abstract interpretation as well as deriving the optimized interpreter instructions.
Python itself is implemented in C and we use casts to force
the compiler to use specific semantics.
Figure 2 shows our example Python instruction sequence
and how we incrementally and iteratively rewrite this sequence using our speculatively staged optimized interpreter
instruction derivatives. We use the prefix INCA to indicate
optimized interpreter instruction derivatives used for inline
caching, i.e., the first-level quickening. The third instruction
set uses the NAMA prefix, which abbreviates native machine execution since all instructions directly operate on machine data
and hence use efficient machine instructions to implement
their operation semantics. This corresponds to the secondlevel quickening. Note that the NAMA instruction set is portable
by construction, as it leverages the back-end of the ahead-oftime compiler at interpreter compile-time.
The LOAD_FAST instruction pushes a local variable onto
the operand stack, and conversely STORE_FAST pops an
object off the operand stack and stores it in the local stack
frame. Table 1 lists the set of eligible start and end instructions
for our abstract interpreter, and Figure 3 illustrates the data
flow of the instruction sequence as assembled by the abstract
interpreter. In our example, the whole instruction sequence
operates on a single data type, but in general the abstract
interpreter needs to be aware of the type lattice implemented
by the Python interpreter. For example, dividing two long
numbers results in a float number and comparing two complex
numbers results in a long number. We model these type
conversions as special rules in our abstract interpreter.
Having identified a complete sequence of instructions that
all operate on operands of type PyFloat_Type, we can replace all instructions of this sequence with optimized derivatives directly operating on native machine float numbers.

Figure 1: Speculatively staged interpreter optimization using
multi-level quickening.
3.3

Putting It All Together

Figure 1 shows, in a general form, how speculative staging
of interpreter optimizations works. The first part of our technique requires speculatively staging optimized interpreter
instructions at interpreter compile-time. In Figure 1, the enclosing shaded shape highlights these staged instructions. We
systematically derive these optimized interpreter instructions
from the original interpreter instructions. The second part of
our technique requires run-time information and concerts the
speculatively staged interpreter instructions such that optimized interpretation preserves semantics.
The interpreter starts out executing instructions belonging
to its original instruction set (see 0 in Figure 1). During
execution, the interpreter can capture type feedback by rewriting itself to optimized instruction derivatives: Figure 1 shows
0
this in step 1 , where instruction Ij:π
replaces the more
generic instruction Ij , thereby capturing the type information
π at offset j. The next step, 2 , propagates the captured
type information π to a complete sequence of instructions,
starting with instruction S and terminating in instruction E.
We use an abstract interpreter to identify candidate sequences
operating on the same type. Once identified, 3 of Figure 1
illustrates how we rewrite a complete instruction sequence
S, . . . , E to optimized instruction derivatives S 00 , . . . , E 00 .
This third instruction set operates on unboxed native machine
data types, and therefore requires generic ways to handle
(un-)boxing of objects of type π (cf. mπ and m−1
π ), as well as
converting data to and from the operand stack (cf. cτ and c−1
τ ).
All instructions circled by the dotted line of Figure 1 are instruction derivatives that we speculatively stage at interpreter
compile-time.

4.

End Instr.
POP_JUMP_IF_FALSE
POP_JUMP_IF_TRUE
RETURN_VALUE
STORE_FAST
YIELD_VALUE

4.1

Implementation

Deriving Optimized Python Interpreter
Instructions

In this section we present details to implement speculative
staging of optimized interpreter instructions in a methodological fashion. First, we are going describe the functions we
use to (un-)box Python objects and the conventions we use to
pass operand data on the mixed-value operand stack. We treat
arithmetic operations for Python’s integers, floating point
and complex numbers, though our technique is not limited

This section presents implementation details of how we use
speculative staging of optimized interpreter instructions to
substantially optimize execution of a Python 3 series interpreter. This interpreter is an implementation vehicle that we
use to demonstrate concrete instantiations of our general
optimization framework. We use an example sequence of
7

2013/07/12

Original Python
bytecode
LOAD_FAST
LOAD_FAST
LOAD_FAST
BINARY_MULT
LOAD_FAST
LOAD_FAST
BINARY_MULT
BINARY_ADD
LOAD_FAST
LOAD_FAST
BINARY_MULT
BINARY_ADD
LOAD_CONST
BINARY_POWER
BINARY_MULT
STORE_FAST

After Type Feedback
via Quickening
LOAD_FAST
LOAD_FAST
LOAD_FAST
INCA_FLOAT_MULT
LOAD_FAST
LOAD_FAST
INCA_FLOAT_MULT
INCA_FLOAT_ADD
LOAD_FAST
LOAD_FAST
INCA_FLOAT_MULT
INCA_FLOAT_ADD
LOAD_CONST
INCA_FLOAT_POWER
INCA_FLOAT_MULT
STORE_FAST

INCA

F

F
F
F

F

F

After Type Propagation
and Quickening
NAMA_FLOAT_LOAD_FAST
NAMA_FLOAT_LOAD_FAST
NAMA_FLOAT_LOAD_FAST
NAMA_FLOAT_MULT
NAMA_FLOAT_LOAD_FAST
NAMA_FLOAT_LOAD_FAST
NAMA_FLOAT_MULT
NAMA_FLOAT_ADD
NAMA_FLOAT_LOAD_FAST
NAMA_FLOAT_LOAD_FAST
NAMA_FLOAT_MULT
NAMA_FLOAT_ADD
NAMA_FLOAT_LOAD_CONST
NAMA_FLOAT_POWER
NAMA_FLOAT_MULT
NAMA_FLOAT_STORE_FAST

Figure 2: Concrete Python bytecode example and its step-wise optimization using multi-level quickening for concerting at
run-time.
LOAD_FAST

LOAD_FAST LOAD_FAST

INCA_FLOAT_MULT

Floating Point Numbers Floating point numbers are represented by the C struct PyFloat_Type.

LOAD_FAST

INCA_FLOAT_MULT

LOAD_FAST

INCA_FLOAT_ADD

LOAD_FAST

mPyFloat Type := PyFloat AS DOUBLE : PyFloatObject∗ → double

INCA_FLOAT_MULT
INCA_FLOAT_ADD

LOAD_FAST

m−1
PyFloat Type := PyFloat FromDouble : double → PyFloatObject∗

LOAD_CONST

INCA_FLOAT_POWER

Complex Numbers Complex numbers are represented by
the C struct PyComplex_Type, but we cannot directly
access a native machine representation of its data. This is
due to a complex number consisting of two parts, a real and
an imaginary part:

INCA_FLOAT_MULT
STORE_FAST

Figure 3: Data-flow of the sequence of instructions of Figure 2
in abstract interpretation. Arrows indicate direction of type
propagation.

1
2
3
4

Furthermore, we need to know something about the internals
of the PyComplex_Type implementation to access the native
machine data. Internally, Python uses a similar struct to
complex_t (Py_complex) to hold the separate parts and we
can access the data via ((PyComplexObject*)x)->cval.

to these. Second, we illustrate the derivation steps in concrete Python code examples—while in theory we could use
a partial evaluator to generate the derivatives, the manual
implementation effort is so low that it does not justify using
a partial evaluator.
4.1.1

typedef struct {
double real ;
double imag ;
} complex_t ;

mPyComplex Type := PyComplexObject∗ → (double, double)
m−1
PyComplex Type := (double, double) → PyComplexObject∗

(Un-)boxing Python Objects

The Python interpreter supports uniform procedures to box
and unbox Python objects to native machine numbers, and
we just briefly mention which functions to use and give their
type.

4.1.2

Operand Stack Data Passing Convention

Across all three instruction sets, instructions pass operands
using the operand stack. The original Python instruction set
operates exclusively on Python objects which reside on the
heap, i.e., the operand stack passes pointers to the heap, of
Integers Python represents its unbounded range integers by
type uint64 on a 64-bit machine. The lowest level instruction
the C struct PyLong_Type.
set operates on native machine data, i.e., we need to map
native machine data types to the existing operand stack. We
mPyLong Type := PyLong AS LONG : PyLongObject∗ → int64 rely on C constructs of explicit casts and unions to ensure
m−1
PyLong Type := PyLong FROM LONG : int64 → PyLongObject∗ that we attach the proper semantics to the bits passed around.
8

2013/07/12

Passing Integers Naturally, it is trivial in C to support
passing integers on the mixed operand stack: we simply
cast from the signed integer representation to the unsigned
representation used for pointers, too.

3
4
5
6
7
8
9

cint64 (o : int64) := (uint64)o

10

c−1
int64 (o : uint64) := (int64)o

The resolving procedure of dynamic types is not visible and
resides in the PyNumber_Subtract function. The resolving
is much more complicated than our simplified interpreter
substrate suggests, in particular due to the presence of ad-hoc
polymorphism and inheritance. In our simplified interpreter
substrate all dynamic types were known at compile-time and
we could use pattern matching to express semantics properly
and exhaustively. For languages such as Python, this is in
general not possible. For example, one could use operator
overloading for integers to perform subtraction, or perform
the traditional integer addition by inheriting from the system’s
integers.

Passing Floats To pass floating point numbers, we need to
avoid implicit casting a C compiler would insert when using
a cast from double to uint64. A solution to circumvent this,
is to use a C union that allows to change the semantics the
compiler attaches to a set of bits. More precisely, we use the
following union:
1

typedef union { uint64 word ; double dbl ; } map_t ;

Map_t allows us to change the semantics by using the corresponding field identifier and thus suffices to map doubles to
uint64 representation in a transparent and portable fashion.

First-level Quickening By fixing operands v and w to the
type PyFloat_Type, we can derive the following optimized
instruction derivative, expressed as INCA_FLOAT_SUBTRACT.

cdouble (o : double) := (map t m; m.dbl = o; (uint64)m.word)
c−1
double (o : uint64) := (map t m; m.word = o; m.dbl)
1

Passing Complex Numbers As previously described, we
represent a complex number using two double numbers.
Therefore, we can reuse the functions that map floating point
numbers:

2
3
4
5
6
7

ccomplex (o : complex t) := (cdouble (o.real), cdouble (o.imag))
c−1
complex (i : uint64, r : uint64) := (complex t c;

8
9
10
11

−1
c.real = c−1
double (r); c.imag = cdouble (i))

12
13

But, the operand stack passing convention alone does not suffice since passing native machine complex numbers requires
two stack slots instead of one. Consequently, we double the
operand stack size such that all instruction operands on the
stack could be two-part complex numbers. Since the abstract
interpreter identifies whole sequences of instructions, there is
always a termination instruction that boxes the two-part double numbers into a PyComplexObject instance. As a result,
this temporary use of two operand stack slots is completely
transparent to all predecessor instructions of the sequence as
well as all successor instructions of the sequence.
4.1.3

Example Instructions

Second-level Quickening The second-level quickening
step optimizes sequences of interpreter instructions to directly modify native machine data. Hence, we move the
required type check to the corresponding load instruction:
1
2

Original Python Instruction The following program excerpt shows Python’s original implementation of the arithmetic subtraction operation:
2

case I N C A _ F L O A T _ S U B T R A C T :
w = POP ();
v = TOP ();
if (!T(v , w , PyFloat_Type )) {
/* misspeculation , g e n e r a l i z e */
goto B I N A R Y _ S U B T R A C T _ M I S S ;
} // if
x = PyFloat_Type . tp_as_number - > nb_sub (v , w );
Py_DECREF ( w );
Py_DECREF ( v );
SET_TOP ( x );
if ( x != NULL ) DISPATCH ();
goto on_error ;

On lines four to seven, we see what happens on misspeculation. After the type check (stylized by symbol T) fails,
we resume execution of the general instruction that INCA_FLOAT_SUBTRACT derives from, BINARY_SUBTRACT in this
case. We change the implementation of BINARY_SUBTRACT
to add another label that we can use for resuming correct
execution.
Directly calling nb_sub on PyFloat_Type optimizes the
complex resolving of dynamic typing hinted at before.
Furthermore, this type-specialized instruction derivative
illustrates that we can in fact infer that both operands as well
as the result (x) are of type PyFloat_Type.

The previous section contains all details necessary to inductively construct all optimized interpreter instructions that
modify native machine data types. In this section, we give
concrete Python interpreter instruction implementation examples for completeness.

1

v = TOP ();
BINARY_SUBTRACT_MISS :
x = P y N u m b e r _ S u b t r a c t (v , w );
Py_DECREF ( v );
Py_DECREF ( w );
SET_TOP ( x );
if ( x != NULL ) DISPATCH ();
goto on_error ;

3
4
5
6
7
8

case BINARY_SUBTR A CT :
w = POP ();

9

case N A M A _ F L O A T _ L O A D _ F A S T :
PyObject * x = fastlocals [ oparg ];
map_t result ;
if (T(x , PyFloat_Type ))
result . dbl = P y F l o a t _ A S _ D O U B L E ( x );
else /* misspeculation , g e n e r a l i z e */
PUSH ( result . word );
NEXT_INSTR ();

2013/07/12

5.

The corresponding floating point subtract operation need not
perform any type checks, reference counting, or (un-)boxing
operations anymore:
1
2
3
4
5
6
7
8
9
10
11

Evaluation

Systems and Procedure We ran the benchmarks on an Intel
Nehalem i7-920 based system running at a frequency of 2.67
GHz, on Linux kernel version 3.0.0-26 and gcc version
4.6.1. To minimize perturbations by third party systems,
we take the following precautions. First, we disable Intel’s
Turbo Boost [28] feature to avoid frequency scaling based on
unpublished, proprietary heuristics. Second, we use nice -n
-20 to minimize operating system scheduler effects. Third,
we use 30 repetitions for each pairing of a benchmark with
an interpreter to get stable results; we report the geometric
mean of these repetitions, thereby minimizing bias towards
outliers.

case N A M A _ F L O AT _ S U B T R A C T :
w = POP ();
v = TOP ();
{
map_t s , t ;
s . word = ( uint64 ) v ;
t . word = ( uint64 ) w ;
s . dbl -= t . dbl ;
SET_TOP ( s . word );
DISPATCH ();
}

Both of the native floating point interpreter instructions
make use of the map_t union as previously explained to avoid
implicit conversions as emitted by the compiler.
In general, the type-specific load instructions have to
validate all assumptions needed to manipulate unboxed native
machine data. For example, integers in Python 3 are by
default unbounded, i.e., they can exceed native machine
bounds. As a result, we modify the corresponding integer
load instruction to check whether it is still safe to unbox
the integer. However, it is worth noting that these are only
implementation limitations, as for example we could expand
this technique to use two machine words and perform a 128bit addition because we already doubled the stack size to
accommodate complex numbers.

Benchmarks We use several benchmarks from the computer language benchmarks game [22]. This is due to the
following reasons. First, since we are using a Python 3 series interpreter, we cannot use programs written for Python 2
to measure performance. Unfortunately, many popular third
party libraries and frameworks, such as Django, twisted, etc.
have not released versions of their software officially supporting Python 3. Compatibility concerns aside, the Python
community has no commonly agreed upon comprehensive
set of benchmarks identified to assess Python performance.
Second, some popular libraries have custom C code modules
that perform computations. Effectively, benchmarking these
programs corresponds to measuring time not spent in the
interpreter, and therefore would skew the results in the wrong
direction. Instead, we use the following benchmarks that
stress raw interpreter performance: binarytrees, fannkuch,
fasta, mandelbrot, nbody, and spectralnorm.
Finally, we rely on those benchmarks because they allow
comparison with other implementations, such as PyPy. PyPy
officially only supports Python 2, but since none of those
benchmarks use Python 3 specifics—with the notable exception of fannkuch, which required minor changes—we run
the identical programs under PyPy. This may sound like a
contradiction, but is in fact only possible with the chosen set
of programs and cannot in general be expected to hold for
other programs.

Implementation Remarks The first-level quickening step
has already been explored in 2010 by Brunthaler [7, 8], and
we used his publicly available implementation [9] as a basis
for ours. In the remainder of this paper, we refer to the original
interpreter as INCA (an abbreviation for inline caching), and
the modified interpreter that supports the new optimizations
as MLQ, which is short for multi-level quickening.
We use a simple code generator written in Python that
generates the C code for all instructions of the Python interpreter. We run our code generator as a pre-compile step
when compiling the interpreter, and rely on the existing build
infrastructure to build the interpreter. In consequence, all of
the instruction derivatives speculatively added to the interpreter and available for concerting at run-time; sidestepping
dynamic code generation altogether.
We provide templates of the C instructions using the
language of the Mako template engine [2]. The semantics of
all instruction derivatives is essentially identical, e.g., adding
numbers, which is why derivative instructions are merely
optimized copies operating on specialized structures or types.
Hence, these templates capture all essential details and help
keeping redundancy at bay. If we were to create a domainspecific language for generating interpreters, similar to the
VMgen/Tiger [10, 21] project, we could express the derivative
relationship for instructions, thereby reducing the costs for
creating these templates. The next section provides lines-ofcode data regarding our interpreter implementation generator
(see Section 5.2).

5.1

Benchmark Results

Figure 4 shows the performance results obtained on our test
system. We report a maximum speedup by up to a factor
of 4.222 over the CPython 3.2.3 interpreter using switch
dispatch. INCA itself improves performance by up to a factor
of 1.7362. As a result, the MLQ system improves upon the
previous maximum speedups by 143%.
PyPy Comparison Even though our speculatively staged
MLQ interpreter is no match in comparison to the multi-year,
multi-person effort that went into the PyPy implementation
(see implementation measurements in the discussion in Section 5.3), we want to give a realistic perspective of the potential of MLQ interpretation. Therefore, we evaluated the
10

2013/07/12

Interpreter

4

Speedup over switch−dispatch

Threaded Code
INCA

3.5

MLQ

3
2.5
2
1.75
1.5
1.25
1.1
1

0
0
0
0
0
0
0
0
0
0
0
2
4
6
9
0
00
00
20
30
40
50
00
00
00
40
50
60
00
s1
s1
s1
ch
h1
00
00
50 brot
rot lbrot y 100 y 150 y 50 orm orm orm orm
ree ytree ytree nkuc nnku a 10 a 15
t
a
b
l
l
t
y
d
n
n
n
n
s
e
e
e
t
t
l
l
l
l
o
fa
ar
ar
ar
fa
fan
nd
nd
nd nbod nbod
fas
fas
nb ectra ectra ectra ectra
bin
bin
bin
ma
ma
ma
sp
sp
sp
sp

Benchmark

Figure 4: Detailed speedups per benchmark normalized by the CPython 3.2.3 interpreter using switch-dispatch.
Benchmark

PyPy 1.9

MLQ

PyPy
MLQ

binarytrees
fannkuch
fasta
mandelbrot
nbody
spectralnorm

3.2031 ×
8.2245 ×
13.4537 ×
6.3224 ×
12.3592 ×
3.5563 ×

1.8334 ×
1.5240 ×
1.6906 ×
1.9699 ×
2.0639 ×
4.0412 ×

1.7471
5.2884
7.9579
3.2095
5.9883
0.8800

machine data instead of boxed objects—we can take full advantage of its benefits: determinism and space-efficiency [15].
5.2

Interpreter Data

We rely on David Wheeler’s sloccount utility [44] to measure lines of code. For calculating the number of interpreter
instructions, we use a regular expression to select the beginning of the instructions and wc -l to count their occurrences.

Table 2: Speedups of PyPy 1.9 and our MLQ system normalized by the CPython 3.2.3 interpreter using switch-dispatch.

Instruction-Set Extension The CPython 3.2.3 interpreter
has 100 interpreter instructions spanning 1283 lines of code.
The INCA instruction set of the INCA interpreter adds another
53 instructions to the interpreter, totaling 3050 lines of code
(i.e., a plus of 138% or 1767 lines of code). NAMA itself
requires additional 134 interpreter instructions adding another
1240 lines of code (increase by 41% over INCA). We adapted
the existing Python code generator of the INCA system to
generate the NAMA instruction derivatives’ C implementation.
The original code generator has 2225 lines of Python code,
where 1700 lines of code just reflect the type structure code
extracted from the C structs of Python objects via gdb.
The required changes were about 600 lines of Python code,
resulting in the updated code generator having 2646 lines of
Python code. The INCA code generator uses 2225 lines of C
code templates. To support the NAMA instruction set, we added
another 1255 lines of templatized C code—giving 3480 lines
of template code in total. In addition to this, our abstract
interpreter identifying eligible sequences requires around 400
lines of C code.

performance against PyPy version 1.9 [40]. Note that the
times we measured include start-up and warm-up times for
PyPy; since it is not clear at which point in time the benefits
of JIT compilation are visible.
Table 2 lists the geometric mean of speedups per benchmark that we measured on our Intel Nehalem system. During
our experiment we also measured overall memory consumption and report that our system uses considerably less memory
at run-time: PyPy uses about 20 MB, whereas our MLQ interpreter uses less than 7 MB. This is primarily due to the
systems using different memory management techniques:
MLQ uses CPython’s standard reference counting, whereas
PyPy offers several state-of-the-art garbage collectors, such
as a semi-space copying collector and a generational garbage
collector. Surprisingly, we find that using a more powerful
memory management technique does not automatically translate to higher performance. Since MLQ is particularly effective
at eliminating the overhead of reference counting—reducing
required reference count operations, as well as using native-

Portability As we have briefly mentioned before, our speculative staging leverages the existing backend of the ahead-oftime compiler that is used to compile the interpreter. There11

2013/07/12

Interpreter
Python 3.2.3/switch-dispatch
Python 3.2.3/threaded code
MLQ Python interpreter

Binary Size
(bytes)
2,135,412
2,147,745
2,259,616

computes 25,991, and for the jit directory 83,435 lines of
Python code. The reduction between the 100kLOC of PyPy
and the 6.5kLOC of MLQ is by a factor of almost 17×. This
is a testament to the ease-of-implementation property of interpreters, and also of purely interpretative optimizations in
general.

Increase
(kB) (%)
0 0.0
12 0.6
121 5.8

Table 3: MLQ binary size increase without debug information
on Intel Nehalem i7-920.

6.

Partial Evaluation In 1996, Leone and Lee [31] present
their implementation of an optimizing ML compiler that
relies on run-time feedback. Interestingly, they mention the
basic idea for our system:

fore, our technique is portable by construction, i.e., since we
implemented our optimized derivatives in C, the interpreter
is as portable as any other C program. We confirm this by
compiling the optimized interpreter on a PowerPC system.
This did not require changing a single line of code.

It is possible to pre-compile several alternative templates for the same code sequence and choose between
them at run time, but to our knowledge this has never
been attempted in practice.

Space Requirements Table 3 presents the effect of implementing our speculatively staged MLQ Python interpreter on
the binary size of the executable. We see that going from
a switch-based interpreter to a threaded code interpreter requires additional 12 kB of space. Finally, we see that adding
two additional instruction sets to our Python interpreter requires less than 110 kB of additional space (when discounting
the space requirement from threaded code).
5.3

Related Work

Substituting “interpreter instructions”—or derivatives, as
we frequently refer to them—for the term “templates” in
the quote, reveals the striking similarity. In addition, both
approaches leverage the compiler back-end of the aheadof-time compiler assembling the run-time system—in our
case the interpreter. This approach therefore automatically
supports all target architectures of the base-compiler and
hence there is no need for building a custom back-end.
In similar vein to Leone and Lee, other researchers addressed the prohibitive latency requirements of dynamic compilation [12, 13, 18, 25, 36] by leveraging ideas from partial
evaluation. While we take inspiration from these prior results,
we address the latency problem superimposed by dynamic
code generation by avoiding it altogether. Instead, we speculate on the likelihood of the interpreter using certain kinds
of types and derive optimized instructions for them. At runtime, we rely on our novel procedure of concerting these
optimized derivatives via abstract interpretation driven multilevel quickening. That being said, since these approaches are
orthogonal, we believe that there are further advancements
to be had by combining these approaches. For example ‘C,
or the recently introduced Terra/Lua [17], could be used to
either stage the optimized derivatives inside of the interpreter
source code, or generate the necessary derivatives at run-time,
thereby eliminating the speculation part.
The initial optimization potential of partial evaluation
applied to interpreters goes back to Futamura in 1971 [23].
But, prior work has repeatedly revisited this specific problem.
In particular, Thibault et al. [43] analyze the performance
potential of partially evaluated interpreters and report a
speedup of up to four times for bytecode interpreters. This
result is intimately related to our work, in particular since
they note that partial evaluation primarily targets instruction
dispatch when optimizing interpreters—similar to the first
Futamura projection. In 2009, Brunthaler established that
instruction dispatch is not a major performance bottleneck
for our class of interpreters [6]. Instead, our approach targets

Discussion

The most obvious take-away from Figure 4 is that there
is clearly a varying optimization potential when using our
optimization. Upon close investigation, we found that this is
due to our minimal set of eligible start and end instructions
(see Table 1). For example, there are other candidates for
start instructions that we do not currently support, such as
LOAD_ATTR, LOAD_NAME, LOAD_GLOBAL, LOAD_DEREF. In
consequence, expanding the abstract interpreter to cover
more cases, i.e., more instructions and more types, will
improve performance even further. Spectralnorm performs
best, because our abstract interpreter finds that all of the
instructions of its most frequently executed function (eval_A) can be optimized.
Finally, we were surprised about the performance comparison with PyPy. First, it is striking that we outperform PyPy
1.9 on the spectralnorm benchmark. Since we include startup and warm-up times, we decided to investigate whether this
affects our result. We timed successive runs with higher argument numbers (1000, 1500, 2000, and 4000) and verified that
our interpreter maintains its performance advantage. Besides
this surprising result, we think that the performance improvement of our interpreter lays a strong foundation for further
optimizations. For example, we believe that implementing
additional instruction-dispatch based optimizations, such as
superinstructions [19, 39] or selective inlining [37], should
have a substantial performance impact.
Second, we report that the interpreter data from Section 5.2
compares favorably with PyPy, too. Using sloccount on
the pypy directory on branch version-1.9 gives the following results. For the interpreter directory, sloccount
12

2013/07/12

forms PyPy by up to 14% on the spectralnorm benchmark,
and requires substantially less implementation effort.

known bottlenecks in instruction implementation: dynamic
typing, reference counting operations, and modifying boxed
value representations.
Glück and Jørgensen also connect interpreters with partial
evaluation [24], but as a means to optimize results obtained
by applying partial evaluation. Our technique should achieve
similar results, but since it is speculative in nature, it does not
need information of the actual program P that is interpreted,
which is also a difference between our work and Thibault et
al. [43].

Miscellaneous Prior research addressed the importance
of directly operating on unboxed data [32, 35]. There are
certain similarities, e.g., Leroy’s use of the wrap and unwrap
operators are related to our (un-)boxing functions, and there
exist similar concerns in how to represent bits in a uniform
fashion. The primary difference to the present work is that
we apply this to a different language, Python, which has a
different sets of constraints and is dynamically typed.
In 1998, Shields et al. [42] address overhead in dynamic
typing via staged type inference. This is an interesting approach, but it is unclear if or how efficient this technique
scales to Python-like languages. Our technique is much simpler, but we believe it could very well benefit of a staged
inference step.

Interpreter Optimization The most closely related work in
optimizing high-level interpreters is due to Brunthaler [7,
8]. In fact, the first-level quickening step to capture type
feedback goes back to the discovery by Brunthaler, and we
have compared his publicly available system against our
new technique. In addition to the second-level quickening
that targets the overheads incurred by using boxed object
representations, we also describe a principled approach to
using partial evaluation for deriving instructions.

7.

Conclusions

We present a general theory and framework to optimize interpreters for high-level languages such as JavaScript, Python,
and Ruby. Traditional optimization techniques such as aheadof-time compilation and partial evaluation only have limited
success in optimizing the performance of these languages.
This is why implementers usually resort to the expensive
implementation of dynamic compilers—evidenced by the
substantial industry efforts on optimizing JavaScript. Our
technique preserves interpreter characteristics, such as portability and ease of implementation, while at the same time
enabling substantial performance speedups.
This important speedup is enabled by peeling off layers
of redundant complexity that interpreters conservatively reexecute instead of capitalizing on the “dynamic locality of
type usage”—almost three decades after Deutsch and Schiffman described how to leverage this locality for great benefit.
We capitalize on the observed locality by speculatively staging optimized interpreter instruction derivatives and concerting them at run-time.
First, we describe how speculation allows us to decouple
the partial evaluation from any concrete program. This enables a principled approach to deriving the implementation of
optimized interpreter instruction derivatives by speculating
on types the interpreter will encounter with a high likelihood.
Second, we present a new technique of concerting optimized interpreter instructions at run-time. At the core, we
use a multi-level quickening technique that enables us to optimize untyped instructions operating on boxed objects down
to typed instructions operating on native machine data.
From a practical perspective, our implementation and
evaluation of the Python interpreter confirms that there is
a huge untapped performance potential waiting to be set
free. Regarding the implementation, we were surprised how
easy it was to provide optimized instruction derivatives
even without automated support by partial evaluation. The
evaluation indicates that our technique is competitive with

Just-in-time compilers Type feedback has a long and successful history in just-in-time compilation. In 1994, Hölzle
and Ungar [26, 27] discuss how the compiler uses type feedback to inline frequently dispatched calls in a subsequent
compilation run. This reduces function call overhead and
leads to a speedup by up to a factor of 1.7. In general, subsequent research gave rise to adaptive optimization in just-intime compilers [1]. Our approach is similar, except that we
use type feedback for optimizing the interpreter.
In 2012, there has been work on “repurposed JIT compilers,” or RJITs, which take an existing just-in-time compiler for a statically typed programming language and add
support for a dynamically typed programming language on
top [11, 29]. This approach is interesting, because it tries to
leverage an existing just-in-time compilation infrastructure
to enable efficient execution of higher abstraction-level programming languages—similar to what has been described
earlier in 2009 by Bolz et al. [5] and Yermolovich et al. [46],
but more invasive. Unfortunately, the RJIT work is unaware
of recent advances in optimizing interpreters, and therefore
misses some important optimization opportunities available
to a repurposed just-in-time compiler. Würthinger et al. [45]
found that obtaining information from the interpreter has
substantial potential to optimize JIT compilation, and we anticipate that this is going to have major impact on the future
of dynamic language implementation.
Regarding traditional just-in-time compilers, Python nowadays only has one mature project: PyPy [41]. PyPy follows a
trace-based JIT compilation strategy and achieves substantial
speedups over standard CPython. However, PyPy has downsides, too: because its internals differ from CPython, it is not
compatible with many third party modules written in C. Our
comparison to PyPy finds that it is a much more sophisticated
system offering class-leading performance on some of our
benchmarks. Surprisingly, we find that our technique outper13

2013/07/12

a dynamic compiler w.r.t. performance and implementation
effort: besides the speedups by a factor of up to 4.222, we
report a reduction in implementation effort by about 17×.

[11] J. G. Castanos, D. Edelsohn, K. Ishizaki, P. Nagpurkar,
T. Nakatani, T. Ogasawara, and P. Wu. On the benefits and
pitfalls of extending a statically typed language jit compiler
for dynamic scripting languages. In Proceedings of the 27th
ACM SIGPLAN Conference on Object Oriented Programming:
Systems, Languages, and Applications, Tucson, AZ, USA, October 21-25, 2012 (OOPSLA ’12), pages 195–212, 2012. doi:
http://doi.acm.org/10.1145/2384616.2384631.

References
[1] J. Aycock. A brief history of just-in-time. ACM Computing
Surveys, 35(2):97–113, 2003. ISSN 0360-0300. doi: http:
//doi.acm.org/10.1145/857076.857077.
[2] M. Bayer.
Mako, April 2013.
makotemplates.org.

[12] C. Chambers. Staged compilation. In Proceedings of the ACM
SIGPLAN Workshop on Partial Evaluation and SemanticsBased Program Manipulation, Portland, OR, USA, January
14-15, 2002 (PEPM ’02), pages 1–8, 2002. doi: http://doi.acm.
org/10.1145/503032.503045.

URL http://www.

[3] J. R. Bell. Threaded code. Communications of the ACM, 16
(6):370–372, 1973. ISSN 0001-0782. doi: http://doi.acm.org/
10.1145/362248.362270.

[13] C. Consel and F. Noël. A General Approach for Run-Time Specialization and its Application to C. In POPL ’96 [38], pages
145–156. doi: http://doi.acm.org/10.1145/237721.237767.

[4] M. Berndl, B. Vitale, M. Zaleski, and A. D. Brown. Context
threading: A flexible and efficient dispatch technique for virtual machine interpreters. In Proceedings of the 3rd IEEE /
ACM International Symposium on Code Generation and Optimization, San Jose, CA, USA, March 20-23, 2005 (CGO ’05),
pages 15–26, 2005.

[14] E. H. Debaere and J. M. van Campenhout. Interpretation and
instruction path coprocessing. Computer systems. MIT Press,
1990. ISBN 978-0-262-04107-2.
[15] L. P. Deutsch and D. G. Bobrow. An efficient, incremental,
automatic garbage collector. Communications of the ACM, 19
(9):522–526, 1976. ISSN 0001-0782. doi: http://doi.acm.org/
10.1145/360336.360345.

[5] C. F. Bolz, A. Cuni, M. Fijałkowski, and A. Rigo. Tracing
the meta-level: PyPy’s tracing JIT compiler. In Proceedings
of the 4th Workshop on the Implementation, Compilation,
Optimization of Object-Oriented Languages and Programming
Systems (ICOOOLPS ’09), Lecture Notes in Computer Science,
pages 18–25. Springer, 2009. ISBN 978-3-642-03012-3. doi:
http://doi.acm.org/10.1145/1565824.1565827.

[16] L. P. Deutsch and A. M. Schiffman. Efficient implementation of the Smalltalk-80 system. In Proceedings of the SIGPLAN ’84 Symposium on Principles of Programming Languages (POPL ’84), pages 297–302, New York, NY, USA,
1984. ACM. ISBN 0-89791-125-3. doi: http://doi.acm.org/10.
1145/800017.800542.

[6] S. Brunthaler. Virtual-machine abstraction and optimization
techniques. In Proceedings of the 4th International Workshop
on Bytecode Semantics, Verification, Analysis and Transformation, York, United Kingdom, March 29, 2009 (BYTECODE ’09),
volume 253(5) of Electronic Notes in Theoretical Computer
Science, pages 3–14, Amsterdam, The Netherlands, December
2009. Elsevier. doi: http://dx.doi.org/10.1016/j.entcs.2009.11.
011.

[17] Z. DeVito, J. Hegarty, A. Aiken, P. Hanrahan, and J. Vitek.
Terra: a multi-stage language for high-performance computing. In Proceedings of the ACM SIGPLAN Conference on
Programming Language Design and Implementation, Seattle,
WA, USA, June 16-22, 2013 (PLDI ’13), pages 105–116, 2013.
doi: http://doi.acm.org/10.1145/2462156.2462166.
[18] D. R. Engler, W. C. Hsieh, and M. F. Kaashoek. ‘C: A
Language for High-Level, Efficient, and Machine-Independent
Dynamic Code Generation. In POPL ’96 [38], pages 131–144.
doi: http://doi.acm.org/10.1145/237721.237765.

[7] S. Brunthaler. Inline caching meets quickening. In Proceedings
of the 24th European Conference on Object-Oriented Programming, Maribor, Slovenia, June 21-25, 2010 (ECOOP ’10), volume 6183/2010 of Lecture Notes in Computer Science, pages
429–451. Springer, 2010. ISBN 978-3-642-03012-3. doi:
http://dx.doi.org/10.1007/978-3-642-03013-0.

[19] M. A. Ertl and D. Gregg. The structure and performance of
efficient interpreters. Journal of Instruction-Level Parallelism,
5:1–25, November 2003.

[8] S. Brunthaler. Efficient interpretation using quickening. In
Proceedings of the 6th Symposium on Dynamic Languages,
Reno, NV, USA, October 18, 2010 (DLS ’10), pages 1–14, New
York, NY, USA, 2010. ACM Press. ISBN 978-3-642-03012-3.
doi: http://dx.doi.org/10.1007/978-3-642-03013-0.

[20] M. A. Ertl and D. Gregg. Combining stack caching with dynamic superinstructions. In Proceedings of the 2004 Workshop
on Interpreters, Virtual Machines and Emulators (IVME ’04),
pages 7–14, New York, NY, USA, 2004. ACM. ISBN 1-58113909-8. doi: http://doi.acm.org/10.1145/1059579.1059583.

[9] S. Brunthaler. Python quickening based optimizations for
cpython 3.3a0, 2012. URL http://www.ics.uci.edu/
~sbruntha/pydev.html.
[10] K. Casey, D. Gregg, and M. A. Ertl. Tiger – an interpreter
generation tool. In Proceedings of the 14th International
Conference on Compiler Construction, Edinburgh, United
Kingdom, April 4-8, 2005 (CC ’05), volume 3443/2005 of
Lecture Notes in Computer Science, pages 246–249. Springer,
2005. ISBN 3-540-25411-0. doi: http://dx.doi.org/10.1007/
978-3-540-31985-6 18.

[21] M. A. Ertl, D. Gregg, A. Krall, and B. Paysan. Vmgen: a
generator of efficient virtual machine interpreters. Software
Practice & Experience, 32:265–294, March 2002. ISSN 00380644. doi: 10.1002/spe.434. URL http://portal.acm.
org/citation.cfm?id=776235.776238.
[22] B. Fulgham. The computer language benchmarks game, 2013.
URL http://shootout.alioth.debian.org/.
[23] Y. Futamura.
Partial Evaluation of Computation
Process–An Approach to a Compiler-Compiler.
Sys-

14

2013/07/12

tems.Computers.Controls, 2(5):45–50, 1971.

Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture, in Cambridge, UK, September 1991, pages 636–666, 1991. ISBN
3-540-54396-1. doi: http://dl.acm.org/citation.cfm?id=645420.
652528.

[24] R. Glück and J. Jørgensen. Generating Optimizing Specializers.
In Proceedings of the IEEE Computer Society International
Conference on Computer Languages, Toulouse, France, May
16-19, 1994 (ICCL ’94), pages 183–194, 1994.

[36] M. Philipose, C. Chambers, and S. J. Eggers. Towards Automatic Construction of Staged Compilers. In Proceedings
of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, OR, USA, January 16-18, 2002 (POPL ’02), pages 113–125, 2002. doi:
http://doi.acm.org/10.1145/503272.503284.

[25] B. Grant, M. Mock, M. Philipose, C. Chambers, and S. J.
Eggers. Annotation-Directed Run-Time Specialization in C.
In Proceedings of the ACM SIGPLAN Workshop on Partial
Evaluation and Semantics-Based Program Manipulation, Amsterdam, The Netherlands, June 12-13, 1997 (PEPM ’97),
pages 163–178, 1997. doi: http://doi.acm.org/10.1145/258993.
259016.

[37] I. Piumarta and F. Riccardi. Optimizing direct threaded code
by selective inlining. In Proceedings of the ACM SIGPLAN
Conference on Programming Language Design and Implementation, Montréal, QC, Canada, June 17-19, 1998 (PLDI ’98),
pages 291–300, New York, NY, USA, 1998. ACM. ISBN 089791-987-4. doi: http://doi.acm.org/10.1145/277650.277743.

[26] U. Hölzle. Adaptive Optimization for SELF: Reconciling
High Performance with Exploratory Programming. PhD thesis,
Stanford University, Stanford, CA, USA, 1994.
[27] U. Hölzle and D. Ungar. Optimizing dynamically-dispatched
calls with run-time type feedback. In Proceedings of the
ACM SIGPLAN Conference on Programming Language Design
and Implementation, Orlando, FL, USA, June 20-24, 1994
(PLDI ’94), pages 326–336, 1994. ISBN 0-89791-662-X. doi:
http://doi.acm.org/10.1145/178243.178478.

[38] POPL ’96. Proceedings of the 23rd ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages, St. Petersburg Beach, FL, USA, January 21-24, 1996 (POPL ’96),
1996.
[39] T. A. Proebsting. Optimizing an ANSI c interpreter with
superoperators. In Proceedings of the 22nd ACM SIGPLANSIGACT Symposium on Principles of Programming Languages,
San Francisco, CA, USA, January 23-25, 1995 (POPL ’95),
pages 322–332, 1995. doi: http://doi.acm.org/10.1145/199448.
199526.

[28] Intel. Intel turbo boost technology – on-demand processor performance, 2012. URL http://www.intel.com/
content/www/us/en/architecture-and-technology/
turbo-boost/turbo-boost-technology.html.
[29] K. Ishizaki, T. Ogasawara, J. G. Castanos, P. Nagpurkar,
D. Edelsohn, and T. Nakatani. Adding dynamically-typed
language support to a statically-typed language compiler: Performance evaluation, analysis, and tradeoffs. In Proceedings of the 8th ACM SIGPLAN International Conference on
Virtual Execution Environments, London, United Kingdom,
March 3-4, 2012 (VEE ’12), pages 169–180, 2012. doi:
http://doi.acm.org/10.1145/2151024.2151047.

[40] PyPy. The PyPy project, 2013. URL http://pypy.org/.
[41] A. Rigo and S. Pedroni. PyPy’s approach to virtual machine construction. In Proceedings of the 21st ACM SIGPLAN Conference on Object Oriented Programming: Systems, Languages, and Applications, Portland, OR, USA, October 22-26, 2006 (OOPSLA ’06), pages 944–953, 2006. doi:
http://doi.acm.org/10.1145/1176617.1176753. OOPSLA Companion.

[30] N. D. Jones, C. K. Gomard, and P. Sestoft. Partial evaluation
and automatic program generation. Prentice Hall international
series in computer science. Prentice Hall, 1993. ISBN 978-013-020249-9.

[42] M. Shields, T. Sheard, and S. L. Peyton Jones. Dynamic
Typing as Staged Type Inference. In Proceedings of the
25th ACM SIGPLAN-SIGACT Symposium on Principles of
Programming Languages, San Diego, CA, USA, January 19-21,
1998 (POPL ’98), pages 289–302, 1998. doi: http://doi.acm.
org/10.1145/268946.268970.

[31] P. Lee and M. Leone. Optimizing ML with run-time code generation. In Proceedings of the ACM SIGPLAN Conference on
Programming Language Design and Implementation, Philadephia, PA, USA, May 21-24, 1996 (PLDI ’96), pages 540–553,
1996. doi: http://doi.acm.org/10.1145/989393.989448.

[43] S. Thibault, C. Consel, J. L. Lawall, R. Marlet, and G. Muller.
Static and Dynamic Program Compilation by Interpreter
Specialization. Higher-Order and Symbolic Computation,
13(3):161–178, 2000. ISSN 1388-3690. doi: 10.1023/A:
1010078412711.

[32] X. Leroy. Unboxed Objects and Polymorphic Typing. In
Proceedings of the 196h ACM SIGPLAN-SIGACT Symposium
on Principles of Programming Languages, Albuquerque, NM,
USA, January 19-22, 1992 (POPL ’92), pages 177–188, 1992.
doi: http://doi.acm.org/10.1145/143165.143205.

[44] D. Wheeler. sloccount, May 2010.
dwheeler.com/sloccount/.

[33] X. Leroy. Java bytecode verification: Algorithms and formalizations. Journal of Automated Reasoning, 30(3-4):235–269,
2003. ISSN 0168-7433. doi: http://dx.doi.org/10.1023/A:
1025055424017.

URL http://www.

[45] T. Würthinger, A. Wöß, L. Stadler, G. Duboscq, D. Simon, and
C. Wimmer. Self-optimizing AST interpreters. In Proceedings
of the 8th Symposium on Dynamic Languages, Tucson, AZ,
USA, October 22, 2012 (DLS ’12), pages 73–82, 2012. doi:
http://doi.acm.org/10.1145/2384577.2384587.

[34] T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, Boston, MA, USA, first edition,
1996.

[46] A. Yermolovich, C. Wimmer, and M. Franz. Optimization
of dynamic languages using hierarchical layering of virtual
machines. In Proceedings of the 5th Symposium on Dynamic

[35] S. L. Peyton Jones and J. Launchbury. Unboxed Values as
First Class Citizens in a Non-Strict Functional Language. In

15

2013/07/12

Languages, Orlando, FL, USA, October 26, 2009 (DLS ’09),
pages 79–88, New York, NY, USA, 2009. ACM. ISBN
978-1-60558-769-1. doi: http://doi.acm.org/10.1145/1640134.
1640147.

16

2013/07/12

