home · mobile · calendar · colloquia · 1998-1999 · 

Colloquium - Chilimbi

Cache-Conscious Data Structures
University of Wisconsin - Madison

In this talk I will show that cache-conscious pointer structure layout can improve the performance of real programs by up to 30-40%. I will outline a wide variety of techniques for laying out pointer structures in languages such as C, C++, and Java. These include completely automatic techniques that require no programmer assistance or source code modification.

I will discuss one such technique -- cache-conscious reorganization using copying garbage collection that co-locates objects with high temporal affinity in the same cache block -- in detail. Measurements show that this technique reduces cache miss rates by 21-42%, and improves program performance by 14-37% over a conventional copying algorithm (Cheney). In addition it outperforms an algorithm (Wilson-Lam-Moher) designed to improve locality at the page level by 18-31%, indicating that improving locality at the page level is not necessarily beneficial at the cache level.

Finally, for structures comparable in size to a cache block, structure splitting can increase the number of hot fields that can be placed in a cache block. In five Java programs, structure splitting reduced cache miss rates 10-27% and improved performance 6-18% beyond the benefits of cache-conscious reorganization.

Hosted by Richard Byrd.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)