Cheney's Garbage Collection Algorithm Explained | Two-Finger Approach

[00:00:00]in the current segment i actually want to talk about another type of garbage collection algorithm which i did not talk about last week and that's known as the cheney algorithm it's actually has a more generic name it's called the two finger approach or the two-finger algorithm it has many variants but i want to talk about the basic uh algorithm and then from now you can read on if you want about all the variants so the way it works is the following we have a we have a uh memory and suppose that our memory is actually divided into two parts let's call it two parts the two the two first part and the second part is called the front part we have the two and the front now the way it works is the following we go and we allocate uh memory every time you do a new every time you actually go and you and you make a you know you ask for dynamic memory dynamic keep remembering what we do is we allocate our memory from the two notice so slowly memory will actually fill up which makes a lot of sense right slowly we fill up the two portion will get filled up now not all these guys are actually alive some of them already you know been you know already garbage was known as garbage and some of them actually alive now again the definition of alive means that you can get to it from the live set meaning there's like a one-time stack somewhere and there's globals and somewhere in the runtime stack there is a pointer into the heap into that location it could very well very well be that this location leads to that location that could very well very very well happen but in a sense that's what the runtime stack is that's what's called known as the as the live set that's what's known as live set now we need to ask ourselves what happens when the memory is depleted meaning if you ask for another new there is no wait there's no way to actually get more memory because the two is full so the first thing we do is we change the name this becomes the from and this becomes the two that's the first thing we do why do we have those names the reason we have those names is because um we are taking from the from and putting into the two what does that mean well we start from again from the one-time stack or the global which is known as the live stand we started the live set which includes the runtime stack and the globals and we follow them into the heap we follow them into the heap so for example suppose it said here i'm just throwing suppose we have the following let's just make the example more you know more complicated a bit just so we can have a you know a nice sample of what's going on suppose we had two pointers pointing into the heap suppose these guys this guy was also pointing at this memory just let's assume okay and suppose that this guy was also garbage okay now oh we started we start from the right we have we put one finger at the first empty location in the two okay and we put another finger at the last full location which in the beginning obviously is the same place right it's the last the first empty one last four were actually exactly the same now what we do is the following we follow the live set into the heap and we we get to see let's put numbers here let's call this 9 10 and 11.

[00:03:44]okay let's just put that there okay so we can follow them around now if we we find the nine we find the nine and we move it into the heap now one of these pointers will actually move because the next free location right the next free location is now over here that's our next free location right that's our next relocation so now we have one finger pointing to the to the base of the two and one point to moving ahead next we say okay what is the next uh what is the next value we can reach from the live set and we get the 11 which is fine so we now i skipped a step we move the nine to down here i skipped a couple of steps okay next next thing we do is we put a pointer here to the new location where it is so we can find it if we need to okay and we update the pointer at the runtime stack to point at the new location meaning that if we want to go from the runtime stack to find the variable we can find it there it is right that's the number nine now why do we need to store pointer at the previous location to the new location we'll see in a minute but that's we did that we finished step step one step two we do the same thing for the 11. notice we copy the 11 down to here and we move the 11 down to here we put a pointer at the old location pointing to the new location we move the red finger here that we have move it down to the next free empty spot right we update the pointer over here we update the pointer to the new location and we are finished now once we finished following the live set into the heap we're going to have a very interesting picture notice in the two we have all those that can be reached directly from the live set 9 11. we have pointers in the old locations showing where the new locations are we have the pointers on the heap updated to the new locations and now we finish that step the next part we want to do is to see if we need to follow through further in so now notice if we copy look at the nine if we actually really look at the nine the nine had a pointer to right there right that's what it had a pointer to the 11 happens to also have a pointer to the same location notice the two notice the two black notice the two black arrows that we have at the top right over here so i just made them in blue just from from different locations but they're pointing to the same place they actually point in the same place so now we do is we start from the first finger this is why it's called the two finger approach that's the reason why it's called a two finger approach we have actually two fingers or two red arrows that we have one shows the last the the last um variable that we already dealt with one shows the first empty spot so we start from the nine and we say okay can we follow from the nine into the heap and the answer to that is yes that's the 10.

[00:07:19]so now we follow the same procedure we copy the 10 into the first empty spot we move the finger down okay we update the pointer we put a pointer to where the new variable is and we up to the pointer that was pointing to it we update the point that was pointed to it to the new location okay so now if we ask ourselves at this point in time right now right is the nine pointing at the 10 yes did the knight point at the 10 beforehand yes right so all so right now the variable 9 10 is the way it should be everything's okay just in a new location in memory okay and then once we finish that we update this first finger that we had right here we update the first finger to point at the next variable because that's the next one we have to deal with now we say okay 11 let's follow 11 into the heap if we follow 11 into the heap we find that we reach the 10 up on top and it has a pointer down into the two on the bottom so we find the new location and we say okay so the new location says that 11 has to we don't have to move anything because the 10 already moved so the new location says okay so just update the pointer so we update the pointers and here the point is updated and we say that 11 should point at the 10 right and we can move we finish the 11 or we can move the finger further down now the finger is pointing at the 10.

[00:09:08]is the 10 p can you follow through from the 10 into the into the from the answer is no so the finger moves down another one finger moves down another one right and now notice what happens the two fingers are actually pointed at the same location the minute the two fingers point at the same location we are finished and if we actually look at the memory right now we say okay notice that from let's ignore the top half of the picture and look just the bottom half of the picture if we start from the wrong time stack for the first location let's call it location a and we follow through it used to point to the 9 which pointed at the 10 it's still pointing at the 9 which is pointing at the 10.

[00:09:49]if we look at location b that used to point to the 11 which pointed at the 10 and now it's still pointing at that 11 which points to the 10 so we have all our memory the way we're supposed to have it now all of this down here this is our our new free list we will allocate from now on we will allocate only from the two that's what we did till now and all the memory up on top it's just garbage i couldn't care less what's there anymore notice there's nothing pointing towards anywhere there's nothing pointing to it anywhere in in the code or the data pointing to those locations and therefore they are not needed and that's fine concern they can be recycled so now we stop and look right now we keep going and we allocate from the free list every time more and more and more and more at a certain point in time again this will fill up some of it will be garbage some of it will not don't know which ones will be garbage which ones will not right and the minute we can't allocate any more memory we just start the cycle again but all the way around we call this the two we call this the firm and we just do the same thing the other way around okay and therefore the memory is actually reclaimed this is what's known as a chaining algorithm it's actually a two-finger approach it's the class of algorithms called two-finger approach and it actually works well in recycling all the data