skip to content

When a copying or sliding-compaction collector relocates a live object, where is its new address recorded so references can be rewritten?

level: seniorimportance: nice to knowfreq 30%

answer

  1. the mapping has to live somewhere
  2. stale references arrive at the old place
  3. the abandoned copy is free real estate
  4. an object still in place still needs its header
  5. compute addresses before rewriting references

basics

~20 s

An evacuating collector writes a forwarding address over the abandoned original, so any reference still pointing at the old location finds the redirect. A sliding collector cannot overwrite an object it has not moved yet, so it computes new addresses into a side word or table in a separate pass first.

solid answer

~40 s

Moving an object invalidates every reference to it, so the collector needs a mapping from old address to new one until the last reference is rewritten. When the object is **copied** to a different space, the original is dead the instant the copy exists, so its first words can be scribbled over with the new address plus a flag — the cheapest possible mapping, stored exactly where a stale reference will look. When the object is **slid** within the same space, that trick is unavailable: the object is still in place and still needs its own header, so the new address goes into a reserved word or a side table computed in a preliminary pass. That ordering is why a sliding finish needs extra passes: compute addresses, rewrite references, then move.

code

pseudocode · 15 lines
pseudocode
function evacuate(ref):
    if is_forwarded(ref):
        return forwarding_address(ref)   # second reference: reuse the copy
    new = allocate_in_destination(size_of(ref))
    copy_bytes(ref, new)
    set_forwarding_address(ref, new)     # written over the abandoned original
    return new

for each root r:
    r = evacuate(r)
scan = start_of_destination
while scan < top_of_destination:        # objects copied so far, in order
    for each reference field f in object_at(scan):
        f = evacuate(f)
    scan = scan + size_of(object_at(scan))

go deeper

for a junior

The idea to hold on to is that moving an object breaks every reference to it, so the collector must leave a trail from the old address to the new one until all of them are fixed.

for a middle

Explain why the redirect is written at the old location rather than the new one, and why an already-moved object must be recognisable so a shared object is copied exactly once.

for a senior

Be ready to account for the passes: why a sliding finish must compute every new address before it rewrites anything, and what that ordering costs against a single-pass evacuation.

for a principal

The trade is a permanent per-object word or side table against extra traversals, and above both sits the harder constraint that a moving finish is only available at all where every reference into the heap can be enumerated.

## What moving an object breaks A reference is an address. Move the object and every reference holding that address now points at memory the object has left. A moving collector therefore owes two things: a **mapping** from each survivor's old address to its new one, and a guarantee that **every** reference is rewritten before the program runs again. The mapping has to live somewhere, and where it lives is what separates the two moving finishes. ## The forwarding address A forwarding address is the new location of a moved object, recorded where a stale reference will look for it — at the old address. Two properties make it valuable: - It is a **redirect, not a lookup**: a reference already holding the old address reads the redirect directly, with no table search. - It **deduplicates the copy**: an object with many references into it is copied once, because the second reference to reach it finds the mark and takes the recorded address instead of copying again. ## Why the copy path may scribble on the original In an evacuating finish the destination is a different space from the source. The moment the bytes are copied, the original is not merely unreferenced — it is in a region the collector is about to abandon in bulk. Its contents can therefore be destroyed freely, and the natural thing to destroy them with is the forwarding address itself, written over the first word or the header, with a flag bit marking the slot as a redirect rather than a live object. The cost is a word that already existed and is about to be thrown away. ## Why the sliding path cannot A sliding finish packs the survivors downwards **inside the same space**. Consider an object that has not yet moved: its header still describes it, and the walk still needs that header to find the object after it. Overwriting it would destroy information the collector is still using, and the destination may overlap the source. So the address has to be kept elsewhere, and the classic schemes do one of two things: 1. **A reserved word per live object** (or a side table keyed by address) filled in by a preliminary pass that walks the heap in address order, accumulating the running total of surviving bytes to compute where each survivor will land. 2. **Threading**: temporarily reversing each reference chain so that the pointers into an object are linked through the object's own header, then unthreading them once the destination is known — which trades the extra word for two more traversals. Either way the order is forced: 1. Compute the new address of every survivor. 2. Rewrite every reference — from roots and from the fields of live objects — to the computed address. 3. Move the bytes. That ordering, not the byte-copying, is why sliding compaction makes more passes over the heap than an evacuation does for the same survivors. ## What each approach costs | approach | where the mapping lives | extra space | passes over the heap | | --- | --- | --- | --- | | evacuation to another space | over the abandoned original | none beyond the destination reserve | one walk of the live objects | | sliding with a forwarding word | a reserved word or side table per survivor | one word per live object, or a table | address pass, rewrite pass, move pass | | sliding with threading | in the reference chains themselves | none per object | extra traversals to thread and unthread | ## Traps worth naming - **The redirect does not go in the copy.** Recording where the object came from helps nobody: stale references hold the old address and will never read the new object's header. - **The mapping is not permanent.** It is valid only for the cycle that created it. Once every reference has been rewritten, the old locations are meaningless and the space holding them is reclaimed. - **References the collector cannot rewrite defeat the scheme.** Any address held somewhere the collector does not enumerate cannot be corrected, which is a hard constraint on any moving finish. - **A flag is required, not optional.** Without a bit distinguishing "this slot is a redirect" from "this slot is an object header", the collector cannot tell a forwarded object from an un-forwarded one, and it would copy shared objects twice.

  • Why does an evacuating collector need a flag bit as well as the address?
    Because the slot it writes into previously held an object header, and the collector has to be able to tell the two apart. The flag says "what follows is a redirect, not an object". Without it, the second reference reaching a shared object could not know the object had already been copied, and it would be copied again — producing two copies and splitting the program's view of one object.
  • What happens if some reference to a moved object is never rewritten?
    It keeps pointing at the old location, which is either a redirect slot or, once the space is reused, arbitrary bytes. Reading through it gives corruption rather than a clean failure. This is why any moving finish is only sound if the collector can enumerate every reference into the heap, roots included.
  • How long does a forwarding address stay valid?
    Only for the cycle that wrote it. It exists to redirect references during the rewriting work, and once every reference has been corrected there is nothing left that holds the old address. The space holding the redirects is then reclaimed in bulk, and the next cycle starts with no mapping at all.

A forwarding address is the note left in the old flat's letterbox, not in the new one: people arrive holding the old address, so the redirect has to be waiting where they arrive.

saying these in an interview costs you the question

  • Thinks the forwarding address is written into the new copy
  • Says a sliding collector can overwrite an object before it moves
  • Believes forwarding addresses persist across collection cycles
  • Claims a shared object is copied once per reference to it
  • Assumes no flag is needed to spot an already-moved object