Improving program locality on-the-fly

As increases in processor speed continue to outpace increases in cache and memory speed, programs are losing more performance to poor locality. Object-oriented languages exacerbate this problem by adopting new features such as just-in-time (JIT) compilation, dynamic class loading, and many small methods. However, they provide significant software engineering benefits and have become enormously popular. Solutions that bridge the memory gap will combine good performance with fast software development. We found although unique features of object-oriented languages, such as automatic memory management, dynamic compilation, and runtime monitoring systems, generate performance overhead, they also provide new opportunities for online optimizations which are not exploited by previous work. In this thesis, we take advantage of these opportunities with new approaches that improve data and instruction locality at runtime with low overhead. To improve data locality, we first implement a new dynamic, low overhead, online class analysis to find data locality. Our algorithm detects hot fields for hot objects and then reorders the objects according to their heat on-the-fly in a copying generational collector. The overall time variation between static orderings can be up to 25% and there is no consistent winner. In contrast, our new dynamic class reordering always matches or improves over the best static ordering since its history-based copying order tunes memory layout to program traversal. To improve instruction locality, we develop two schemes for improving instruction locality in a Java Virtual Machine environment. We first describes a partial code reordering system, which reduces the program instruction working set and cache conflict misses with extremely low overhead. We then present a code management system that uses dynamic profiling to reorder all JITcompiled code to improve instruction locality with novel efficient algorithms. Both systems show that the VM can dynamically improve instruction locality with little overhead. These results indicate that the VM layer for modern languages are not just a cost-to-be-borne, but instead open up a new class of optimizations for monitoring and improving data and instruction locality, and code quality. Thus these results point to a future of programming languages that are robust, dependable, and high performance.