Introduction

The Java language [1, 2] provides a promising solution to the design of safe programs, with an application spectrum ranging from Web services to operating system components [3]. The success of Java is partly due to the fact that its basic execution model relies on the interpretation of an object-based virtual machine which is highly portable. However, the well-known tradeoff of Java's portability is the inefficiency of interpretation. Several solutions have been proposed to overcome this problem, such as just-in-time (JIT) [4, 5, 6, 7] and off-line [8, 9] bytecode compilers.

Just-in-time systems compile code to native form at runtime on demand. This approach avoids the overhead of compiling unused code, and eliminates the gap between compile time and execution time. Compiling during program execution, however, inhibits aggressive optimizations because compilation must only incur a small overhead. This is particularly important in the case of modern RISC processors for which complex analyses are required to achieve the best result. Moreover, the quality of the generated code critically relies on knowledge about the specific features of the target processor. Therefore, such compilers are not platform independent and requires a large amount of work to be ported.

Off-line compilers does not impose critical bounds on compilation time; optimizing analyses can be run as needed. They can also be platform independent, if they generate as output an intermediate language. However, in the context of Java, many applications dynamically load classes (i.e., bytecode) at run-time that limits applicability of pure off-line compilers.

In this paper, we present an approach that reconciles portability and efficiency, and preserves the ability to dynamically load bytecode. We have designed and implemented an efficient environment for the execution of Java programs, named Harissa. Harissa provides a bytecode compiler and an interpreter integrated in the runtime library. Thus, a compiled program is still able to dynamically load classes and to interpret them. Harissa's compiler translates Java bytecode to C and furthermore incorporates aggressive optimizations.

To evaluate Harissa, we have conducted an extensive experimental study aimed at comparing the various existing alternatives to execute Java programs. The contributions of our work are as follows.

• The C code produced by Harissa's compiler is more efficient than all other alternative ways of executing Java programs (that were available to us): on the Caffeine Micro-benchmarks [10], it is 5 to 140 times faster than JDK 1.0.2 interpreter, 2 to 13 times faster than the Softway Guava JIT [6] and on average 20% faster than the Microsoft JIT compiler. On real application benchmarks, such as the Javac compiler, it is 5 times faster than the JDK interpreter and 30% faster than the Toba [9] bytecode to C compiler.
• The compiler statically evaluates the stack by abstractly interpreting the bytecode and replaces stack management with variables. This optimization suppresses one of the main sources of inefficiency in Java.
• The compilation process does virtual-method call optimization based on the class hierarchy analysis (CHA) [11, 12]. On the set of programs used in our benchmarks, this analysis permit the replacement of up to 40% of virtual methods calls by simple procedure calls.
• In contrast to existing off-line compilers, the runtime system of Harissa includes an interpreter that preserves the ability of an application to dynamically load bytecode.
• Finally, we discuss the benefits and limitations of off-line compilation vs JIT compilation. Based on our experimental study, we show that, for frequently used programs, it is always more advantageous to use off-line compilation rather than JIT compilation.

The paper is organized as follows: Section 2 describes existing approaches for optimizing the execution of Java programs. Section 3 presents Harissa. Section 4 presents related work in class hierarchy analysis and existing bytecode compilers. Section 5 analyzes the performance of the code generated by Harissa's compiler on micro-benchmarks and real benchmarks, such as the Javac compiler and the Javadoc documentation generator. Section 6 concludes by describing future work and comparing JIT and off-line compilers.