Caching strategies to improve generational garbage collection in Smalltalk

by 1977- Reddy, Vimal Kodandarama

REDDY, VIMAL K. Caching strategies for improving generational garbage collection in Smalltalk. (Under the direction of Dr. Edward F. Gehringer). Cache performance of programs is becoming increasingly important as processor speeds grow faster relative to main memory. Cache misses have become a major consideration for performance of garbage collected systems. This thesis explores a caching strategy for generational garbage collectors, the most prevalent form in use, which takes advantage of large caches available to modern-day processors. A portion of the cache is chosen to reserve the youngest generation and the page-fault manager is provided certain mapping rules that remove all conflicts to the youngest generation. The strategy can be completely realized in software which makes it an attractive solution to increase garbage collection performance. This “biased” cache mapping is shown to reduce cache misses and increase overall performance in the IBM VisualAge Smalltalk system, a high quality Smalltalk implementation that employs a generational copying garbage collector. Favoring youngest generation in the mapping strategy is advantageous for the following reasons: 1. Languages like Smalltalk, where “everything” is an object, tend to allocate furiously. This is because they encourage a programming style where objects are created, used and shortly thereafter destroyed. This large number of allocations translates to initialization write misses if the allocated region is not cached. In generational heaps, all memory is allocated in the region containing youngest-generation objects. 2. A generational garbage collector focuses collection on the youngest generation, scavenging it to reclaim most garbage. It relies on empirical knowledge that most young objects die soon. This means the scavenger runs many times during a program lifetime, scanning the youngest generation for garbage. This process can lead to a large number of read and write cache misses if the youngest generation is not in cache. 3. Youngest generation objects form a major part of a program’s working set. Making them available in the cache would also improve the mutator (i.e, user program) performance, making it immune to interference from the garbage collector. 4. Given that most young objects become garbage quickly, when a garbaged object is evicted from a writeback cache, an unneccessary writeback results. Caching the youngest generation would reduce traffic to memory. We do a simulation-based study of our mapping strategies on IBM VisualAge Smalltalk, a generational copying garbage collected system. Our results show a 45% average drop in cache miss rates at the L2 level for direct-mapped caches and 15% average drop for 2 ? way set-associative caches. Caching strategies for improving generational garbage collection in Smalltalk by REDDY, VIMAL KODANDARAMA A thesis submitted to the Graduate Faculty of North Carolina State University in partial satisfaction of the requirements for the Degree of Master of Science Department of Electrical and Computer Engineering Raleigh 2003