Caching strategies to improve generational garbage collection in Smalltalk
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
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 translate 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.
Advisor:Gregory T. Byrd; Edward F. Gehringer; Warren J. Jasper; Eric Rotenberg
School:North Carolina State University
School Location:USA - North Carolina
Source Type:Master's Thesis
Date of Publication:08/20/2003