Mark-sweep & mark-compact

Find live objects, free the rest

A collector needs a clear question: which objects can the running program still reach? Mark-sweep marks those live objects, then frees the unmarked ones. Mark-compact also groups live objects together after finding them.

This follows Reference counting & cycles. Counting had trouble with cycles; tracing answers a different question: can a root reach this object?

Marking from roots

Start with roots such as a current variable or host-held reference. Follow each reference. Every reached object is marked live.

1const root = { cart: { items: ["tea"] } };2console.log(root.cart.items[0]);

Line 1 creates a root object, then connects it to a cart and an items array. Line 2 reads the first item through that whole path. It prints tea.

Marking is the collector phase that starts at roots and records every object it can reach. A root is not special because of its name. It is special because the running program or host still holds it.

1const graph = { cart: ["items"], user: [], items: [], oldBanner: [] };2const roots = ["cart", "user"];3const marked = new Set(roots);4for (const name of roots) {5  for (const child of graph[name]) marked.add(child);6}7console.log([...marked].join(","));

Line 1 creates four names and one reference from cart to items. Line 2 names the roots. Line 3 marks them. Lines 4 to 6 follow their children. Line 7 prints cart,user,items; oldBanner is unreachable.

1const graph = {2  cart: ["items"],3  user: [],4  items: [],5  oldBanner: [],6};7const roots = ["cart", "user"];8console.log(markGraph(graph, roots).join(","));

Line 1 writes a graph where each name has a list of references. Line 7 chooses cart and user as roots. Line 8 calls the lesson model, which repeatedly takes one name from a worklist and adds its children. It also prints cart,items,user.

1const graph = { cart: ["items"], user: [], items: [], oldBanner: [] };Run2const roots = ["cart", "user"];3const marked = new Set(roots);4for (const name of roots) {5  for (const child of graph[name]) marked.add(child);6}7console.log([...marked].join(","));

Sweeping and free lists

A free list is a list of slots that sweeping made available. It lets later allocations reuse freed space.

1const heap = ["cart", "old-banner", "user"];2const marked = new Set(["cart", "user"]);3console.log(heap.map((name) => marked.has(name) ? name : null));

Line 1 has a live cart, an old banner, and a live user. Line 2 marks only the cart and user. Line 3 replaces the unmarked banner with null, so it prints an array holding cart, null, and user.

Sweeping walks the heap representation after marking. It keeps marked entries, clears unmarked entries, and remembers the cleared positions for a later allocation.

1function sweep(heap, marked) {2  const live = new Set(marked);3  const nextHeap = heap.map((name) => live.has(name) ? name : null);4  return { heap: nextHeap, freeList: nextHeap.flatMap((name, slot) => name === null ? [slot] : []) };5}6const heap = ["cart", null, "user", "old-banner", null, "items"];7const swept = sweep(heap, ["cart", "user", "items"]);8console.log(swept.heap);9console.log(swept.freeList);

Line 1 makes six labeled slots. Line 2 lists the live names from marking. Line 3 sweeps. Lines 4 and 5 print the new heap and free slot numbers. The model frees slots 1,3,4.

There is an important limit: this array is a teaching model. Real engines store headers, object sizes, and allocator metadata. The useful idea remains the same: sweep can reuse dead space without moving live objects.

Fragmentation

Fragmentation means free space is split into small holes. The total can be large enough, while no single adjacent run is large enough.

1const freeSlots = [1, 3, 4];2const needs = 3;3console.log(hasRun(freeSlots, needs));

Line 1 lists three free positions. Line 2 says the new object needs three slots. Line 3 asks the lesson helper whether positions 1, 2, and 3 all exist. It prints false, because slot 2 is occupied.

Total free space answers “how much space exists?” The largest free run answers “what is the biggest thing that can fit right now?” Those are different questions.

function sweep(heap, marked) {
  const live = new Set(marked);
  const nextHeap = heap.map((name) => live.has(name) ? name : null);
  return { heap: nextHeap, freeList: nextHeap.flatMap((name, slot) => name === null ? [slot] : []) };
}
const heap = ["cart", null, "user", "old-banner", null, "items"];
const swept = sweep(heap, ["cart", "user", "items"]);
console.log(swept.heap);
console.log(swept.freeList);

Compaction and moving objects

Compaction slides live objects toward one end of the heap. The reward is one long free region. The cost is copying live objects and fixing every reference that used an old location.

1const heap = ["cart", null, "user", null, "items", null];2const moved = compactWithSteps(heap);3const pointers = updatePointers({ cartItems: 4, activeUser: 2 }, moved.forwarding);4console.log(moved.heap);5console.log(pointers);

Line 1 starts with holes between three live names. Line 2 calls the compacting model. Line 3 translates two model pointers with the forwarding table. Lines 4 and 5 print the packed heap and the translated pointers.

Moving a live object is not free. The collector must copy its data, record where it went, and update references before the program observes the heap again.

