Mark-sweep
- Node.js course
- Expert
- Lesson 21/47
- 5 min
Learn mark-sweep and mark-compact algorithms.
Mark-sweep
Mark-sweep is the garbage collection algorithm used for the old generation. It has two steps: mark — starting from roots, it marks all reachable objects; sweep — it deletes unmarked objects. This handles circular references correctly.
A markSweep(roots, allObjects) function models this: it finds objects reachable from roots and discards the rest. new Set(roots) builds the reachable set; allObjects.filter(o => reachable.has(o)) keeps only reachable ones. Example: markSweep(['a', 'b'], ['a', 'b', 'c', 'd']) returns 'a,b'. c and d are unreachable; they are swept. This model shows mark-sweep with a deterministic filter.
The reachable set
The essence of mark-sweep is checking whether an object is reachable from the roots. new Set(roots) builds the reachable set. reachable.has(o) tells whether an object is in the set. This is a simple model of the mark step.
Example: const reachable = new Set(['a', 'b']). reachable.has('a') is true, reachable.has('c') is false. allObjects.filter(o => reachable.has(o)) keeps only ['a', 'b']. .join(',') yields the string 'a,b'. This shows how mark-sweep decides which objects live: those reachable from roots live, the rest are swept. The output is a,b.
Practice Write the mark-sweep function
Write function markSweep(roots, allObjects). Define const reachable = new Set(roots). Return allObjects.filter(o => reachable.has(o)).join(','). Print console.log(markSweep(['a', 'b'], ['a', 'b', 'c', 'd'])).
Starter code
// Write a markSweep function
// Find objects reachable from the roots
// Join reachable ones with a comma and return
// Call with ['a','b'], ['a','b','c','d']
// write hereSample solution
function markSweep(roots, allObjects) {
const reachable = new Set(roots);
return allObjects.filter(o => reachable.has(o)).join(',');
}
console.log(markSweep(['a', 'b'], ['a', 'b', 'c', 'd']));Expected output
a,b
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Match each concept to its description
| Term | Meaning |
|---|---|
Mark |
Marks reachable objects |
Sweep |
Deletes unmarked objects |
Roots |
Starting points |
Set |
Set data structure |
2 What does markSweep(['a'], ['a','b','c']) return?
markSweep(['a'], ['a','b','c'])- 'a,b,c'
- 'b,c'
- 'a' Correct answer
- 'a,b'
Explanation: Only 'a' is reachable from the root; 'b' and 'c' are swept.
3 Complete the filter call
return allObjects.____(o => reachable.has(o)).join(',');return allObjects.filter(o => reachable.has(o)).join(',');Explanation: filter keeps those matching the condition.