38
$\begingroup$

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?

$\endgroup$
19
$\begingroup$

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

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So you could argue that generational GCs are cache-friendly compared to non-generational (classical) ones? $\endgroup$ – Raphael Aug 8 '12 at 7:01
  • $\begingroup$ I would argue that the GC should be designed in an integrated way with caches & virtual memory as part of its design, which is tricky in existing architectures. however to expand on the answer-- yes generational collectors aggregate/consolodate/group the frequently used objects into contiguous memory which will be inherently more cache-compatible than other designs in which the frequently and infrequently used objects are scattered/intermixed (although the latter will still have some cache benefit). $\endgroup$ – vzn Aug 8 '12 at 14:42
  • 1
    $\begingroup$ One somewhat-tricky aspect of merging GC and caching/virtualization architectures is that such architectures generally don't care about the content of memory pages, but in a GC system they are required to. Different languages sometimes promise different GC-related features to programmers, and figuring out which features to support at an OS level may be difficult. The best approach would probably to say that each object needs to contain a pointer to a structure whose initial fields are defined by the OS, but which may be followed by language-specific data the OS wouldn't know or care about. $\endgroup$ – supercat Jun 27 '15 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.