Technical Report: Structure Splitting and Inheritance

The increasing gap between memory and processor performance drives the research for cache optimizations. Recently research concentrates on optimizing pointer based applications. Structure splitting is an important enabling transformation for optimizations that improve the layout of dynamic data structures. Previous work has shown the potential of structure splitting in runtime optimizations. This paper discusses issues of structure splitting applied to inheritance hierarchies of object oriented languages. Inheritance requires similar layout of compound types to simplify type casts. Structure splitting, in contrast, requires a layout that is tailored for a single type. Therefore compatibility between the split type and its super and sub-types is lost. This issue was not addressed by previous work. We explain several strategies to deal with this type compatibility issue and implement two as a compiler optimization. Our experiments show that a careful choice of the strategy is necessary, as they either increase the overhead for accessing cache-neutral data, or they can not achieve the full possible speed up for cache-critical data. Nevertheless, both approaches show considerable speed ups of our tests.