Mark-sweep & mark-compact

Find the objects in use, free the rest

Your program makes objects all the time. Each object takes up some memory. When the program can no longer reach an object, its memory can be used again. The part of the JavaScript engine that frees this memory is the garbage collector, or collector for short.

This lesson shows two ways a collector can work:

• Mark-sweep: find the objects still in use, then free the rest.
• Mark-compact: do the same, then move the objects still in use close together.

A root is a value the program can always reach, such as a variable in the code that is running now. A reference is a link from one value to an object. For example, cart.items links the cart to its items.

This lesson follows Reference counting & cycles. There, the collector counted the links to each object. Two objects that linked to each other were hard to free. Marking asks a different question: can the program still reach this object, starting from a root?

Marking from roots

Marking starts at the roots. From each root, the collector follows every reference. It marks each object it reaches as live, which means still in use.

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

Line 1 makes a root object. Inside it is a cart object, and inside that is an items array. Line 2 follows the path root.cart.items[0] and prints tea. Each step along that path follows a reference. The collector follows the same links that your code does.

The name root is not what makes it a root. A value is a root because the running program, or the browser or Node around it, still holds it.

The next code is a small model of marking. Each name stands for an object. Each list holds the names that object links to.

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(","));

In plain words, line by line:

1. Line 1 makes graph. cart links to items. user, items, and oldBanner link to nothing.
2. Line 2 says the roots are cart and user.
3. Line 3 marks the roots by putting them in marked. A Set is a list that keeps each value only once.
4. Lines 4 to 6 go through each root and mark every name it links to. So items gets marked too.
5. Line 7 prints the marked names, joined with commas: cart,user,items.

oldBanner is not printed. Nothing links to it, so the program can no longer reach it.

This short loop only follows links one step away from the roots. Real objects can link many steps deep. The next model uses a worklist: a to-do list of names still to visit. It takes one name off the list, marks it, and adds that name's links to the list. It stops when the list is empty.

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

Lines 1 to 6 write the same graph over several lines. Line 7 picks cart and user as roots. Line 8 calls markGraph, which the hidden setup code defines. It sorts the marked names before it returns them, so this 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

After marking, the collector sweeps. Memory is split into slots. In this lesson, one slot holds one object. Sweeping walks through the slots one by one. It keeps the marked objects and empties every other slot.

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

Line 1 makes a heap: a list of slots. The heap is the part of memory where objects live. Line 2 marks cart and user. Line 3 goes through each slot with map. It keeps a marked name and puts null in place of any other name. It prints [ 'cart', null, 'user' ].

A free list is a list of the slot numbers that are now empty. When the program makes a new object later, the engine can put it in one of those slots.

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);

In plain words, line by line:

1. Lines 1 to 5 make a function, sweep. It takes the heap and the marked names.
2. Line 2 puts the marked names in a Set, so checking a name is quick.
3. Line 3 keeps each marked name and puts null in every other slot.
4. Line 4 returns the new heap and the free list: the numbers of the slots that hold null.
5. Line 6 makes six slots. Slots 1 and 4 are already empty. Slot 3 holds old-banner, which was not marked.
6. Line 7 sweeps, with cart, user, and items as the marked names.
7. Lines 8 and 9 print the new heap and the free list, [ 1, 3, 4 ].

This array is a small model. A real engine keeps more facts about each object, such as its size. The main idea is the same: sweeping frees memory without moving any object that is still in use.

Fragmentation

Fragmentation means the free memory is split into small gaps between objects that are in use. There can be enough free slots in total, but not enough of them side by side. A big object needs its slots side by side.

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

Line 1 lists the free slots: 1, 3, and 4. Line 2 says the new object needs three slots. Line 3 calls hasRun, which the hidden setup code defines. It checks whether three free slots sit in a row. It prints false, because slot 2 is not free.

So there are two different questions:

• How many slots are free in total? Here, three.
• What is the longest row of free slots? Here, only two: slots 3 and 4.

A big object needs the second answer to be large enough.

Try it below. The playground sweeps the same six slots as before. Press the button to stop using items, and watch the longest row of free slots.

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: moving objects together

Compaction slides the objects in use toward one end of the heap. Then all the free slots sit together at the other end, in one long row.

Moving has a cost. For each object it moves, the collector must:

• copy the object to its new slot,
• write down where the object went,
• fix every reference that still points at the old slot.

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);

In plain words, line by line:

1. Line 1 makes a heap with empty slots between cart, user, and items.
2. Line 2 calls compactWithSteps. It slides the objects to the front. It also writes each move into a forwarding table: a list of "old slot to new slot" pairs.
3. Line 3 has two pointers. Here, a pointer is a slot number that says where an object is. cartItems says slot 4 and activeUser says slot 2. updatePointers looks up each one in the forwarding table.
4. Line 4 prints the packed heap: [ 'cart', 'user', 'items', null, null, null ].
5. Line 5 prints the new pointers: { cartItems: 2, activeUser: 1 }.

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

