Questions: Garbage Collection Algorithms

Question 1

A program creates thousands of short-lived temporary string objects during text processing, discarding most of them within milliseconds. Which garbage collection strategy is best suited to this workload, and why?

• A. Mark-and-sweep, because it handles variable-sized objects cleanly by freeing each one individually.
• B. Generational collection, because most strings will be collected cheaply in frequent nursery passes without ever reaching the older generation.
• C. Reference counting, because each string is freed immediately when its reference count drops to zero.
• D. Mark-and-compact, because the many small freed objects would otherwise cause severe heap fragmentation.

Answer: (B)

Generational collection is designed precisely for this pattern. The generational hypothesis states that most objects die young — short-lived temporaries like these strings almost never survive a nursery collection. The nursery is small and collected frequently using copying collection, so the per-collection cost is proportional to the few survivors, not the many dead objects. Reference counting (option C) is superficially appealing but cannot reclaim cycles and incurs per-assignment overhead; it also misses the deeper efficiency gain from batching collections.

Question 2

Object A holds a reference to object B, and object B holds a reference back to A. No other live variables reference either A or B. Under which memory management approach will A and B be reclaimed without programmer intervention?

• A. Reference counting, because each object's count drops to zero when the other is freed first.
• B. Reference counting, but only if a separate cycle-detection pass is added.
• C. Any tracing garbage collector (mark-and-sweep, copying, generational), because reachability from roots determines garbage regardless of internal reference cycles.
• D. No automatic strategy can reclaim them; the programmer must break the cycle manually.

Answer: (C)

Reference counting fails on cycles: A's count is 1 (B points to it) and B's count is 1 (A points to it), so neither ever reaches zero, and both leak. Tracing collectors (mark-and-sweep, copying, generational) start from the root set — stack variables, globals, registers — and mark everything reachable by following pointer chains. Since no root reaches A or B, neither gets marked and both are collected. Reachability-from-roots is a global property that correctly identifies cyclic garbage; reference counting tracks only local pointer counts.

Question 3

Copying collection is inefficient when most objects are short-lived, because it should copy most those short-lived objects before reclaiming their space.

• T. True
• F. False

Answer: False

This is the key misconception. Copying collection only copies LIVE (reachable) objects from fromspace to tospace — dead objects are simply abandoned and their space reclaimed by swapping the roles of the two halves. If most objects are short-lived (the generational hypothesis), very few survive, and copying cost is proportional to survivors, not to all objects. A collection that sees 10,000 allocations but only 100 survivors copies only 100 objects. This is exactly why copying collection is the preferred algorithm for the nursery in generational systems.

Question 4

In generational garbage collection, write barriers are needed to track old-to-young references so that nursery collections can find all roots without scanning the entire old generation.

• T. True
• F. False

Answer: True

The nursery root set must include not only stack and global variables but also any pointers from old-generation objects into the nursery — otherwise a live young object pointed to only from old memory would appear unreachable and be incorrectly collected. Since scanning the entire old generation on every nursery collection would defeat its purpose, the runtime uses write barriers: small pieces of code executed on every pointer store that record when an old object is updated to point to a young one. These recorded pointers form a remembered set, which supplements the normal root set for nursery collections.

Question 5

Explain why copying collection's cost is proportional to what survives rather than to what dies, and why this makes it efficient for short-lived objects.

Model answer: Copying collection works by evacuating all live objects from fromspace into a fresh tospace and then treating all remaining fromspace memory as free. Dead objects are never touched — the algorithm simply abandons them by swapping the roles of the two halves. Therefore, the work done is exactly proportional to the number (and size) of live objects copied. If most objects die before collection, few survive, and the collection is cheap regardless of how many short-lived objects were allocated. This is the opposite of mark-and-sweep, which must traverse and reclaim each dead object explicitly.

The key insight is that copying collection ignores garbage rather than reclaiming it item by item. The 'cost of garbage' is zero — garbage is simply left behind in fromspace. The cost is entirely in evacuating survivors. This creates a counter-intuitive result: allocating many objects that almost immediately die is cheap for a copying collector, because it pays work only for the few that live. This property directly motivates generational collection, which concentrates copying collection in the nursery where the survivor ratio is lowest.