Data reorganization for improving cache performance of object-oriented programs

Hardware trends have increased the disparity of processor and main memory performance. Processors are becoming faster and faster while main memory performance has not kept pace. It takes many cycles to fetch data from main memory. Data caches, which are much faster and much smaller in size, bridge the performance gap to some extent by storing the most frequently accessed data items. For the best performance, it has become crucial to have in the cache almost all the data needed rather than having to access the much slower main memory.; It is a very active research area to explore both hardware and software techniques to increase the cache hit rate to achieve maximum performance. Software techniques have been quite successful in the case of regular scientific programs where data accesses are fairly predictable (linear loop nests over arrays). However, for object-oriented programs where data accesses are less predictable, there has been little success so far.; In this work we explore run-time software techniques to improve cache performance of object-oriented programs, in particular, Java. We propose a range of data layout schemes using run-time profiling and feedback. We demonstrate how the Java class loader and the garbage collector may cooperate to produce better run-time data organizations. In particular, we explore different data traversals by the garbage collector with and without using profile information. We demonstrate the effectiveness of our techniques with an implementation using the IBM Jalapeño optimizing compiler and virtual machine and the UMass garbage collection toolkit. We identify conditions when and to what extent our techniques are likely to be useful in real world object-oriented programs.