Mark and Sweep Algorithm in JavaScript

Mark and Sweep algorithm

Mark and Sweep algorithm looks out for objects 'which are unreachable' rather than objects 'which are no longer needed'. This algorithm is the improvement of Reference-counting algorithm.

This algorithm actually goes through 3 important steps.

•  Root: In general, a root is a global variable that is used in the code. A window object in javascript can act as a   root. This algorithm uses global object root to find whether the objects are reachable or unreachable.
• This algorithm then monitors every root and also their children. While monitoring, some objects which are reachable are marked and remaining objects which are unreachable are unmarked, based on the provided conditions.
•  The objects which are unmarked, that means which are unreachable will be garbage collected. 

Mark phase

In mark phase we can able to find which elements are marked and which are unmarked. Let's suppose assign a property 'hello' to an object 'obj1' as shown in given Example-1. The root, global object used by this algorithm, can reach to obj1 and its property 'hello'. So it is marked now.

Example-1

var obj1 = {
pro1: "hello" // marked because it can be reached by root.
}

For suppose let this object be assigned a null value as shown in Example-2. Then newly assigned 'null' will be marked and previously assigned 'property hello' will be unmarked. So at the end of the Mark phase we can conclude that object assigned with 'null' got marked and object assigned with 'property hello' was unmarked.

Example-2

obj1 = null // null will be marked(reachable) and hello will be unmarked(unreachable)

Sweep phase

As the name suggests it 'sweeps' the unreachable objects. In mark phase we have seen that object with "property hello" got unmarked, making it unreachable. Since unreachable objects will be garbage collected, the object with 'property hello' will be garbage collected in this phase.

The Mark and Sweep algorithm is also called as a tracing garbage collector because it traces out the entire collection of objects that are directly or indirectly accessible by the program.

Cycles are no more a problem

In the following example, when the function call returns, the two objects obj1 and obj2 are not referenced by something that is reachable there by eligible for garbage collection. So garbage collector will free the memory of the objects obj1 and obj2.

Example

function f() {
   var obj1 = {};
   var obj2 = {};
   obj1.p = obj2; // obj1 references obj2
   obj2.p = obj1; // obj2 references obj1. This creates a cycle.
}
f();

Limitations

There are some moments when it is very convenient to manually decide when and what memory is released. In order to release the memory of the object, it has to be made explicitly unreachable. This process of explicitly triggering garbage collection in JavaScript is not possible as of now.