Mark-and-Sweep Algorithm in JS: Full Tutorial

A full tutorial on the mark-and-sweep garbage collection algorithm in JavaScript. Covers the mark phase, sweep phase, tri-color marking, incremental marking, compaction, fragmentation, building a mark-and-sweep simulator, and comparing with reference counting.

JavaScriptadvanced

RuneHub Team

March 4, 2026

16 min read

RuneHub Team

Mar 4, 2026

16 min read

Mark-and-sweep is the foundational garbage collection algorithm used by all modern JavaScript engines. This tutorial walks through how it works, its variants (tri-color, incremental, with compaction), and builds a working simulator to visualize the process.

For how V8 implements this, see How V8 Garbage Collector Works in JavaScript.

Basic Mark-and-Sweep

The algorithm has two phases: mark all reachable objects, then sweep (free) all unmarked objects:

javascript

class BasicGC {
  constructor() {
    this.heap = new Set();     // All allocated objects
    this.roots = new Set();    // Root references (globals, stack)
  }
 
  allocate(data) {
    const obj = {
      data,
      marked: false,
      refs: [],                // References to other objects
    };
    this.heap.add(obj);
    return obj;
  }
 
  addReference(from, to) {
    from.refs.push(to);
  }
 
  addRoot(obj) {
    this.roots.add(obj);
  }
 
  removeRoot(obj) {
    this.roots.delete(obj);
  }
 
  // MARK PHASE: traverse from roots, mark reachable objects
  mark() {
    const worklist = [...this.roots];
 
    while (worklist.length > 0) {
      const obj = worklist.pop();
 
      if (obj.marked) continue;
      obj.marked = true;
 
      // Add all referenced objects to worklist
      for (const ref of obj.refs) {
        if (!ref.marked) {
          worklist.push(ref);
        }
      }
    }
  }
 
  // SWEEP PHASE: free all unmarked objects
  sweep() {
    const collected = [];
 
    for (const obj of this.heap) {
      if (!obj.marked) {
        collected.push(obj.data);
        this.heap.delete(obj);
      } else {
        obj.marked = false; // Reset for next cycle
      }
    }
 
    return collected;
  }
 
  // Run full GC cycle
  collect() {
    this.mark();
    const freed = this.sweep();
 
    return {
      freed: freed.length,
      alive: this.heap.size,
      freedItems: freed,
    };
  }
}
 
// Demonstration
const gc = new BasicGC();
 
const a = gc.allocate("A");
const b = gc.allocate("B");
const c = gc.allocate("C");
const d = gc.allocate("D");
 
gc.addReference(a, b); // A -> B
gc.addReference(b, c); // B -> C
gc.addRoot(a);         // A is reachable
 
// D is unreachable (no path from any root)
console.log(gc.collect());
// { freed: 1, alive: 3, freedItems: ["D"] }

Tri-Color Marking

Modern engines use tri-color marking to enable incremental collection:

javascript

class TriColorGC {
  constructor() {
    this.heap = new Set();
    this.roots = new Set();
  }
 
  allocate(data) {
    const obj = {
      data,
      color: "white",    // white: unvisited, grey: in progress, black: done
      refs: [],
    };
    this.heap.add(obj);
    return obj;
  }
 
  addReference(from, to) {
    from.refs.push(to);
  }
 
  addRoot(obj) {
    this.roots.add(obj);
  }
 
  removeRoot(obj) {
    this.roots.delete(obj);
  }
 
  // Initialize: mark roots as grey
  initMarking() {
    for (const root of this.roots) {
      root.color = "grey";
    }
  }
 
  // Process one grey object (for incremental use)
  markStep() {
    let greyObj = null;
 
    for (const obj of this.heap) {
      if (obj.color === "grey") {
        greyObj = obj;
        break;
      }
    }
 
    if (!greyObj) return false; // No more grey objects
 
    // Process: mark children grey, mark self black
    for (const ref of greyObj.refs) {
      if (ref.color === "white") {
        ref.color = "grey";
      }
    }
    greyObj.color = "black";
 
    return true; // More work may remain
  }
 
