Ph.D. Alumni: Mathew Zaleski

Reference:

Mathew Zaleski
YETI: a GraduallY Extensible Trace Interpreter
Ph.D. Thesis, Department of Computer Science, University of Toronto, Toronto, Canada, 2008.
Primary supervisor: Prof. Angela Demke Brown

Supervisor(s):

Angela Demke Brown (primary)
Michael Stumm

Download Thesis:

PDF

Abstract:

The implementation of new programming languages benefits from interpretation because it is simple, flexible and portable. The only downside is speed of execution, as there remains a large performance gap between even efficient interpreters and systems that include a just-in-time (JIT) compiler. Augmenting an interpreter with a JIT, however, is not a small task. Today, Java JITs are typically method-based. To compile whole methods, the JIT must re-implement much functionality already provided by the interpreter, leading to a “big bang” development effort before the JIT can be deployed. Adding a JIT to an interpreter would be easier if we could more gradually shift from dispatching virtual instructions bodies implemented for the interpreter to running instructions compiled into native code by the JIT.

We show that virtual instructions implemented as lightweight callable routines can form the basis for a very efficient interpreter. Our new technique, interpreted traces, identifies hot paths, or traces, as a virtual program is interpreted. By exploiting the way traces predict branch destinations our technique markedly reduces branch mispredictions caused by dispatch. Interpreted traces are a high-performance technique, running about 25% faster than direct threading. We show that interpreted traces are a good starting point for a trace-based JIT. We extend our interpreter so traces may contain a mixture of compiled code for some virtual instructions and calls to virtual instruction bodies for others. By compiling about 50 integer and object virtual instructions to machine code we improve performance by about 30% over interpreted traces, running about twice as fast as the direct threaded system with which we started.

Keywords:

Dynamic optimization, interpretation, branch prediction

BibTeX:

@phdthesis(Zaleski-PhD08,
    author = {Mathew Zaleski},
    title = {YETI: a GraduallY Extensible Trace Interpreter},
    school = {Department of Computer Science, University of Toronto},
    address = {Toronto, Canada},
    supervisors = {Angela Demke Brown (primary), Michael Stumm},
    month = {August},
    year = {2008},
    keywords = {Dynamic optimization, interpretation, branch prediction}
)