How does the "Mark-and-Sweep" algorithm work?

Difficulty: 5/10

garbage collection, memory management, V8 engine

The Mark-and-Sweep algorithm is a fundamental tracing garbage collection technique that operates in two distinct phases: first marking all reachable objects starting from root references, then sweeping the heap to reclaim memory from unmarked objects.

The Mark-and-Sweep algorithm solves the problem of automatic memory management by identifying which objects are still in use and which are garbage. It's called a 'tracing' garbage collector because it traces through the object graph starting from known roots . Unlike reference counting, it can handle circular references without getting stuck in infinite loops . The algorithm fundamentally requires two operations: detecting all unreachable objects and reclaiming the heap space they occupy.

Conceptual Pseudocode of Mark-and-Sweep

Phase 1: Mark Phase - Finding Live Objects

1
Starting Point - The Roots: The algorithm begins from a set of known root objects—global variables, local variables on the stack, and CPU registers that can reference heap objects . In browsers, roots include the window object; in Node.js, the global object.
2
Graph Traversal: From each root, the algorithm traverses all references, following pointers to other objects recursively . This is typically implemented using depth-first search, visiting every reachable node in the object graph .
3
Marking Mechanism: Each object has a mark bit (initially set to 0/false). When visited, this bit is set to 1/true to indicate the object is reachable and should be preserved . This marking may use a separate bit table or a bit within the object itself .
4
Handling Cycles: Because the algorithm traces reachability from roots rather than counting references, it correctly identifies cycles as garbage if no external references point to them .

JavaScript Example: Circular References Handled Correctly

Phase 2: Sweep Phase - Reclaiming Memory

1
Heap Scan: After marking completes, the algorithm scans through the entire heap, examining every object in order of increasing address . This is a linear pass through memory that examines all allocated objects .
2
Reclamation Decision: Objects with their mark bit still set to 0 (false) are considered unreachable garbage. Their memory is freed and returned to the system or made available for new allocations .
3
Mark Reset: For objects that were marked (reachable), their mark bit is cleared back to 0 in preparation for the next garbage collection cycle . This ensures each collection starts with a clean state.
4
Free List Management: Reclaimed memory is typically added to a free list, which tracks available blocks for future allocations .

Visual Example of Mark-and-Sweep in Action

The Mark-and-Sweep algorithm has several important advantages. It handles cyclic references automatically, which is impossible for pure reference counting collectors . It adds no overhead during normal program execution—all work happens during collection pauses . However, it also has significant disadvantages. The most critical is that normal program execution must be suspended ('stop-the-world') while collection runs, which can cause noticeable pauses in interactive applications . Additionally, sweeping time is proportional to the total heap size, not just the amount of live data .

Major Challenges: Fragmentation and Pauses

1
Memory Fragmentation: Over time, as objects are freed in arbitrary order, the heap becomes fragmented with small unused gaps between live objects . This can prevent allocation of large objects even when sufficient total free memory exists.
2
Compaction Solution: Many modern collectors add a compaction phase after sweeping, moving live objects together to create one contiguous free block . This eliminates fragmentation but adds overhead.
3
Incremental Marking: To reduce pause times, engines like V8 break marking into small steps interleaved with program execution, using write barriers to track references created during marking .
4
Concurrent Sweeping: Some engines perform sweeping on a background thread while the program continues running, reducing perceived pause times .

In modern JavaScript engines, pure Mark-and-Sweep is rarely used alone. Instead, it's combined with generational collection (young/old generations) to optimize performance . V8's Orinoco collector, for example, uses Mark-and-Sweep for the old generation but employs a copying collector for the young generation . The fundamental insight remains: by tracing reachability from roots, the algorithm correctly identifies garbage regardless of reference patterns, making it the foundation of virtually all modern production garbage collectors.

Scenario Questions

0-2 years experience

1If you have a simple Node.js script that creates a large array and then sets it to null, can you walk me through what the Mark-and-Sweep collector does after that line executes?
2Suppose you add a circular reference between two objects in a browser environment. How does the Mark-and-Sweep algorithm handle that, and will those objects be reclaimed?
3What would happen if you manually invoke global.gc() in a V8 process after allocating many temporary objects? Describe the steps the Mark-and-Sweep collector takes.

2-5 years experience

1We noticed a memory leak in a React app after navigating between pages. The heap snapshot shows many detached DOM nodes still referenced. How would you use knowledge of Mark-and-Sweep to debug why those nodes aren't being collected?
2During a performance regression, the GC pause time increased dramatically after adding a new caching layer. Explain how the Mark phase could be affected by the cache structure and what trade‑offs you might consider.
3If you switch V8's GC mode from incremental marking to full Mark-and-Sweep, what impact would you expect on latency and throughput for a real‑time chat server?

5-8 years experience

1Design a custom memory pool for a high‑frequency data processing service in Node.js. How would you integrate Mark-and-Sweep considerations to avoid fragmentation and ensure timely reclamation?
2Your team is evaluating moving a critical microservice from Node.js to a Rust runtime to reduce GC pauses. What aspects of Mark-and-Sweep in V8 would you compare against Rust’s ownership model when arguing the trade‑off?
3Explain how you would instrument V8’s GC to monitor Mark‑and‑Sweep cycles in production, and what thresholds would trigger a rollback of a recent feature.

8+ years experience

1We have a legacy monolith written in JavaScript that runs on a constrained IoT device with limited RAM. How would you architect a migration strategy that reduces reliance on Mark-and‑Sweep pauses, possibly by partitioning workloads or using WebAssembly?
2Across multiple teams, you need to establish a company‑wide policy for memory‑intensive services. How would you incorporate Mark‑and‑Sweep behavior into guidelines for object lifetimes, caching patterns, and monitoring dashboards?
3If you were to propose a new GC algorithm to replace Mark‑and‑Sweep in V8, what high‑level design criteria would you set to satisfy both latency‑sensitive front‑ends and batch processing back‑ends?

Follow-up Questions

What are the main drawbacks of Mark-and-Sweep compared to other GC strategies?
How does incremental marking help with pause times?
Can you give an example of a false retain that can occur with Mark-and-Sweep?

Sharethis question

Share via WhatsApp, X, Facebook, LinkedIn or copy link. Open Graph preview enabled.