Online profiling and feedback-directed optimization of Java

The dynamic nature of the Java™ programming language presents a number of challenges for Java Virtual Machine (JVM) implementations. Constructs such as dynamic class loading and reflection make traditional whole program analysis and optimization difficult, or even impossible; however, Java's dynamic execution environment also presents a potential performance advantage over the traditional static compilation model: the ability to perform feedback-directed optimizations, where profiling information is collected at runtime and used to tailor the optimization decisions that are made.; Although previous work has shown that feedback-directed optimizations can substantially improve program performance, most of these systems used offline profiles collected using a separate training run. Performing profiling and optimization online during the same run is an attractive approach because it avoids the need for a separate training run. Unfortunately, the overhead of collecting online profiles is often a problem, and is one of the main reasons why today's JVM's perform only limited forms of feedback-directed optimizations.; The first contribution of this thesis is a new technique called an instrumentation sampling framework, a mechanism that allows previously expensive instrumentation to be executed with low overhead. The instrumentation sampling framework is designed as an automatic code transformation that takes instrumented code as input, and produces a modified version of the code that collects a similar profile, but executes with low overhead. We implemented and evaluated our framework in the Jikes Research Virtual Machine; our results demonstrate that the sampling framework effectively reduces the overhead of several types of instrumentation while having only a minimal effect on the accuracy of the profiles collected.; The second contribution of this thesis is the design and implementation of an on-line system that uses instrumentation sampling to drive feedback-directed optimizations and improve the performance of Java programs. Our implementation is built on top of the general adaptive optimization architecture of the Jikes RVM. Our system collects intra-procedural edge profiles using the instrumentation sampling framework and uses the resulting profiles to drive four feedback-directed optimizations. Our empirical evaluation demonstrates that our online approach can improve the performance of long-running programs without degrading the performance of short-running programs.