Explain how a copying (semi-space) garbage collection algorithm reclaims memory, why its collection cost does not depend on how much garbage there is, and what it gives up in exchange.
answer
- from-space / to-space, roles swap
- evacuate survivors, forwarding pointer prevents double copy
- dead objects never touched
- cost ~ survivors; compaction free; bump allocation
- price: reserved space + everything moves
basics
~20 sThe space is split in two. Live objects are copied from the in-use half into the empty half, references are updated to the new addresses, and the source half is then reclaimed entirely - dead objects are never touched. Cost scales with survivors only; the price is holding half the space in reserve.
solid answer
~60 sA semi-space collector divides its memory into a **from-space** (currently in use) and a **to-space** (empty reserve). Allocation in from-space is a pointer bump. When from-space fills, the collector traverses from the roots and **evacuates** each live object it reaches: copies it into to-space, writes a forwarding pointer into the old copy so any later reference to the same object resolves to the same new address, and updates the reference it came through. When the traversal completes, every live object sits packed at the start of to-space; the whole of from-space is declared free without examining it. The roles then swap. Three consequences follow. **Cost is proportional to surviving data**, not to heap size or garbage volume - dead objects cost literally nothing. **The result is compacted**, so allocation stays a bump-pointer operation and locality is good. And **half the space is idle at any moment**, which is the direct cost. That profile suits the young generation exactly, where the overwhelming majority of objects die before the first collection, so survivors are few and copying is cheap.
code
text · 13 linescopy(ref):
if from_space_object(ref).has_forwarding_pointer:
return from_space_object(ref).forwarding_pointer # already evacuated
new_addr = to_space_bump_pointer
to_space_bump_pointer += size_of(ref)
memcpy(new_addr, ref, size_of(ref))
from_space_object(ref).forwarding_pointer = new_addr # so the 2nd reference agrees
return new_addr
collect():
for r in roots: r = copy(r)
for obj in to_space: for each reference f in obj: f = copy(f) # to-space is the work queue
free(from_space); swap(from_space, to_space)go deeper
Say that live objects are copied into an empty space and the old space is then thrown away whole, so only survivors cost anything.
Add forwarding pointers and reference updating, the cost-proportional-to-survivors model, the space reserve, and why this fits the young generation.
Discuss why HotSpot uses eden plus two survivor spaces rather than a true 50/50 split, promotion to avoid endless recopying, and the pathological high-survival case.
Reason about when the space-for-time trade is right at system level - reserve size versus pause cost versus allocation-path speed - and the constraints moving objects imposes on native interop and address stability.
## The mechanism A copying collector partitions its memory into two equal halves. One, *from-space*, holds all current objects; the other, *to-space*, is kept empty. Allocation into from-space needs only a pointer and a limit: take the next N bytes, advance the pointer, and check you have not passed the limit. That is why bump-pointer allocation is often quoted as costing only a handful of instructions. When from-space is exhausted, collection begins: 1. Start from the roots - thread stacks, statics, and other references live by definition. 2. For each reference encountered, look at the object it points to. If the object has not yet been copied, copy its bytes into to-space at the current to-space bump pointer, then write a **forwarding pointer** into the original copy recording the new address. If it has already been copied, the forwarding pointer is already there. 3. Overwrite the reference that was followed with the new address. 4. Continue through the references inside the copied objects (classic implementations scan to-space itself as a work queue, so no auxiliary stack is required). 5. When no unprocessed references remain, every live object is in to-space, laid out contiguously in traversal order. 6. Declare all of from-space free - without inspecting it - and swap the roles of the two spaces. The forwarding pointer is essential and is the detail interviewers probe: without it, an object reachable through two different references would be copied twice, breaking object identity, and the two references would disagree about which object they name. ## Why the cost model is unusual There is no phase that visits dead objects. Mark-sweep visits them during sweep; mark-compact visits the heap to slide survivors; copying does neither. The collector touches exactly the live data - reading it in from-space and writing it in to-space - plus the references it must rewrite. So collection cost is proportional to *survivors*, and reclaiming a space containing a million dead objects and one survivor costs almost nothing. That is why copying pairs so naturally with the young generation: the overwhelming majority of newly allocated objects become garbage very quickly, so survivor counts are tiny relative to allocation volume, and each collection is fast. ## What it costs 1. **Space.** In the pure form, half the memory is always idle. Practical implementations soften this: HotSpot's young generation uses one eden plus two small survivor spaces, copying eden-plus-one-survivor into the other survivor, so the reserve is a small fraction rather than 50%. Objects that outlive several such cycles are promoted elsewhere instead of being copied forever. 2. **Objects move.** Every reference to a moved object must be found and rewritten, which means the collector must be able to identify all references precisely, and any native code or data structure holding a raw address must cooperate (pinning, handles, or an update protocol). Addresses are not stable, so identity hash codes and lock state must be preserved across the move. 3. **Copy cost scales with survivor size.** If survival rates are high - a workload that allocates a large, long-lived cache in a burst, for example - copying loses its advantage: it does the maximum possible work (copying nearly everything) for the minimum reward. 4. **Repeated copying of medium-lived objects.** Objects that survive but are not yet promoted may be copied on every cycle, which is why age thresholds and promotion exist. ## The comparison to keep in your head - **Mark-sweep**: no space reserve, no movement, but fragmentation and free-list allocation; sweep scales with heap size. - **Mark-compact**: no space reserve and no fragmentation, but a relocation pass plus reference fixup, with cost driven by live data and the heap walk. - **Copying**: fastest per collection when survival is low, compaction for free, bump-pointer allocation - paid for with reserved space and unconditional movement of survivors. Stating that trade in those terms, and then saying "which is why copying is applied where survival rates are lowest," is the answer an interviewer is looking for.
- What breaks if the collector omits forwarding pointers?An object reachable through two different references would be copied twice, producing two distinct copies in to-space. The two references would then point at different objects, so reference equality and mutation through one reference would no longer be visible through the other. The forwarding pointer left in the old copy is what makes the second visit resolve to the address chosen on the first.
- Under what workload does a copying collector perform worst?When survival rates are high - for example a burst that allocates a large, long-lived structure that is still fully reachable at collection time. Copying then does its maximum work, moving nearly everything, and frees almost nothing, while also consuming the reserved space. This is precisely why copying is applied to the young generation, where most objects die before the first collection, and not to a heap of long-lived data.
Moving out of a flat by carrying only what you still want into the new flat, then handing back the keys without sorting the rest. Leaving takes as long as your possessions require, regardless of how much rubbish stays behind - and you must be paying rent on the second flat.
saying these in an interview costs you the question
- Saying the collector scans or frees the dead objects in from-space; it never touches them.
- Omitting forwarding pointers and claiming references are simply updated as they are found.
- Believing copying costs scale with heap size or with the amount of garbage.
- Asserting a real JVM young generation permanently wastes 50% of memory - eden plus two small survivor spaces reduce the reserve substantially.
- Claiming a copying collector still needs a free list because of fragmentation; it produces a compacted space and bump allocation.