Insights on the Mark and Sweep Algorithm

As a developer, understanding how Mark and Sweep algorithm in JavaScript helps to write an efficient code 

Memory Management:

A memory allocation will be created for all the variables, objects, functions we declare in the code. The memory heap is the place where all these memories are stored. This is constantly in sync with the call stack. Once the execution phase starts, there will be a read/write operation for that memory once it is done with the execution that part of the memory location needs to be cleaned.  

Garbage Collection:

The Garbage Collection helps to clean the memory that is no longer in use by the code. This prevents memory leaks. In JavaScript, the garbage collection is handled by JavaScript engine. The garbage collection considers references, and it tries to release the memory if a location is not reachable. 

let obj = { 
 name: 'Orange', 
} 
let obj = null;

In this example, the obj has a reference to name which is orange, and that reference is cancelled as the obj is null. The “name” will not have any reference. Nothing can access this value without any reference, so it is not “reachable”. 

The Mark and Sweep Algorithm:

The Mark and Sweep Algorithm is the garbage collection technique used in JavaScript. It operates in two phases: 

1. Marking 
2. Sweeping 

The algorithm starts from the root object and checks for the reference linked. In case if this algorithm finds unreachable locations, then those are the locations to be removed.

Marking Phase:

“Mark” will mark all the referenced items. Values which are not reachable and do not have any reference will not be marked. 

Example #1 : 

globalObj → obj1 
functionA → obj2 → obj3 
functionB (unmarked)

1. It marks globalObj, which leads to marking obj1. 
2. Then, it checks functionA, marking obj2, and subsequently obj3 since obj2 references it. 
3. functionB is unmarked because it does not reference anything. 

Sweep Phase:

Revolutionize Your Business With Generative AI

From product design and software development to virtual agents, content creation, and reporting, GenAI is transforming business. Our AI experts help you unlock GenAI’s full potential and drive growth.

Let’s Get Started

The Garbage collector scans the memory that is not marked during the marking phase. Unmarked objects are considered unreachable.

It finds that functionB is unmarked and thus can be collected. 

The memory occupied by functionB is now freed, while globalObj, obj1, functionA, obj2, and obj3 remain. 

Example #2 : 

let author1 = { 
    name: "J.K. Rowling", 
    books: [] 
}; 

let author2 = { 
    name: "George Orwell", 
    books: [] 
}; 

let book1 = { 
    title: "Harry Potter", 
    author: author1 
}; 

let book2 = { 
    title: "1984", 
    author: author2 
}; 

// Establishing references 
 author1.books.push(book1); 
 author2.books.push(book2); 
  
// Later we remove one author and their books 
 author1 = null;

Marking Phase for Example #2: 

Marked reachable object which is author2 and book2. 

author1 is set to null, so it does not get marked. As a result, book1 is not marked which is reachable only through author1. 

Sweep Phase for Example #2: 

Collects unmarked(unreachable) object author1 and book1 and frees the memory occupied by these objects. 

Final State of Example #2: 

Memory Freed: author1, book1 

Memory Retained: author2, book2 

Why is Garbage Collection Important? 

Prevents Memory Leaks: Understanding how garbage collection works helps to avoid issues that lead to memory leaks. 

Boosts Performance: When memory is managed efficiently, your application runs smoother and faster. 

Advantages of Mark and Sweep Algorithm

1. Handles Cyclic References: The algorithm handles cyclic references without getting stuck in an infinite loop 
2. No Additional Overheads: It does not produce additional overheads during its execution 
3. Efficient Memory Reclamation: Can reclaim memory in large chunks, rather than just one object at a time 

Disadvantages of Mark and Sweep Algorithm

1. Interruptions: Causes interruptions in normal program execution while the garbage collection algorithm is running. 
2. Fragmentation: Leads to memory fragmentation, with small unused memory regions scattered throughout the heap. 
3. Time-Consuming: The sweeping phase can be time-consuming as every location in memory must be examined. 

Optimization Techniques for Mark and Sweep Algorithm

1. Lazy Sweeping: Executes the sweeping phase by spreading the cost of sweeping over time. 
2. Bitmap Marking: Uses a bitmap to store marking information, reducing space overhead, and improving performance. 
3. Pointer Reversal: Eliminates the need for a marking stack by recycling variables, reducing space overhead. 
4. Incremental Marking: Breaks the marking phase into smaller chunks to avoid long pauses. 

Understanding the Mark and Sweep algorithm and its optimizations helps to write more efficient code and manage memory effectively. By leveraging these techniques, we can prevent memory leaks and boost the performance of the applications. For more information, contact our technical experts. Design sharp, code smart!