Cache aware data layout reorganization optimization in GCC

Abstract

Many programs suffer from poor cache behavior due to poor locality of their data. We are interested in optimizations that improve data locality by changing the layout of data structures in a cache aware manner. One technique for changing the layout of a data structure is to change its high level definition (struct definitions in C and struct/class definitions in C++). There are two such transformations that we can perform on data structures: structure splitting (splitting fields into several sub-structures) and field reordering. In this paper we present our implementation of these optimizations in GCC. Our optimization consists of three main stages: Deciding if it is safe to perform the optimization; Determining how to rearrange the data records; and, applying the transformation. We measured the performance impact of our optimization and discovered that while some programs had no noticeable performance improvements, in at least one case there were significant gains in cache behavior and overall performance.