Mark and Sweep Garbage Collection Algorithm Explained

[00:00:00]garbage collection has to be one of the most interesting topics of discussions out there in the previous video we took a look at why programming languages need an automatic garbage collection and what are the key metrics and characteristics we'll look at while picking one in this video we take a detailed look into one of the most common garbage collection algorithm out there called mark and sweep instead of just talking about the mark and the sweep phase of it we will dive into the details and the nuances of the key decisions made by the algorithm and we'll take a look at two super interesting optimizations that would boost the performance of the algorithm by a massive factor but before we move forward i'd want to talk to you about a code based course on system design that i have been running since march 2021 right if you're looking to learn system design from the first principles this course is for you yeah because this is a cohort based course it will not just be me rambling a semi-optimized solution thinking it's the most amazing solution out there instead it will be a collaborative environment where every single person who is part of the cohort will can pitch in his or her ideas and we will evolve our system around that and every single problem statement comes with a brainstorming session where we all together brainstorm and evolve our system that's why everyone understands the kind of trade-offs we made while making that decision instead of just saying hey we'll use a particular queue we'll have the justification why we use only that queue why we use that particular database why sequel why not nosql right how are we leveraging throughput how are we ensuring that our system skills that's the highlight of this course this course is taken by more than 500 engineers to date spanning nine countries and seven cohorts right people from all top companies have taken this course and the outline is very intriguing it's very exciting so we start with week one around we start with the core foundation of the course where we design online offline indicator then we try to design our own medium then we go into database where we go in depth of database logging and take and see few very amazing examples of data log or database logging in in action and how do we ensure that our system scales through that then the third week is all about going distributed where we design our load balancer i'll walk you through the actual code of a toilet balancer and understand how pcb connections are managed and how simple it is to build load balancer then week 4 is about all about social networks week 5 is all about building your own storage indians like we'll build that intuition on if you were to ever design your storage agent how would you do that right then week six is about building high throughput system seven is about building uh ir systems basically information retrieval systems and adopt designs where we design our own message brokers like sqs where we design distributed task scheduler and we conclude the course with week 8 where we talk about the super clever algorithms that has powered or that has made those systems possible right i have also attached a video verbatim as is from my first code where we designed and scaled instagram notifications i will highly encourage you to check this video out right and now back to the video so programming languages out there supports object references which means one object can refer to another object in the heap a simple example of that is a three structure in c structures you have members one of the member might store the reference to some another start right when you create when you allocate the instances of the structs on the heap you can link them through this pointer objects and and when you are linking this to this pointer object it creates this nice object reference relationships with between them right so let's say you have a global variable and that global variable is a struct and that struct contains three members which contains three pointers to three different objects out there so it creates this very nice interconnected graph of four nodes where the root node becomes your global variable that contains three members each one is a pointer to some another object right similarly for n global variables you might have just over simplifying things that you might have n such small graphs right and mark and sweep operates on this object reference graph if you if you may call it right so the idea here is mark and swift garbage collection is split into two phases the marking phase and the sweeping phase in the marking phase it starts iterating through all of these root nodes and sees which all objects are reachable from them and the objects which are reachable from them it marks them right it marks them live these objects are live i don't want to clean them up right so after the marking phase is done you will have all the reachable objects marked as life right so that's what triggers the sweeping phase in the sweeping phase we go through all the objects out there and see the objects which are not marked the objects which are not marked are garbage because they are supposedly not reference anywhere which has unreachable from the root nodes right and when that is the case you can your garbage collection can trigger like in the sweeping phase it can actually start deallocating the memory that it allocated to those objects before because now they are not referenced this is a very basic idea of mark and swift we will take a detailed look at the implementation in some time but you can form a but but you can form a solid understanding when when we are going through other micro nuances detail of it right so this the the two phases of market strip are pretty straightforward but what is this algorithm all about like this is an indirect collection algorithm which means that the algorithm does not know which nodes are garbage or which objects are garbage instead what it does is it sees what's life and the objects that are not life become the garbage which is why it is an indirection collection algorithm right so there is another algorithm called reference counting which is a direct collection algorithm which knows hey this object is garbage margins whip on the other hand it does not know which which object is a garbage so that's why it has to go through all the nodes which is okay these are reachable so this is not garbage and what is not marked becomes the garbage right so few terminologies before we move forward uh mutator thread and collector thread so mutator thread is yeah is like your normal user development stuff where these threads would create objects would read objects would write objects normal thread like when you do malloc when you're invoking new when you read an object when you write so anything related to the program that you are writing is part of mutator thread whose job is to mutate something in your heap while your while there is something called as a collector thread and this collector thread is the one that is running your garbage collection which is what is called as a collector thread right so you might have uh like whenever you're doing malloc reading a variable writing a variable usual actual business logic stuff is all done by your muted result i'm just overlapping them into a mutator thread sort of stuff and while everything about garbage collection is run by this collector thread so whenever the garbage collection garbage collection kicks in this particular collector that is the one that is doing that right so to simplify our understanding of mark and sweep and obviously as we move forward into this garbage collection series we will we will stop assuming things and see how those things are built in real time but to simplify for now what we would do is we would assume that the garbage collection that we are writing is top double gc so what is stop the world gc so stop the world gc says that hey when the garbage collection is running i have to stop the world which means that all of this mutator threads like when my garbage collection is triggering all the three mutator threads or many mutated all the mutated threads will stop which means that with the stop the world garbage collection kicking in everything around your business logic is stopped and what executes is only garbage collection which means that your program will literally hang at a place until the garbage collection is finished and then it would resume right this is the first assumption that we made second is you'll have multiple mutator threads but only one collector thread and we are just over simplifying things so that it becomes easier because otherwise we have to take care of consistency and snapshotting and whatnot we will we will cover that in the future once but for now we'll just keep it very simple that you have multiple mutator threads but one collector thread right so when we look at any garbage collection in general what you will find is that any automatic memory management system has three tasks first one is allocate as in that memory management system of that programming language needs to allocate space for the new objects that we want second is to identify the live objects hey out of all of these objects that i have these are the objects that are life and third is where it knows that these objects are garbage it has to reclaim the space occupied by the dead object so the three key functionality of any memory manage any programming language memory management system like these three are the core responsibilities of it now let's talk about when exactly is gc triggered like when would you trigger your garbage collection the simplest way to trigger a garbage collection is when you are unable to allocate a new memory to it or like when your programming language or when your usual business logic stuff is trying to do an allocation of an object but it is failing that's when you can trigger a garbage collection right so obviously there are you can have routine garbage collections and all but this is another place where you can plug your garbage collection in so what you do is you might have a new function or a malloc function or something this implementation of that right so when your new function is invoked which is allocating a new object for you in the heap what it might do is it might try to first allocate on the heap if it is not able to allocate so allocation is stored in this obj if obj is null which means allocation did not happen that's when you trigger collect collect is the one that would invoke the garbage collector right so depending on the algorithm that you have plugged in mark and swap reference counting what not this would trigger the collection of the dead objects right once the collection is done then it would try to reallocate once it tries to reallocate if it is still unable to allocate which means that literally there was no garbage available and your program is actually out of memory right that's where it might throw an out of memory error which in most cases is a fatal error but there are some programming languages in which if the allocation fails it gives you an error which you can handle explicitly right but in most cases you would see this as a fatal error where your process crashes because it was not unable to allocate new memory onto the or new object into the heap right but if this failure path didn't happen which means the allocation was succeeded then it would return the object right so here this is a very simple and standard way of allocating a new object this is not something that you have to do it this the programming language would do it like internally uh your new function in your java or whenever you are creating a new object in the heap internally it would do this you don't have to explicitly write this right so you internally the flow would be it would try to allocate the object if it is allo if it is able to allocate the object it would immediately return if it is not able to allocate the object then to trigger the garbage collection if once the garbage is collected it will try to reallocate it if it is able to reallocate then uh sorry it would try to allocate it again if this time the allocation succeeds it would return the object if it doesn't succeed then would raise an out of memory error which in most cases is a fatal error right so just a simple visual representation of this could be that hey let's say this is your memory right and this memory got full right the red ones are the objects which are there in your memory but they are dead right so what you would do is when someone is trying to allocate a chunk of memory for an object you would first see hey am i trying i want let's say one mb of space in memory do i have it your programming language will return no it's not that it would return null once it returns null what it would do is it would trigger garbage collection once it triggers garbage collection it would delete this and this because these are dead objects and then try to really get let's say you tried to allocate this 1mb memory and it got allocated over here right and this is exactly what happens in your memory management of your programming language right so now we talk about the phases of mark and sweep although i said to you there are two phases of market stream but when you are actually implementing it there basically there are more than two phases of it the first phase is preparation of the root list so in this one what we definitely want to identify is identify all possible root nodes right key hey these are all the global variables from which i will start tracing all of my live objects like objects referenced from this global variable are live object reference within those references are live and so on and so forth right but in order to trigger this process you need to know what all are the routes right now these routes can be a threat stack it can be a global variable it can be the root process that it is running which is doing that memory management there are so many things we will talk about this later uh in this particular series but for now assume that there is a function called get roots which somehow returns the roots as in all the roots that you have the references to those objects which are the roots uh from which you would have to start your mark and sweep right so any object that is directly or indirectly referenced in this root is is the live object right so that's the end of phase one once we have identified the roots uh then what we do is we proceed for marking once we identify the root obviously the first job would be for us to mark these roots uh as life right so what we do is we uh each route is marked as live and is added to the list now this is like a work list that you have in which what you are doing is once something is marked as life you add it to the list so that you can visit the you can visit the the the children pointers of this particular reference of this particular object after some time right so we invoke this function where we start with all the roots that we got from the verb function we mark the root as life so is marked equal to true list dot add root right so all the roots are added into this work list after marking right so this is kind of like visited node in your in your standard dfs based approach now one very interesting optimization that you can do over here is you can trigger mark as soon as you as soon as you added or as soon as you added root into the list you can invoke the marking phase so as in you can immediately start iterating from that root and start marking the root node or the or the child nodes of it this is one of the most amazing optimizations that i have seen what this does is that for example as because immediately as you added root into the list you are immediately invoking the actual marking phase where you would trigger the your trigger the depth first search algorithm right but here we are doing it every time the route is added because what it would make mean is if let's say your if you are waiting for all the routes to be marked and then you are triggering the marking phase then your work list might be gigantic right so here what you are doing is as soon as you add over here you are immediately invoking the mark phase for that specific route so whatever is there in the work list it would trigger the mark base for that and it would then like you will always have a bare minimum needed work list instead of having a very gigantic list of all possible nodes out there you are operating at smaller scale this is a very interesting optimization that some programming languages might choose to do but in some cases it is not possible to do so for example when you are running things in a concurrent manner this might not be the best choice where you are triggering mark again and again right instead you might want to wait so both implementations are there but in case you are running a very simplistic mark and save collector this is a very interesting optimization that would keep the size of this list to a bare minimum right then comes the like the idea behind the normal uh depth first search part so here what we do the list that we are talking about where we were where we added the root to the list think of this list as a stack so what we are doing is we are running we are basically running a simple dfs algorithm a simple depth first search traversal on this graph that we have we start from the root node we visit it then we add all the child into the list then we loop out the entire process until the list is empty and once we pop something out we are what we are doing is we are actually marking that and then adding the child back into it right so the idea is pretty simple like normal dfs algorithm for each route we initialize the mark we we initiate the marking part of it in which we traverse all the objects that are reachable from it right so while not list dot empty object equal to list dot pop we popped out one reference for the child object in the child of object right so all the objects which are reachable from this object we continue if it is already marked we don't do anything right but if it is not marked we mark it as one and then we add it to our stack again right this way the loop this process this depth versus travis will continue until every single object that is reachable from the graph is reached or is marked right so once we do that after this phase all the reachable objects are marked and then we can trigger the next set of process or the next set of uh or the next phase which is the sweeping phase right after this step any object that is not marked becomes the garbage which is what our indirection collection algorithm was all about right and when this became the uh when the nodes which are not marked becomes the garbage what we have to do is we have to initiate the sweeping phase that would iterate over all objects and would sweep out all the garbage out there right so that's what triggers the phase four which is the sweeping phase in which what we do is we iterate through all the objects out there all the objects not the root all the objects out there if the object is mark if the object is not marked which means the object is not live we free that particular object which means we are deleting the unmarked object and if the object is smart this is another superb optimization or rather nice cheeky optimization or not really optimization but a nice cheeky way of not having to reiterate those objects again so if the object is marked right if the object is sorry if the object is not marked we are mark or we are freeing that a particular object because which means that object is not like we have to free it otherwise if the object is marked we are mark we are unmarking it making it available or basically preparing it for the next cycle because when we initiated the cycle what we were doing is we were always we assume that all the objects are unmarked and then we start marking it starting from the root node correct so in the same iteration of the sweeping phase what we are actually doing is we are not only just freeing the object but we are resetting the mark bit right so that we are prepared for the next garbage collection cycle we don't have to write another for loop to just reset everything it's all part of the sweeping phase right so this way we are i look or we are uh the sweep phase is not only cleaning up the garbage but also preparing your memory management system or your object references for the next garbage collection cycle one very interesting optimization this was the second super optimization i wanted to talk about this one very interesting optimization that you can do is you can skip this part you can actually skip not to reset the bit how like for example we can save that particular effort by by by flipping what the bit means for example you set is marked to false is marked to false implies that my object is not marked but what if in the next cycle is marked equal to false implies that the object is marked this way you stop it so every even cycle like let's say you have the first cycle if the bit is set to one you say that object is marked and the bit is set to zero you say object is unmarked right and in the next cycle what you can say is bit zero like bit is not set implies mark and bit is set implies unmarked and this can continue to flip this way what you can save is you can save one invoking this one line of code over here okay to reset the bit always like here no matter like whenever we're iterating through the objects we are doing either free of that object or setting the bit of it right uh two false or basically basically resetting the bit why would you want to do it if you can flip the meaning although a little complex but it would save you enough computation to make your uh garbage collector perform it right like whenever when you operate at a garbage collector level every single line of code induces a performance uh hamper so you would have to reduce as much of lines of code as much as many instructions as possible so this is one super optimization that you can leverage in order to speed up your entire garbage collection process right by just flipping uh the meaning of the bit so that you don't have to reset it every time right that is amazing optimization that i just found oh okay so yeah that's the basic idea behind uh the garbage uh behind the mark and swift garbage collection thing in the future videos we will take a look into other detail stuff around garbage collection like most probably the next video will be or the next video will be about the tri-color abstraction we will talk about that in detail or next friday right amazing so yeah that's it that's it for this one uh if you guys like this video give this video a thumbs up if you guys like the channel give this channel a sub i post three in-depth engineering videos every week i'll see you in the next one thanks