skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · 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.

The Department holds colloquia throughout the Fall and Spring semesters. These colloquia, open to the public, are typically held on Thursday afternoons, but sometimes occur at other times as well. If you would like to receive email notification of upcoming colloquia, subscribe to our Colloquia Mailing List. If you would like to schedule a colloquium, see Colloquium Scheduling.

Sign language interpreters are available upon request. Please contact Stephanie Morris at least five days prior to the colloquium.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:29)