Tri-Color Marking Process in JavaScript Garbage Collection

[00:00:00]Marking is the first and most crucial step in the  major garbage collection cycle.

[00:00:01]In this video, we will discuss the Tri-Color approach to the marking process, and we will also take a closer look at all the techniques that JS utilises to make this much more efficient so the interference in the regular code execution is minimised.

[00:00:20]Hi, I'm Rohan, and this video is part of a series of videos where we are exploring how JS manages its memory in depth, so let's get to it.

[00:00:30]What is Tri-Color marking? This algorithm is  used as an enhancement to a previous marking algorithm where each object is marked either  as a live or a dead object. Here instead, each object is marked with three different  colours. V8 employs a marking method which utilises two Mark bits for each object and  something called a marking work list. These two Mark bits represent three different colours:  white with 00, gray with 10, and black with 11.

[00:00:59]Now, what does each of these three different  colours mean to the collector? The first colour is white. When an object is created, then it is  set to white, which signifies it as a new object, which also means that the collector has  not yet visited this object. But when the garbage collection process starts, then these  objects can be safely considered as objects that are no longer referenced and are hence  dead objects. The second color is gray. Gray objects are those objects that have been  visited by the collector at least once and its reference have been pushed into  the marking work list, but the collector has not yet examined its references to other  objects. When the garbage collection starts, these objects are also considered to be dead  objects and can be deallocated. The third color is black. Objects marked as black are  those objects that have been visited by the collector and its references to other objects  have been visited too. An important thing to note here is that black objects do not contain any  references to white objects. From the perspective of the garbage collector, these objects are  considered to be live and are hence retained.

[00:02:13]Now, initially, all objects are  marked as white indicating that the collector has not yet identified  them. A white object transitions to a gray object when the collector discovers  it and adds it to the marking work list.

[00:02:27]When the collector removes a gray  object from the marking work list, uses the references within this object to visit  all the neighbouring objects and processes them, then it changes the colour of the object from  gray to black. This process is known as Tri-Color marking. The marking process concludes when there  are no more gray objects in the marking work list and the remaining white objects are considered  to be unreachable and can hence be safely swept.

[00:02:56]Let's look at the algorithm in detail.  When the marking process starts, then all the roots are fetched. After that, we iterate  through the roots one by one and mark each one of them. This will call the mark function with  reference to the root. Inside the mark function, we will get the mark bits of the object and check  if the mark bits are white or not. If it is, then we will set the mark bits to gray and then  we will push the reference to the object in the marking work list and return. Also, if it is gray  or black, then we won't enter into the condition and simply return. When all the roots are marked  and we have an initial marking work list, then we will call the mark work list nodes function.  Inside this function, we iterate through the nodes in the marking work list one by one. We,  of course, iterate using a loop. When we enter inside the loop, then we set the mark bits of the  node to black and then get all the references to the subnodes from the node. Then iterate through  the subnodes one by one and mark each one of them, which means we call the mark function with  reference to the subnode and check if the mark bits of the subnode are set to white. If it is,  we set it to gray and push the reference in the marking work list and return. Otherwise, we just  return if it is gray or black, in cases of already visited nodes or circular references. When all the  sub-nodes are marked and the work list is updated, then we repeat the process till all the nodes in  the marking work list are visited at least once and the nodes are set to black and there are  no more gray objects. Then we return. In the main marking function, we wait for the next  marking cycle and then repeat the process.

[00:04:38]Let's visualise the Tri-Color marking with an  example. When we run our code, then we create a bunch of objects during the course of our  execution, so they are allocated in the Heap and are linked to each other using references, and  the root objects reference is stored in the stack.

[00:04:54]There are also some objects whose references are  removed from the stack because they are no longer needed for various reasons. Then at some point  in time, the marking process starts. So the root objects that are accessible from the stack are  immediately marked as gray and are pushed into the marking work list. Then these root references  are popped from the marking work list one by one, marked as black, and are used to traverse to  other linked objects. Those linked objects are marked as gray and their references are pushed  into the marking work list. And this process of popping a node reference from the marking work  list, marking it as black, and then subsequently reaching and marking other neighboring nodes to  gray and pushing their reference in the marking work list continues till all reachable  nodes are marked as black and the marking work list is empty. Then the remaining white  objects can then be safely swept or compacted.

