Mark and Sweep Algorithm in JS: Full Tutorial

Mark-and-sweep is the foundational garbage collection algorithm used by every major JavaScript engine. It works in two phases: mark every object that is reachable from a root, then sweep away (free) everything that was not marked.

The algorithm is simple in concept but has been refined over decades with optimizations like concurrent marking, incremental sweeping, and generational collection. Understanding the core algorithm helps you understand why GC pauses happen and how engines work to minimize them.

The Two Phases

The mark phase starts from roots and follows every reference. Every object visited is marked.

The sweep phase scans all objects linearly. Objects without a mark are freed. Objects with a mark have their mark cleared for the next cycle.

The Mark Phase

The mark phase begins with a set of roots. In JavaScript, roots are global objects, local variables on the call stack, active closures, and internal engine structures.

From each root, the collector follows references to other objects. From those objects, it follows more references.

This is a graph traversal. The collector visits each reachable object exactly once and sets a mark bit. The traversal stops when every path from every root has been exhausted.

Any object that was never visited during this traversal is unreachable.

The mark phase must handle cycles correctly. If object A references object B and B references A, the collector visits A, marks it, follows the reference to B, marks B, follows the reference back to A, and finds A already marked. The traversal terminates without getting stuck.

The Sweep Phase

The sweep phase is linear. The collector walks through every allocated object in the heap and checks its mark bit.

If the bit is set, the object is live. The collector clears the bit for the next cycle and moves on.

If the bit is not set, the object is garbage. Its memory is added to a free list for future allocations.

Sweeping is fast per object because the check is a single bit test. But for large heaps with millions of objects, sweeping every object takes time. Modern engines use concurrent sweeping that runs in a background thread while JavaScript continues executing.

The Tri-Color Abstraction

Mark-and-sweep is often described using the tri-color abstraction, which divides objects into three sets during marking.

White objects have not been visited by the collector yet. At the start of marking, every object is white. At the end, white objects are garbage.

Gray objects have been visited but their outgoing references have not been processed yet. The collector knows the object is reachable but has not yet followed its references to other objects.

Black objects have been visited and all their outgoing references have been processed. The collector has fully explored everything reachable from this object.

The marking algorithm processes gray objects one at a time. For each gray object, it marks all referenced white objects as gray, then turns the current object black.

When there are no more gray objects, marking is complete. Every remaining white object is garbage.

Handling the Mutator

The mutator is the running JavaScript program. While the collector marks objects, the mutator is still creating new objects, modifying references, and destroying old ones. This creates a problem: the collector's view of the object graph can become stale.

There are two main approaches. Stop-the-world collection pauses the mutator entirely during marking. This is correct but causes visible pauses.

Concurrent collection lets the mutator run during marking but requires write barriers.

A write barrier is a small piece of code that runs every time the mutator writes a reference. If the mutator stores a reference to a white object into a black object, the collector would miss it because black objects are already processed. The write barrier catches this and marks the white object gray, preventing it from being incorrectly collected.

Incremental Marking

Marking a large heap can take hundreds of milliseconds. Stopping JavaScript for that long is unacceptable. Incremental marking splits the mark phase into small steps.

Each step marks a few objects and then yields control back to JavaScript. The mutator runs normally between steps. The next step resumes where the previous one left off.

The challenge with incremental marking is that the mutator can change references between steps. Write barriers handle this. The overhead of write barriers is small compared to the benefit of eliminating long pauses.

V8, SpiderMonkey, and JavaScriptCore all use incremental marking. The typical step size is a fraction of a millisecond, keeping the page responsive even during major GC.

Lazy Sweeping

Sweeping every object in a large heap takes time, but most sweeping work can be deferred. Lazy sweeping only sweeps a page of the heap when the allocator needs fresh memory from that page.

The heap is divided into pages. After marking, each page is in an unswept state.

When the allocator needs memory, it sweeps the next unswept page, adding free objects to the free list. If the allocator finds enough free memory, it stops sweeping. Pages that are never needed for allocation are never swept.

Lazy sweeping spreads the sweep cost across many allocation operations instead of paying it all at once. This eliminates the visible pause from sweeping entirely.

Mark-and-Compact

Fragmentation is a problem for mark-and-sweep collectors. After many collections, the heap contains many small free chunks scattered between live objects. A large allocation may fail even though total free memory is sufficient because no single chunk is large enough.

Mark-and-compact adds a third phase after sweeping. Live objects are moved together to one end of the heap, creating a single large free region at the other end. Compaction is expensive but eliminates fragmentation.

V8 uses compaction selectively. It compacts highly fragmented pages and leaves well-organized pages alone. This balances the cost of compaction against the cost of fragmentation.

For the broader GC picture, see /javascript/javascript-garbage-collection-complete-guide. For V8's specific implementation, read /javascript/how-v8-garbage-collector-works-in-javascript.