V8 is the JavaScript engine inside Chrome and Node. It does not compact the whole heap every time. The heap is split into blocks called pages, and V8 compacts only the pages with the most gaps. On the other pages, a sweep leaves enough usable space, so V8 skips the cost of moving.

Updating pointers after a move

A forwarding table pairs each old slot with its new slot. When an object moves, the collector uses this table to fix every reference to it.

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

Line 1 says the object in slot 4 moved to slot 2. Line 2 is a pointer that still says slot 4. Line 3 looks up slot 4 in the table and prints 2.

References to one object can sit in many places:

• variables in functions that are running now,
• properties of other objects,
• the engine's own lists.

The collector fixes all of them. The forwarding table is a small model of that work. The next code puts the whole move together.

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

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]));
}

In plain words, line by line:

1. Line 1 makes a heap with gaps.
2. Line 2 makes two pointers: cartItems says slot 4 and activeUser says slot 2.
3. Line 3 compacts the heap and builds the forwarding table.
4. Line 4 fixes both pointers with the forwarding table.
5. Lines 5 and 6 print the packed heap and the fixed pointers, { cartItems: 2, activeUser: 1 }.
6. Lines 8 to 14 make the two functions, compact and updatePointers.

Your JavaScript code can never see a slot number or a memory address. So you never notice a move. Your variables keep working because the collector fixed every reference.

JavaScript lets you compare two objects with === and read their properties. It never tells you where an object sits in memory, so your code should never depend on that.

A small V8 trace

Node can print one line each time V8 collects garbage. This printout is called a trace. The code below makes many objects and then asks for a collection.

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);

In plain words, line by line:

1. Line 1 makes an empty array, keep.
2. Line 2 adds 4000 small objects to it.
3. Line 3 asks V8 to collect garbage now. globalThis.gc only exists when Node starts with the --expose-gc flag. It is for tests, not for real apps.
4. Line 4 prints app output 4000.

The lesson test runs this code with node --trace-gc --expose-gc. The --trace-gc flag tells V8 to print a line for each collection. The test checks two things:

• V8 printed Mark-Compact or Mark-sweep, the name of the collector it used.
• The program still printed app output 4000. The collection did not change the program's own result.

Practical use

Your code can't choose which collector runs, or when. What your code can do is stop holding on to objects it no longer needs.

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

Line 1 makes a cache: a Map that stores values under keys. Line 2 stores a cart under the key "cart". Line 3 deletes that entry when the cart is done. Line 4 prints 0, the number of entries left.

Deleting does not start a collection right away. It removes one path from a root to the cart. At the next collection, marking won't reach the cart, so its memory can be freed.

In a real site, first find out what keeps a big object alive. Then change the code. Common causes are:

• an event listener that is never removed,
• a timer that keeps running,
• a cache that keeps growing,
• a global variable.

The browser's memory tools can show the path from a root to an object. This path is called a retaining path.

Common misconceptions

Mark-sweep and mark-compact both start the same way: they mark the objects in use. The difference is what comes next:

• Mark-sweep frees the gaps and leaves every object where it is.
• Mark-compact moves the objects together, so the gaps join into one big free area.

Neither one fixes a memory leak on its own. A memory leak is memory your program keeps but no longer needs. If a cache, listener, timer, or global variable still reaches an object, marking will correctly keep it. First remove that link. Then the next collection can free the object.

• “Sweeping always leaves one big empty area.” It can leave many small gaps between objects.
• “Compaction changes my variable values.” No. The collector moves objects and fixes every reference, so your variables still point at the same objects.
• “Three free slots mean a three-slot object fits.” Only if the three slots are side by side.

The table compares the two collectors. Read each row as one collector, from left to right.

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 steps for every question:

1. Find the roots.
2. Mark every name the roots reach.
3. Sweep: the rest become free slots.
4. Check whether the free slots sit side by side.

Three free slots do not mean a three-slot object fits. Always check where the free slots are.

For questions about moving, remember two facts. Compaction puts the free slots in one row. The forwarding table lets the collector fix every reference. Your code sees the same object before and after the move, because JavaScript never shows you where an object sits in memory.

Key takeaways

• Marking starts at the roots and follows every reference. Each object it reaches is in use.
• Sweeping frees every slot that was not marked. The free slot numbers form a free list.
• Fragmentation means the free slots are split up by objects in use.
• Compaction moves the objects in use together, so the free slots form one long row.
• A forwarding table pairs old and new slots, so the collector can fix every reference to a moved object.

Coming next: Generational collection & the Scavenger. It uses the fact that most objects are only needed for a short time.