skip to content

After a trace finishes, why does the sweep phase's cost grow with total heap size while copying survivors does not?

level: middleimportance: must knowfreq 58%

answer

  1. two denominators, not one
  2. who pays for the dead blocks
  3. rebuilding a free list needs every block
  4. references followed versus addresses walked
  5. sweep linear in heap, copy linear in live

basics

~20 s

Sweeping walks every block in address order, live and dead alike, to rebuild the free list, so its cost tracks heap size. Evacuation follows references and copies only survivors, so its cost tracks the live set, not the garbage.

solid answer

~50 s

A tracing collection charges each phase against one of two quantities: the **live set** (bytes reachable when the trace ends) or the **heap** (every byte the collector manages). Marking follows references, so it is charged for the living. Sweeping does the opposite walk — it steps through the heap in address order, inspects every block's mark bit, clears the marks on live blocks and threads unmarked ones onto a free list — so it is charged for the whole heap, and a mostly-live heap costs it about what a mostly-dead heap of the same size costs. Evacuation into a second space follows references too: it copies survivors and abandons everything else in one bulk step, so more garbage does not make it slower. Sweeping can be made lazy, paid a block at a time during allocation, but that defers and amortises the same work rather than removing it.

code

pseudocode · 10 lines
pseudocode
block = start_of_heap
while block < end_of_heap:
    next = block + size_of(block)        # header read, live or dead
    if marked(block):
        unmark(block)                    # clear for the next cycle
    else:
        add_to_free_list(block)
        if next is on the free list:
            coalesce(block, next)
    block = next

go deeper

for a junior

Hold on to the shape: some phases follow references and some walk memory in address order. The first is charged for what is alive, the second for how big the region is.

for a middle

Be able to explain why the sweep has to look at live blocks at all — it reads each block's size to find the next one and clears marks for the next cycle — and why that makes its cost independent of how much garbage there is.

for a senior

Reason about a real heap: state what happens to mark time, sweep time and evacuation time when the region is enlarged but the live set is unchanged, and say which of those actually showed up in your measurements.

for a principal

The interesting trade is that the cheap-per-cycle finishing move and the cheap-overall one differ: sweeping wins on constant factor, evacuation wins on the denominator, and which you fund depends on the survivor share you expect to see across the whole fleet.

## The two quantities a collection can be charged against Every phase of a tracing collection is charged against one of two quantities: - **The live set** — the bytes still reachable from the roots at the instant the trace ends. - **The heap** — every byte of the region the collector manages, live and dead together. The garbage is simply the difference between the two. Asking whether a phase is expensive is really asking which of those two it walks. A phase that **follows references** walks the live set. A phase that **walks memory in address order** walks the heap. That one distinction explains almost every cost claim made about tracing collectors, and it is the thing an interviewer is listening for. ## Marking is charged for the living The trace starts at the roots and follows every reference it finds, marking each object it reaches. It never reads a dead object, because no reference to one exists — having no reference to it is what makes it dead. So marking cost rises with the number and size of reachable objects and with how many references they hold, and it does **not** rise when the program produces more garbage. Double the garbage while holding the live set fixed and the mark phase does exactly the same work. ## Sweeping is charged for the whole heap Sweeping runs after marking and does the opposite kind of walk. It steps through the heap in address order, block by block, asking of each one whether its mark is set: 1. If the block is marked, the sweep clears the mark so the next cycle starts from a clean slate, and steps past it. 2. If it is unmarked, the block is garbage: it is threaded onto a free list and merged with an adjacent free block where one exists. 3. Either way the walk must step *past* the block, which means it must read the block's size header — so live blocks are visited too, even though nothing is reclaimed from them. That is why sweep cost tracks the size of the heap rather than the amount of garbage in it. Two heaps of the same size, one 5% live and one 80% live, cost a sweep roughly the same. Enlarging the heap while holding the live set fixed makes each sweep longer even though each mark stays exactly as long as before. Two refinements are worth knowing: - Keeping marks in a **side bitmap** rather than in object headers makes the scan denser and cheaper per byte, but it is still a scan of the whole heap. - **Lazy sweeping** hands the free-list rebuild to the allocator, which sweeps the next span only when it needs memory from it. This moves the cost out of the collection and spreads it across allocation; the same blocks are still visited. ## Evacuation is charged for the living again A collector that finishes by copying does not sweep at all. It walks reachable objects, copies each into reserved space, leaves a redirect behind for references that still point at the old location, and then abandons the whole vacated space in a single bulk step — no per-object work for anything dead. Its price is paid in space, not time: the reserve has to be able to hold every survivor in the worst case, so at any moment only part of the reserved capacity is usable. It also gives up the heap's original address order, which is a real cost for programs whose access pattern followed that order. ## Side by side | finishing move | what it walks | cost tracks | extra space | heap left as | | --- | --- | --- | --- | --- | | sweep | every block, in address order | heap size | mark bits only | survivors in place, holes between them | | sliding compaction | the heap once for new addresses, then the live objects | heap size **and** live set | a forwarding word or side table | survivors packed together | | semispace copying | reachable objects only | live set | room for every survivor elsewhere | survivors packed in the other space | ## Reading this off one batch job's heap Picture a nightly batch job's heap as an address line at the instant its trace finishes, with live blocks shaded: - If 5% of it is shaded, a sweep is charged for 100% of the line while an evacuation is charged for the 5%. - If 80% is shaded, the two converge, and the evacuation's reserve looks much less affordable. - Give the same job twice the heap and the same live set: every mark costs the same, every sweep costs twice as much, every evacuation costs the same. - "Cheap per cycle" is not "cheap overall" — how often cycles run is a separate trade from what one cycle costs. ## What an interviewer listens for - Naming the denominator explicitly: heap size for the sweep, live set for the mark and the copy. - Knowing that the sweep visits live blocks too, and why it must. - Not claiming that more garbage slows an evacuation down. - Saying out loud that the copy's saving is bought with reserved space.

  • If sweeping is charged for the whole heap, why is it still the cheapest way for many collectors to finish?
    Because the per-byte constant is tiny: the walk is sequential, touches a size header and a mark bit, and moves nothing. Nothing has to be copied and no reference anywhere has to be rewritten. A heap-sized walk with a very small constant often beats a live-set-sized walk that copies bytes and fixes up every pointer into them.
  • Does lazy sweeping change the total work a cycle costs?
    No — it changes when the work is paid, not how much there is. The same blocks are still examined and threaded onto free lists; the allocator does it a span at a time when it needs memory from that span. It shortens the collection itself and spreads the same cost across the program's allocations.
  • Which quantity does the cost of enumerating roots track?
    Neither of the two main ones: it tracks the number of root slots — the call-stack frames, register contents, global slots and native handles that must be examined before tracing can start. It is usually small next to both the heap walk and the live-set walk, but it is the part that cannot be made proportional to either.

saying these in an interview costs you the question

  • Says a sweep visits only the dead blocks
  • Claims a copying collection slows down as garbage grows
  • Thinks marking cost scales with heap size rather than live data
  • Believes a larger heap makes every phase of a cycle cheaper
  • Assumes lazy sweeping removes the work instead of deferring it