[00:05:49]So how does V8 makes this more efficient? Since  we know that running the entire marking process all at once after a large number of allocations  pauses our main application down for several 100 milliseconds, a clever solution to this is to  do the entire marking process incrementally, which means that instead of a single long pause,  the entire marking process is split into smaller chunks and our main application can run in  between those chunks. The collector determines the amount of marking work in each incremental  chunk is directly based on the allocation rate in our main application. Typically, this  significantly enhances the application's responsiveness. However, in case of a large  memory heap under substantial memory constraints, there can still be extended delays as the  collector tries to keep pace with the allocations.

[00:06:41]But there is a problem when we do incremental  marking and then our main process resumes and it changes the structure of an already visited  object like assigning a new object to an existing object's field, which will definitely cause  inconsistencies such as retaining a dead object or deallocating a live object. To resolve this,  every time we change the structure of an object, we need to inform the collector by calling  a function known as a write barrier. Let's look at the write barrier algorithm. When we  assign an object to another object's field, then we call this function with object field  and value, which is also an object. When we enter into the function, then we will get the  mark bits of the object and the mark bits of the value. After that, we will check if the  object's mark bits are set to black and the value values mark bits are set to white.  If this holds true, then we will set the mark bits of the value to gray and push it  into the marking work list and return. This ensures that there are no black objects that  are pointing to white objects, maintaining the strong Tri-Color invariant. This will make  sure that the application cannot conceal a live object from the garbage collector. As a result,  any white objects that are remaining at the end of the marking process are genuinely unreachable  from the application and can be safely released.

[00:08:00]Browser task scheduler schedules small  incremental marking steps during the idle times in our main thread without causing  any long pauses. This optimisation is highly effective when there is some available idle  time. However, due to right barriers cost, the incremental marking may actually reduce  the overall application's throughput. Why do I say that? Take a period in time and sum  up all the time it takes to do incremental marking plus right barrier and compare it  to the time that it would have taken if we had done the entire marking process all  at once. Then this duration is greater than regular marking, which means that the overall  application throughput is slightly reduced.

[00:08:42]To enhance this throughput and reduce the pause  times, we need to utilize additional worker threads. There are two approaches to perform  marking on worker threads: parallel marking and concurrent marking. Parallel marking occurs  both in the main thread and in the worker threads, leading to a pause in the main application process  during this phase. It essentially represents the multi-threaded version of stop the world  marking. Concurrent marking, on the other hand, takes place on the worker threads, which allows  our main application to keep running and the marking is in progress concurrently. Now, V8 does  something interesting. It combines the concurrent marking with the existing incremental  marking process. So in the main thread, the code execution and the marking process in  chunks are done alternatively, and concurrently, the marking process is also performed in  the dedicated worker threads. This way, the work of marking is shared among all the  threads until all the objects are marked and the marking work list is empty. And a  finalization step in which all the roots are checked again just to see if there are any  more additional white live objects. That were missed earlier. This step also leverages the  worker threads just to speed up the process.

[00:09:56]Anyway, let's look at the flow to understand  this process better. Assume we have three threads to work with: one main and two  worker threads. In the main thread, the process execution happens for some time, and  during this time, objects are being allocated in the heap. So marking process starts concurrently  in the worker threads. Periodically, a check is being made to see if there is any idle time. If  there is none, then the main process continues, but if it does find some, then a chunk of the  marking process happens in the main thread as well. After some time, the main process resumes  until there is another idle time available, and this process repeats alternatively  in the main thread. Now, after some time, the marking process is complete in all three  threads, which means that the marking work list is empty and all the objects are marked black.  So a final marking process starts just to make sure there are no more live white objects. And  after that, sweep or compact process happens.

[00:10:56]Now, we are not going to get into how this  is actually being done since V8 has to deal with concurrency, making it thread safe,  synchronization via Atomic operations, etc., which is getting out of scope, and frankly,  I do not have the necessary knowledge to get into this topic with you. If you want to know more  about this topic, there are several articles on it in the V8 website. You can check them out.  I will put the link down in the description.

[00:11:21]So to summarise, we discussed what Tri-Color  marking is, understanding its process in detail, and we also visualised it with an example.  After that, we discussed the incremental marking process and the need for right barriers  during the normal execution intervals in between the marking processes, which revealed to us  the limitations of the incremental process, which led us to discuss ways to enhance  the incremental marking even further by discussing parallel and concurrent marking  and how V8 combines them into a single process which ultimately enhances it. We also  discussed this incremental parallel concurrent marking process by understanding the flow  of this process. I also want to discuss the sweep and compact process in detail  with you. So this is what we will discuss in the upcoming couple of videos. Thank you  for your time.

[00:12:13]Have a nice day. Namahshkar.