1function compact(heap) {Run2  const live = heap.flatMap((name, oldSlot) => name === null ? [] : [{ name, oldSlot }]);3  return { heap: [...live.map(({ name }) => name), ...Array(heap.length - live.length).fill(null)], forwarding: Object.fromEntries(live.map(({ oldSlot }, newSlot) => [oldSlot, newSlot])) };4}5function updatePointers(pointers, forwarding) {6  return Object.fromEntries(Object.entries(pointers).map(([name, slot]) => [name, forwarding[slot] ?? slot]));7}8const moved = compact(["cart", null, "user", null, "items", null]);9const updated = updatePointers({ cartItems: 4, activeUser: 2 }, moved.forwarding);10console.log(moved.heap);11console.log(updated);

V8 compacts only the pages that are most fragmented. That is one simple way to avoid paying movement cost when ordinary sweeping leaves usable space.

Updating pointers after a move

A forwarding table records an old slot and its new slot. The collector uses it to update references while moving objects.

1const forwarding = { 4: 2 };2const pointer = 4;3console.log(forwarding[pointer]);

Line 1 says that old slot 4 moved to new slot 2. Line 2 holds a pointer to the old slot. Line 3 looks up the new slot and prints 2.

A collector must update references held in stack frames, heap objects, and runtime structures. The forwarding table is a short model of that bookkeeping.

function compact(heap) {
  const live = heap.flatMap((name, oldSlot) => name === null ? [] : [{ name, oldSlot }]);
  return { heap: [...live.map(({ name }) => name), ...Array(heap.length - live.length).fill(null)], forwarding: Object.fromEntries(live.map(({ oldSlot }, newSlot) => [oldSlot, newSlot])) };
}
function updatePointers(pointers, forwarding) {
  return Object.fromEntries(Object.entries(pointers).map(([name, slot]) => [name, forwarding[slot] ?? slot]));
}
const moved = compact(["cart", null, "user", null, "items", null]);
const updated = updatePointers({ cartItems: 4, activeUser: 2 }, moved.forwarding);
console.log(moved.heap);
console.log(updated);

Line 1 makes holes. Line 2 models two references by slot number. Line 3 compacts the heap. Line 4 updates references. Lines 5 and 6 print the compact heap and correct new slots. JavaScript code can never see addresses, so this move is invisible: your variables still work because the collector updated every reference.

This is also why application code should not try to reason from an object address. JavaScript gives you object identity and properties, not an internal slot number.

A small V8 trace

Node can expose a test-only collection hook. This Node-only probe keeps application output separate from V8 trace text.

const keep = [];
for (let index = 0; index < 4000; index += 1) keep.push({ index, text: "tea".repeat(20) });
globalThis.gc();
console.log("app output", keep.length);

The test runs Node with --trace-gc --expose-gc. It checks for Mark-Compact or Mark-sweep, then confirms the program still prints app output 4000.

Practical use

You cannot choose a collector from application code. You can avoid retaining data accidentally and use memory tools when a real problem appears.

1const cache = new Map();2cache.set("cart", { items: ["tea"] });3cache.delete("cart");4console.log(cache.size);

Line 1 creates a cache. Line 2 stores a cart. Line 3 removes that entry when it is no longer needed. Line 4 prints 0. The deletion does not force collection, but it removes one path that could keep the cart reachable.

In a real site, investigate a retaining path before changing code. A long-lived listener, timer, cache, or global can be the path that keeps a large object alive.

Common misconceptions

Mark-sweep and mark-compact are not competing answers to the marking question. Both first need to know which objects are live. The difference comes after that decision: sweeping reuses holes where they are, while compaction pays to move survivors and joins the holes into one larger area.

Neither phase makes a logical memory leak disappear by magic. If a cache, listener, timer, or global still reaches an object, marking will correctly keep it. First remove the accidental retaining path; then the next collection can treat the object as unmarked.

• “Sweep always gives one big empty area.” It can leave scattered holes.
• “Compaction changes my variable values.” The collector updates internal references.
• “A free list proves a large object fits.” The slots must be adjacent.

Practice exercises

const graph = { cart: ["items"], user: [], items: [], oldBanner: [] };
const roots = ["cart", "user"];
const marked = new Set(roots);
for (const name of roots) {
  for (const child of graph[name]) marked.add(child);
}
console.log([...marked].join(","));

Check your understanding

Use the same order for every question: find the roots, mark the reachable names, sweep what remains, and then ask whether the free slots form one run. Do not jump from “three empty slots” to “a three-slot object fits” without checking their positions.

For moving questions, keep two facts together. Compaction improves the shape of free space, and forwarding information keeps every internal reference correct. JavaScript sees the same object before and after the move because its address was never part of the language contract.

Key takeaways

• Marking follows references from roots to find live objects.
• Sweeping frees unmarked slots and can build a free list.
• Fragmentation scatters free space into holes.
• Compaction makes one long free area by moving live objects.
• Forwarding information lets collectors update every moved reference.

Coming next: Generational collection & the Scavenger.