  // Full mark phase
  markAll() {
    this.initMarking();
    while (this.markStep()) {
      // Continue until no grey objects remain
    }
  }
 
  sweep() {
    const collected = [];
 
    for (const obj of this.heap) {
      if (obj.color === "white") {
        collected.push(obj.data);
        this.heap.delete(obj);
      } else {
        obj.color = "white"; // Reset for next cycle
      }
    }
 
    return collected;
  }
 
  collect() {
    this.markAll();
    const freed = this.sweep();
    return { freed: freed.length, alive: this.heap.size };
  }
}

Color	Meaning	During Mark Phase
White	Not yet visited	Will be swept if still white after marking
Grey	Visited, but children not yet processed	In the worklist; children need scanning
Black	Fully processed (self and all children visited)	Known reachable; will survive

Incremental Marking

Split the mark phase into small steps interleaved with JavaScript execution:

javascript

class IncrementalGC {
  constructor() {
    this.heap = new Set();
    this.roots = new Set();
    this.greyList = [];
    this.phase = "idle"; // "idle", "marking", "sweeping"
    this.stats = { markSteps: 0, sweepSteps: 0 };
  }
 
  allocate(data) {
    const obj = { data, color: "white", refs: [] };
    this.heap.add(obj);
 
    // Write barrier: if we are in the middle of marking,
    // new objects must be grey to ensure they get scanned
    if (this.phase === "marking") {
      obj.color = "grey";
      this.greyList.push(obj);
    }
 
    return obj;
  }
 
  addReference(from, to) {
    from.refs.push(to);
 
    // Write barrier: if black object points to white object during marking,
    // mark the white object grey to prevent it from being wrongly collected
    if (this.phase === "marking" && from.color === "black" && to.color === "white") {
      to.color = "grey";
      this.greyList.push(to);
    }
  }
 
  addRoot(obj) { this.roots.add(obj); }
  removeRoot(obj) { this.roots.delete(obj); }
 
  // Start incremental marking
  startMarking() {
    this.phase = "marking";
    this.greyList = [];
    this.stats.markSteps = 0;
 
    for (const root of this.roots) {
      if (root.color === "white") {
        root.color = "grey";
        this.greyList.push(root);
      }
    }
  }
 
  // Do a small amount of marking work (time-boxed)
  markIncrement(maxSteps = 10) {
    if (this.phase !== "marking") return { done: true };
 
    let steps = 0;
 
    while (this.greyList.length > 0 && steps < maxSteps) {
      const obj = this.greyList.pop();
 
      for (const ref of obj.refs) {
        if (ref.color === "white") {
          ref.color = "grey";
          this.greyList.push(ref);
        }
      }
 
      obj.color = "black";
      steps++;
      this.stats.markSteps++;
    }
 
    if (this.greyList.length === 0) {
      this.phase = "sweeping";
      return { done: true, totalSteps: this.stats.markSteps };
    }
 
    return { done: false, remaining: this.greyList.length };
  }
 
  // Sweep all at once (or could also be incremental)
  sweep() {
    if (this.phase !== "sweeping") return null;
 
    const collected = [];
    for (const obj of this.heap) {
      if (obj.color === "white") {
        collected.push(obj.data);
        this.heap.delete(obj);
      } else {
        obj.color = "white";
      }
    }
 
    this.phase = "idle";
    return { freed: collected.length, alive: this.heap.size };
  }
}
 
// Simulate incremental GC interleaved with "application work"
const igc = new IncrementalGC();
 
// Create a graph of objects
const nodes = [];
for (let i = 0; i < 100; i++) {
  nodes.push(igc.allocate(`node-${i}`));
}
 
// Create references
for (let i = 0; i < 50; i++) {
  igc.addReference(nodes[i], nodes[i + 1]);
}
 
// Only root the first node (nodes 51-99 are unreachable)
igc.addRoot(nodes[0]);
 
