Garbage Collection in Javascript

We shall today discuss memory management and garbage collection in JavaScript.Even though in JavaScript we are not performing any memory operations explicitly, however, it is good to know how it works.

In the low-level languages like C, programmers need to manually allocate and deallocate the memory using the malloc(), calloc(), realloc(), and free() methods.

In high-level languages like Java and JavaScript, programmers don't need to explicitly allocate or release memory.JavaScript memory is allocated when things are created (objects, Strings, etc.) and freed automatically when they are no longer used. This process is called Garbage collection.

  var a = 1;  // allocates memory for a number
  var b = {a: 1}; // allocates memory for an object

When the allocated memory is no longer needed, then it will be released.
Memory leaks, and most memory-related issues, occur while releasing memory.

Garbage Collection:

Garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage or memory occupied by objects that are no longer in use by the program.
We shall look into two algorithms used for garbage collection:-

1). Reference-counting garbage collection.

Reference Counting is a programming technique of storing the number of references, pointers or handles to a resource, such as an object, a block of memory, disk space, and others.

In garbage collection algorithms, reference counts may be used to deallocate objects which are no longer needed. If in reference counting algorithms, there are no references to an object, it will be automatically garbage collected.

This algorithm considers zero referencing object as an object that is no longer used by the application.

  var object1 = { object2: { value: 2 } };
  object1 = 2; // object2 now has zero reference count, hence memory will be released

However, this algorithm has limitations with cycles.

consider the below function,

  function cycleReference() {
    var object1 = {};
    var object2 = {};
    object1.a = object2; // object1 references object2
    object2.a = object1; // object2 references object1
    return 'done';
  }

In the above function in which object1 is referenced to object2 and object2 is referenced to object1 and it creates a cycle.
When the scope goes out of the function, then these two objects are useless. However, the garbage collector is unable to free the memory since those two still got the reference to each other.
It leads to memory leaks in the application.

2). Mark and Sweep algorithm.
The garbage collector uses this algorithm to free memory when an object is unreachable, rather than a zero referencing object.

The garbage collector will first find all the global objects or root objects and will find all the references to these global objects and references to the reference object, and so on. Using this algorithm, the garbage collector will identify the reachable and unreachable objects.
All the unreachable objects will be automatically garbage collected.

Let us try to implement something similar to this algorithm.

	// For simplicity lets represent the "heap" (the memory where
	// our objects are stored) as a plain array.
	var mockHeap = [];
	// freeList, just to visualize the free'ed objects
	var freeList = [];
	// Allocate object1
	var object1 = {
	value: 1
	};
	// object1 will be allocated in heap, let's push it to mockHeap
	mockHeap.push(object1);
	// Allocate object2
	var object2 = {
	value: 2
	};
	// object2 will be allocated in heap, let's push it to mockHeap
	mockHeap.push(object2);
	// create a chain from object1 to object2
	object1.object2 = object2;
	// Object object2 is allocated and is also reachable from object1: root -> object1 -> object2
	// Allocate object3
	var object3 = {
	value: 3
	};
	// object3 will be allocated in heap, let's push it to mockHeap
	mockHeap.push(object3);
	// create a chain from object1 to object3
	object1.object3 = object3;
	// Object object3 is allocated and is also reachable from object1: root -> object1 -> object3
	// Allocate object4
	var object4 = {
	value: 4
	};
	// object4 will be allocated in heap, let's push it to mockHeap
	mockHeap.push(object4);
	// create a chain from object2 to object4
	object2.object4 = object4;
	// Object object4 is allocated and is also reachable from object1: root -> object1 -> object2 -> object4
	// But now the "object2" reference is removed from "object1".
	delete object1.object2;
	// This means that "object4" still has the reference to it from "object2", but it's
	// not reachable (since the "object2" itself is not reachable anymore).
	// Notice the important point: that an object has some references to it
	// doesn't mean it cannot be Garbage Collected. The creteria is "reachability", but not the
	// reference counting here.
	// After these manipulations the heap still contains four objects:
	// [object1, object2, object3, object4], but only the "object1" and "object3" is reachable
	// (starting from the root).
	// ----------------------------------------------------------
	// Mark and Sweep Garbage Collection
	// ----------------------------------------------------------
	function gc() {
	garbageCollector.mark();
	garbageCollector.sweep();
	}
	var garbageCollector = {
	// In Mark phase, trace all reachable objects.
	// The "mark" phase traverses all reachable objects starting from
	// the root and mark them as reachable.
	mark: function () {
	var items = [mockHeap[0]];
	while (items.length) {
	// pick the next object to process
	var next = items.pop();
	// If the object is not marked yet:
	if (!next.__mark__) {
	// then we mark it
	next.__mark__ = 1;
	// and add _all reachable_ pointers from
	// this "next" object to our items list.
	for (var k in next)
	if (typeof next[k] == 'object') {
	items.push(next[k]);
	}
	}
	}
	},
	// And in the sweep phase collect the garbage.
	// After we have marked all reachable objects, we can start
	// the sweep phase. We simply traverse the heap and move
	// all unmarked (that is, unreachable objects) to the free list.
	sweep: function () {
	mockHeap = mockHeap.filter(function (o) {
	// If the object is marked, keep it and reset the mark bit
	// back to zero (for future GC cycles).
	if (o.__mark__ == 1) {
	o.__mark__ = 0;
	return true;
	} else {
	// Remove garbage object ("move to free list")
	freeList.push(o);
	return false;
	}
	});
	}
	}
	console.log('Heap before Garbage Collection:', mockHeap);
	// Heap before Garbage Collection: [object1, object2, object3, object4] of length 4
	gc();
	console.log('Heap after Garbage Collection:', mockHeap);
	// Heap after Garbage Collection: [object1, object3] of length 2
	console.log('[freeList] - Released objects:', freeList);
	// [freeList] - Released objects: [object2, object4] of length 2

view raw mark_and_sweep.js hosted with ❤ by GitHub