Compare mark-compact collection with mark-sweep: what the compaction phase does, what it costs, and why a collector might still use compaction only as a fallback rather than on every cycle.
answer
- same mark phase; sweep vs slide
- compaction = destinations + move + reference fix-up
- cost ~ live data; sweep cost ~ heap size
- compaction restores bump allocation and locality
- used as the fallback when fragmentation blocks allocation
basics
~20 sBoth mark identically. Mark-sweep then adds dead space to a free list and leaves survivors in place, so the heap fragments. Mark-compact instead slides survivors together into one contiguous block and rewrites every reference to them, ending fragmented-free but paying a relocation plus pointer-fixup pass over live data.
solid answer
~60 sThe marking phase is the same: trace from roots, flag reachable objects. The phases differ in what follows. **Mark-sweep** walks the heap and hands unmarked space to a free list. Survivors never move, so no reference needs changing - but free space is left as holes, allocation must search a free list, and large contiguous requests can fail. **Mark-compact** relocates the survivors so they occupy a contiguous prefix of the space, then updates every reference that pointed to a moved object. Typical implementations need extra passes: compute each survivor's destination (often via forwarding information), move the objects, then fix all references, including those from roots. Afterwards allocation is a pointer bump again and the free space is one contiguous block. The cost profile is why compaction is often a fallback. It touches all live data - reading, writing, and fixing up - so a heap dense with long-lived objects makes it expensive, and the pause scales with live-set size. Non-moving sweeping is cheaper per cycle and preserves addresses. So collectors commonly sweep or reclaim regions normally and compact only when fragmentation actually threatens allocation - the classic "full GC" fallback.
code
text · 8 linesbefore: L . L L . . L . '.' = garbage
mark-sweep: L _ L L _ _ L _ free space = four separate 1-slot holes
-> largest allocatable block = 1 slot; free list required
mark-compact: L L L L _ _ _ _ free space = one 4-slot block
-> bump-pointer allocation restored; every reference to a
moved survivor had to be rewritten to its new addressgo deeper
State that both mark the same way, that sweeping leaves holes while compacting slides survivors together, and that compaction fixes fragmentation but has to move objects.
Add the reference fix-up requirement, the restored bump-pointer allocation, and the cost asymmetry (heap-size sweep versus live-data compaction).
Explain why compaction commonly appears as a fallback for fragmentation-driven allocation failure, and what a live-data-proportional stop-the-world pass means for pause behaviour.
Weigh address stability and native interop against fragmentation risk and allocator cost, and reason about which workloads (survival rate, allocation size distribution, latency budget) justify paying relocation continuously versus only under duress.
## Shared beginning Both algorithms determine liveness the same way: start from the roots (thread stacks, statics, native handles), traverse the reachable object graph, and mark every object found. Anything unmarked at the end is garbage. Marking cost tracks live data and graph shape. ## What sweeping does Mark-sweep walks the heap linearly and returns the space of each unmarked object to a free list, coalescing neighbouring free blocks where it can. Survivors stay exactly where they were. Nothing outside the collector needs to know a collection happened, because no address changed. The residue is fragmentation. Free memory is a distribution of hole sizes rather than one block. Allocation becomes a search, allocators grow size-class structures to keep that search cheap, and a request larger than the biggest hole fails despite a healthy total-free figure. Over a long run, fragmentation tends to worsen unless something eventually compacts. ## What compaction does Mark-compact keeps the marking phase and replaces sweeping with relocation. The canonical sliding form preserves allocation order: survivors are moved toward one end of the space so that they end up adjacent, with all free memory as a single block at the other end. Doing that requires more than a copy. The collector must: 1. **Compute destinations.** Walk the marked objects in address order, accumulating sizes, to determine where each will land. The destination is commonly recorded in a forwarding word or a side table. 2. **Move the objects.** Copy each survivor's bytes to its destination. Sliding in the right order lets a moved object overwrite space vacated by an earlier one. 3. **Fix up references.** Every reference to a moved object - from roots, from other moved objects, and from anywhere else in the runtime - must be rewritten to the new address. This is the pass people forget, and it is why moving collection requires *precise* knowledge of where references live. Afterwards, allocation is a bump pointer, locality is improved because objects allocated near each other in time are again near each other in space, and the largest-allocatable-block problem disappears. ## The cost comparison - **Work scales with live data.** Compaction reads and writes every surviving byte and touches every reference to a survivor. A heap that is 80% live is close to the worst case: nearly everything is moved for a small reclamation. - **Multiple passes.** Sliding compaction classically needs several traversals (mark, compute forwarding, move, fix up), though implementations reduce this. - **Addresses change.** Anything holding a raw address must be handled: native code via JNI needs pinning or handle indirection, and object header state such as identity hash and lock information must survive relocation. - **Pause length.** Because the pass covers the live set, stop-the-world compaction gives a pause proportional to live data - the very thing latency-sensitive systems try to bound. Mark-sweep, by contrast, pays a heap-size-proportional sweep but no relocation, and it never invalidates an address. ## Why compaction is often a fallback Many production designs use the cheap path normally and compaction only when needed: - Historical concurrent mark-sweep designs did non-moving concurrent reclamation and fell back to a stop-the-world compacting collection when fragmentation prevented allocation - a rare but very long pause. - Region-based designs sidestep the choice by evacuating regions: copying survivors out of selected regions gives compaction incrementally, with a full compacting collection reserved as a last-resort fallback. - Generational designs use copying for the young generation, where survival is low and moving is cheap, and reserve compaction of the old generation for when fragmentation genuinely bites. ## How to phrase the trade Mark-sweep buys cheap collection and address stability at the price of fragmentation and free-list allocation. Mark-compact buys contiguity, bump allocation, and better locality at the price of moving all live data and rewriting all references to it. Which is right depends on survival rate, allocation size distribution, tolerance for a long pause, and whether anything outside the collector depends on addresses staying put.
- Which phase of mark-compact is usually the most expensive, and why?The relocation plus reference fix-up work, because it touches all live data twice in effect - once to copy the bytes and once to rewrite every reference pointing at a moved object - and the reference fix-up must cover roots and the whole surviving graph. Marking is proportional to live data too, but it only reads; compaction reads, writes, and mutates references, which is why its cost dominates on heaps dense with long-lived objects.
- Why does a moving collector require precise knowledge of where references are, while a non-moving one can tolerate ambiguity?A non-moving collector only needs to decide reachability, so treating an ambiguous word (say a value on a stack that might be a reference) conservatively as a reference is safe - it merely retains an object longer than necessary. A moving collector must rewrite references, and rewriting a word that turned out to be an integer would corrupt data, so it cannot guess. That is why moving collectors depend on precise stack maps and safepoints where those maps are valid.
Mark-sweep empties random lockers along a corridor; mark-compact then shuffles every remaining occupant down to the near end so all empty lockers are together - at the price of reissuing everyone's locker number to everyone who had it written down.
saying these in an interview costs you the question
- Saying mark-compact and mark-sweep differ in how they determine liveness; the marking phase is the same.
- Forgetting the reference fix-up pass and claiming compaction is just a memory copy.
- Assuming compaction is always better because fragmentation is bad, without acknowledging that its cost scales with live data.
- Claiming compaction can be done safely without precise reference information.
- Believing free-list allocation is as cheap as bump-pointer allocation.