// Start marking
igc.startMarking();
 
// Interleave marking with application work
let markResult;
do {
  // Application work happens here...
  markResult = igc.markIncrement(10); // 10 objects per increment
} while (!markResult.done);
 
// Sweep
const result = igc.sweep();
console.log(result); // { freed: ~49, alive: ~51 }

Compaction

After sweep, the heap has gaps ("holes") where freed objects were. Compaction moves objects to eliminate fragmentation:

javascript

class CompactingGC {
  constructor(heapSize = 1024) {
    this.memory = new Array(heapSize).fill(null);
    this.objects = new Map(); // id -> { start, size, data }
    this.nextId = 0;
    this.roots = new Set();
  }
 
  allocate(size, data) {
    // Find contiguous free space
    const start = this.findFreeSpace(size);
    if (start === -1) {
      // Try compaction then retry
      this.compact();
      const retryStart = this.findFreeSpace(size);
      if (retryStart === -1) throw new Error("Out of memory");
      return this.placeObject(retryStart, size, data);
    }
    return this.placeObject(start, size, data);
  }
 
  placeObject(start, size, data) {
    const id = this.nextId++;
    this.objects.set(id, { start, size, data, marked: false });
    for (let i = start; i < start + size; i++) {
      this.memory[i] = id;
    }
    return id;
  }
 
  findFreeSpace(size) {
    let consecutive = 0;
    for (let i = 0; i < this.memory.length; i++) {
      if (this.memory[i] === null) {
        consecutive++;
        if (consecutive >= size) {
          return i - size + 1;
        }
      } else {
        consecutive = 0;
      }
    }
    return -1;
  }
 
  compact() {
    // Move all live objects to the beginning of the heap
    let writePos = 0;
 
    const sortedObjects = [...this.objects.entries()]
      .sort((a, b) => a[1].start - b[1].start);
 
    for (const [id, obj] of sortedObjects) {
      if (writePos !== obj.start) {
        // Move object
        for (let i = obj.start; i < obj.start + obj.size; i++) {
          this.memory[i] = null;
        }
        for (let i = writePos; i < writePos + obj.size; i++) {
          this.memory[i] = id;
        }
        obj.start = writePos;
      }
      writePos += obj.size;
    }
 
    // Clear remaining memory
    for (let i = writePos; i < this.memory.length; i++) {
      this.memory[i] = null;
    }
  }
 
  getFragmentation() {
    let holes = 0;
    let inHole = false;
 
    for (let i = 0; i < this.memory.length; i++) {
      if (this.memory[i] === null) {
        if (!inHole) { holes++; inHole = true; }
      } else {
        inHole = false;
      }
    }
 
    const freeSlots = this.memory.filter((s) => s === null).length;
    return {
      freeSlots,
      holes,
      fragmentation: holes > 1 ? ((holes - 1) / holes).toFixed(2) : 0,
    };
  }
}

Mark-and-Sweep vs Reference Counting

javascript

// Circular reference: mark-and-sweep handles it, reference counting does not
 
function demonstrateCircularReference() {
  const gc = new BasicGC();
 
  const a = gc.allocate("A");
  const b = gc.allocate("B");
 
  // Create circular reference
  gc.addReference(a, b);
  gc.addReference(b, a);
 
  // Make both reachable
  gc.addRoot(a);
  console.log(gc.collect()); // { freed: 0, alive: 2 } - both alive
 
  // Now make both unreachable
  gc.removeRoot(a);
  console.log(gc.collect()); // { freed: 2, alive: 0 } - both collected!
 
  // Reference counting would FAIL here:
  // a.refCount = 1 (b points to a) -> never reaches 0
  // b.refCount = 1 (a points to b) -> never reaches 0
  // LEAK in reference counting, but correctly collected by mark-and-sweep
}
 
demonstrateCircularReference();

