A batch job's heap is 95% garbage when its trace ends: which finishing move — sweep, sliding compaction or semispace copying — costs least?
answer
- count who pays for the dead
- five per cent versus one hundred
- the cheapest move buys space with time
- compaction is charged on both axes
- survivor share is the flip condition
basics
~20 sSemispace copying, because it touches only the 5% that survives and abandons the rest in one step. Its price is reserved space able to hold every survivor. A sweep is charged for the whole heap; sliding compaction adds address-computing and pointer-rewriting passes on top of marking.
solid answer
~40 sWith a live share that small, copying is the cheapest finish: it copies the survivors into reserved space, leaves a redirect at each abandoned original, and reclaims everything else by declaring the vacated space free — no per-object work for 95% of the heap. A sweep does the opposite walk and is charged for all of it, because it must step past every block to read its size and clear marks. Sliding compaction is charged for both: a heap-order pass to compute each survivor's new address, then passes to rewrite references and move the bytes. What copying buys with time it pays in space — capacity has to exist elsewhere for every survivor, so the usable share of reserved memory is roughly half. The ranking inverts as the live share climbs.
go deeper
Remember the shape of the answer: a move that only touches what survives is cheap when little survives, and it pays for that with memory held in reserve.
Be able to say why a sweep cannot simply skip the dead blocks — it needs each block's size header to find the next one — and why that makes its cost independent of the garbage share.
Commit to a ranking for the heap you are given, then name the measurement that would change it: the share of the heap still live when the trace ends, sampled across real runs rather than assumed.
The judgment is whether to fund a permanent space reserve for a bargain that only appears at low survivor shares, and whether the workloads that show those shares are separable enough to be run under a different configuration.
## Drawing the heap at the instant the trace ends Picture one nightly batch job's heap as a line of addresses at the moment marking finishes, with live blocks shaded. Ninety-five per cent of the line is unshaded. Marking is already paid for — it followed references and cost what the shaded 5% costs. The only decision left is how to turn that picture into usable memory again, and there are three moves available. ## Why copying wins on this heap An evacuating finish walks the reachable objects, copies each into reserved space, and records a redirect so any later reference to the old location finds the new one. When the walk ends, every survivor is in the new space and the whole old space is garbage by construction, so it is reclaimed in a single bulk step: - Work is proportional to the shaded 5%, not to the line. Nothing dead is read, tested or listed. - The survivors land packed and in allocation order relative to each other, so the space they occupy is one contiguous run. - Reclaiming 95% of the heap costs one bookkeeping step rather than millions of block visits. On a heap this lopsided, the difference is not a constant factor to argue about — the other two moves are charged for twenty times as much material. ## What the other two are charged for **Sweeping** must step through the heap in address order. It reads each block's size header to find the next block, clears the mark on live ones, and threads unmarked ones onto a free list. There is no way to visit only the dead: finding where the dead blocks begin and end *is* the walk. So a 95%-dead heap and a 20%-dead heap of the same size cost about the same to sweep, and the survivors stay exactly where they are, with holes between them. **Sliding compaction** keeps the objects in the space they already occupy but packs them downwards. It pays on both axes: 1. A pass in address order to work out where each survivor will land once the space before it closes up. 2. A pass over the roots and over every live object's fields to rewrite each reference to the survivor's new address. 3. A pass that actually moves the bytes. That is strictly more work than the evacuation does for the same survivors, and part of it is charged against the heap rather than the live set. Its compensation is that it needs no second space: it slides into memory it already owns. ## The price copying pays Nothing here is free, and the candidate who only says "copying is cheapest" has answered half the question: - **Reserved capacity.** The destination must be able to hold every survivor in the worst case — the case where nothing is garbage. That reservation is funded permanently, including in cycles where almost everything dies, so usable memory is roughly half of reserved memory. - **Lost address order.** Survivors are relocated, and the order they land in is the order the walk discovered them, not the order the program allocated them. A program whose access pattern followed allocation order can lose locality. - **Every reference must be found.** Redirects only work if the collector can enumerate and rewrite every reference into the moved object. Non-moving finishes have no such obligation. ## Where the ranking inverts | live share when the trace ends | cheapest finish | why | | --- | --- | --- | | very low (a few per cent) | semispace copying | work tracks the tiny survivor set; the abandoned space costs nothing per object | | middling | sweep, usually | small constant per block beats copying bytes and rewriting references | | very high (most of the heap) | sweep, or compaction when the holes stop being usable | copying would move nearly everything and its reserve buys almost nothing | The flip has a simple driver: copying's bill is the survivor share, and once that share is large the collector is copying the heap to move it a short distance. The reserve, which looked like a bargain at 5% live, is then funding a copy of nearly everything. ## Defending the answer out loud - Name the denominator first: copying is charged for survivors, sweeping for the region, compaction for both. - Say what the cheap option costs — the reserve and the relocation — rather than presenting it as free. - State the condition that flips it, which is the survivor share and nothing else about the workload. - Resist "it depends": with 95% garbage stated in the question, there is a defensible answer, and the interviewer wants to hear it committed to.
- What would flip your answer away from copying?A high survivor share. Copying's bill is the live set, so once most of the heap survives each cycle it is moving nearly everything to gain little, while the reserve it demands is funding a second copy of that same nearly-everything. At that point the small per-block constant of a sweep wins, with compaction held for when the surviving layout itself has become the problem.
- Does the 95% figure change what the mark phase cost?No. Marking follows references from the roots and reads only reachable objects, so it was charged for the 5% either way. The garbage share never enters the trace's cost — it only decides which finishing move is the bargain afterwards.
- If the job runs nightly, does a long finishing phase even matter?It matters as throughput rather than responsiveness: time in the collector is time the job is not making progress, and a batch job is usually judged on total wall-clock time. The same finishing move that would be judged on its interruption in an interactive service is judged here purely on how much of the run it consumes.
saying these in an interview costs you the question
- Says the amount of garbage makes a copying finish slower
- Claims a sweep can visit only the unreachable blocks
- Presents copying as free, never mentioning the reserved space
- Thinks sliding compaction copies each survivor twice
- Assumes the cheapest finish stays cheapest at any survivor share