Are generational garbage collectors inherently cache-friendly?

Question

A typical generational garbage collector keeps recently allocated data in a separate memory region. In typical programs, a lot of data is short-lived, so collecting young garbage (a minor GC cycle) frequently and collecting old garbage infrequently is a good compromise between memory overhead and time spent doing GC.

Intuitively, the benefit of a generational garbage collector compared with a single-region collector should increase as the latency ratio of main memory relative to cache increases, because the data in the young region is accessed often and kept all in one place. Do experimental results corroborate this intuition?

Answer 1

Here are a few papers that talk about the cache implications of generational garbage collectors:

• Caching Considerations for Generational Garbage Collection
• The Effect of Garbage Collection on Cache Performance

From what I can gather, the primary issue is that garbage collected systems trade off space in memory to avoid up front collection. The same thing applies to cache memory. As you suggested, the things in the first generation are most likely going to be sitting in cache, and so their allocation and collection will be much faster than something in main memory, or paged out to disk. The main issue is the size of the first generation with respect to the size of your cache. If your cache fills up before the first generation does, then you start to lose those benefits as the misses start piling up.

Answer 2

There is a very tricky aspect of all garbage collectors that might be glossed over in some descriptions, and that is the "full scan" or "full collect". Periodically, randomly, intermittently they must scan all objects. generational collectors are better at postponing the full scan and minimizing its duration, but it is still required.

The generational collector will focus on what is sometimes called the "nursery" space, but it will eventually/inevitably have to collect on the "older" generation space, causing a full scan of memory.

This full scan is incompatible with almost all memory caching and (especially!) virtualization schemes in the sense that almost all memory caching/virtualization schemes will/must fail badly in any performance improvement in this case.

So the key answer to this question is how often the full scan is triggered, and how "bad" its effect is when it happens, and if it can be tolerated. this boils down to a more an application-dependent property/question.

In other words for "most" of the operation of the collector, a cache will probably help it (the cache and the "young" nursery space will generally overlap!), but there is a periodic, intermittent, eventual, inevitable, heavy, maybe even "massive" [degrading] spike in performance when the "old generation" space is full-collected and the cache "hit rate" will degrade to very bad as many objects outside of it are all fetched in a tight loop by the full scan/collect cycle. In other words, an inescapable periodic discontinuity (where statistical estimates/averages/trends of performance etc are misleading and inapplicable).

What is now emerging are some new collection systems that are designed to mesh with the underlying memory management systems (caching/virtualization). it does appear that historical approaches that completely decouple the separate systems of memory collection, caching, and virtualization will not perform as well as approaches that combine/integrate/address all three aspects together.

See eg cache aware garbage collection by Zhou and Demsky.