Aspect	Mark-and-Sweep	Reference Counting
Circular references	Correctly collected	Leaked (refCount never 0)
Collection timing	Batch (periodic)	Incremental (immediate on refCount 0)
Throughput	Higher (batch processing)	Lower (per-reference overhead)
Latency	Pauses during collection	No pauses, but cascading frees possible
Space overhead	Marking bits	Reference count per object

Rune AI

Key Insights

Two-phase simplicity: Mark all reachable objects from roots, then sweep (free) everything unmarked; this guarantees circular references are collected correctly
Tri-color marking enables incrementalism: White/grey/black states allow the mark phase to pause and resume without losing progress or missing objects
Write barriers maintain correctness: When black objects gain references to white objects during marking, barriers turn the white object grey to prevent incorrect collection
Compaction eliminates fragmentation: Moving surviving objects together after sweeping creates contiguous free space for future large allocations
Batch collection is a tradeoff: Mark-and-sweep processes many objects at once (higher throughput) but creates pauses; incremental and concurrent techniques minimize the visible impact

Frequently Asked Questions

Why is mark-and-sweep preferred over reference counting in JavaScript?

Mark-and-sweep correctly handles circular references, which are common in JavaScript (DOM nodes referencing handlers referencing nodes). Reference counting cannot collect cycles without a supplemental cycle collector. Additionally, mark-and-sweep has lower per-operation overhead since it does not need to update counters on every reference change. See [JavaScript Garbage Collection: Complete Guide](/tutorials/programming-languages/javascript/javascript-garbage-collection-complete-guide) for the full comparison.

What are write barriers and why are they needed?

Write barriers are checks inserted by the engine when you assign a reference (e.g., `obj.child = other`). During incremental marking, if a black (fully scanned) object gets a new reference to a white (unscanned) object, the barrier marks the white object grey. Without write barriers, incremental marking would miss objects added during the marking phase.

How does incremental marking affect application performance?

Incremental marking splits the pause into many small pauses (typically under 1ms each). The total marking work is the same or slightly more (due to write barrier overhead), but the user perceives no single long pause. This is critical for 60fps rendering where each frame budget is only 16ms. See [JavaScript Profiling: Advanced Performance Guide](/tutorials/programming-languages/javascript/javascript-profiling-advanced-performance-guide) for measuring GC impact.

When does compaction happen?

Compaction occurs when the heap has significant fragmentation and allocation of large objects fails despite sufficient total free memory. V8 does not compact after every collection; it uses heuristics to decide when fragmentation is severe enough to justify the cost of moving objects and updating all their references.

Can mark-and-sweep miss objects that are still in use?

No. Mark-and-sweep is conservative (safe): it starts from all roots and marks everything reachable. It may keep objects alive longer than necessary (if a reference exists but will never be used), but it never collects reachable objects. The invariant is: if you can reach it from a root, it will not be collected.

Conclusion

Mark-and-sweep is the foundation of JavaScript garbage collection, handling circular references that reference counting cannot. Tri-color marking enables incremental collection, write barriers maintain correctness during concurrent execution, and compaction eliminates fragmentation. The algorithm runs in batch cycles triggered by memory pressure, making short-lived allocations cheap and long-lived objects eventually promoted to less frequently collected spaces. For V8-specific implementation, see How V8 Garbage Collector Works. For practical leak fixing, see Fixing JavaScript Memory Leaks: Complete Guide.

Mark-and-Sweep Algorithm in JS: Full Tutorial

Basic Mark-and-Sweep

Tri-Color Marking

Incremental Marking

Compaction

Mark-and-Sweep vs Reference Counting

Rune AI

Frequently Asked Questions

Why is mark-and-sweep preferred over reference counting in JavaScript?

What are write barriers and why are they needed?

How does incremental marking affect application performance?

When does compaction happen?

Can mark-and-sweep miss objects that are still in use?

Conclusion

Tags

More in this topic

OffscreenCanvas API in JS for UI Performance

Advanced Web Workers for High Performance JS

JavaScript Macros and Abstract Code Generation

Stay Updated