Stop-and-Copy Garbage Collection Explained: Memory Management

[00:00:03]in this video we're going to look at a second garbage collection technique stop and copy in stop and copy garbage collection memory is organized into two areas we have an old space that's used for allocation and so all of the data that the program is currently using lives in this area called the old space and then there's a new space which is reserved for the garbage collector and so this is not used by the program this is just for the GC and so the first decision in stop and copy garbage collection is that the program can only use half the space and uh there are some techniques more advanced techniques for stop M Copy garbage collection that allow the program to use more than half the space so this isn't as bad as it sounds but fundamentally The Fairly significant fraction of the space has to be reserved for the garbage collector now uh the way allocation works is that there's a heat pointer uh here in the old space and everything to the left of the heat pointer is currently in use this is where all the objects have already been allocated in this area that I just shaded here in red and then uh when it comes time to allocate a new object we simply allocate it at the heat pointer so the heat pointer will simply uh bump up and some block of space uh will be allocated to a the next object that we want to do and it'll just keep marching uh through the old space allocating uh as you allocate more objects okay okay so allocation just advances the heat pointer so one of the advantages actually of stoping copy is a very simple and fast allocation strategy now eventually of course if we allocate over and over again we're going to fill up the old space and so a garbage collection will start uh GC will start uh when the old space is full and what is it going to do it's going to copy all the reachable objects all the reachable objects from the old space into the new space and the beauty of this idea is that when you copy reachable objects the garbage is left behind so you simply pick up all the data that you're using you move it over to the new space and all the junk that you didn't need uh anymore is Left Behind uh in the old space and then after you've copied stuff to the new space uh first of all uh since you left the garbage behind you're using less space than you did before the collection so there's some space available now in the new space for allocating new objects and then you simply swap the roles of the old and new space so the old new spaces are reversed what was old becomes the new and what was new becomes the old and then the program resumes so let's take a look at a quick example here just to get the idea of how this works let's say we have our old space over here this is the old space and we have one root uh which is this object a and so what are we going to do well we're going to make a copy of all the objects reachable from a and we're going to move them over to the new space and what's that going to look like well here it is afterwards but let's trace it out so we start at a and we follow pointers from a we can see there's a pointer to C okay so C is going to be reachable and then there's a pointer to F okay and then F points back to a and that's all the reachable objects so we copy them and notice when we copy them we also copy their pointers and now the pointers have all been changed so in the copy of a it now points to the copy of C okay and of course c will point to the copy of F and there's a little issue here this line is not in the right place so it should look like that and then F uh points back uh to the copy of a so we not only move the object we move their pointers and we adjust them so that we have really copied the whole graph of objects over to the new space now we're using less space And so there's some free space here okay and now this will become the old space this is now our old space and uh this is now the new space which we will use for the next garbage collection to summarize the discussion so far one of the essential problems in stoping copy is to make sure that we find all the reachable objects and we saw this same problem with Mark and sweep garbage collection now the thing that really distinguish is stop and copy is that we're going to copy these objects so when we find a reachable object we copy it into the new space and that means that we have to find and fix all the pointers that point to that object and this is actually not obvious how to do all right because when you find an object of course you can't see all the pointers that point into that object so how we going to do that well here is an idea when we copi the object we're going to store in the old version of it it was called a forwarding pointer to the new copy so let's take a look at what that would how that that looks like uh so we have our old space we have our new space and let's say we've discover some reachable object a in the old space so what we're going to do is we're going to make a copy of it over here in the new space and that's easy enough to do but now what we're going to do is we're going to take a and we're going to reuse its space and we're going to store what's called a forwarding pointer in it so we're going to first of all we're going to Mark somehow that this has been copied so this will have some special mark on it which I'll just you know indicate here with a little purple uh bar or something just we're going to mark it in some way so that we can tell that this object has already been copied and then at a distinguished location in the object we're going to store the forwarding pointer and you can think of this as like a forwarding address so if you know where somebody lives uh you can go to their house and if they have moved you can ask for the forwarding address and that's exactly uh and then you can go off to their new house wherever they've where they've gone to and presumably find them and so that's what's going to happen here if we have a pointer that points into this object later on and maybe much later on in the garbage collection we may discover this pointer we may follow this pointer find out it points to this object realize that this object has moved because we've marked it as an object has moved then we can use the forwarding pointer uh to find out where the new object is and then update this pointer wherever it is uh to point to the new object now just like with Mark and sweep we still have the issue of how to implement the traversal of the object graph without using any extra space again when you these garbage collection algorithms they only get used they only get run in low memory situations and you can't assume that you can build unbounded data structures uh to use with the garbage collector the garbage collector really needs to work uh in constant space and now here is the idea um that will that is used in stoping copy algorithms to solve the problem so we're going to partition the new space and this is just the new space here into three contiguous regions uh we're going to have uh well start with the one at the far right we're going to have the empty region where we're allocating uh new objects and there's an allocation pointer uh that points to the beginning of that region so this is the region that we're filling up with objects that we're copying over and this is just empty unused space now uh immediately to the left of that region are the objects that have already been copied but not scanned okay this is copied and not scanned and what does that mean well that means the optic has been copied over and so we've actually you know made a copy of the object into the new space but we haven't yet looked at its pointers we haven't looked at the pointers inside the object to see where they go and then to the left of that are the objects that have been copied and scanned these are objects that have been copied over and we've also processed all the pointers inside of those objects and so you can think of this area here between the scan pointer and the allocation pointer this is the work list so these are the objects that still need to be processed these are the objects that have been copied over but might yet still point to objects that haven't been copied and so these are the objects where we have to look at their pointers to see whether they point to something that still needs to be copied over uh to finish the garbage collection returning to our little example I'm now going to walk through how a stop and copy garbage collector would collect this particular Heap step by step so notice that we have one root object and it's a okay and I just want to point out that a has one pointer which points to object C all right so the very first step what we're going to do is we're going to copy the a object over to the new space okay and this is literally a bit forbit copy so we just take the bits of a and we do a copy uh without you know doing any inspection of the interior of the object over to the new space and uh how does that work of course our allocation pointer is initially right here uh at the beginning of the new space and then we all we copied this one object over and that that means allocating an object and so now the allocation pointer points to the first word of memory Beyond uh the object we just allocated okay now uh what happens when we copy it over well because this is just a bit forbit copy all the pointers in a Still Point to the objects that they pointed to before which are the objects in the old space so notice now that this copy of a points to the object C in the old space the other thing we do is we leave a forwarding pointer in the old copy of a so we Mark a has only been copied that's why it's grayed out that indicates that this object has already been moved and in this dotted line here indicat that somewhere in a we've stored a pointer to the new copy of a and now we're ready to begin the algorithm so notice that uh we have uh some objects here that have been copied but not scanned so this is our work list so now we're just going to repeatedly uh work off of those objects and how do we know that there are objects in there well we just compare the scan and the allocation pointers so if there if they are different if there's an object uh in between the scan and the allocation pointers at least one object in between the two then there's work to do there's an object that needs to be scanned uh that and and possibly resulting in more objects being moved and allocated so what happens next so object we we process a so we walk over a and find all the pointers in a and we copy any objects that a points to that haven't already been moved and so before we said you know a this this copy of a pointed to the old copy of C so now uh when we discover the the C object it hasn't been moved it's still in the old space so we copy it over and we update the pointer in a to point to the new copy of C now of course uh and then the scan pointer moves over a we've scanned all the pointers in a all right and the allocation pointer also moves because we had to allocate space for C and of course C is just a bit forbit copy of what was in the old space and so it any pointers that it has that point to objects that haven't been moved moved yet just point back into the old space so in this case uh the object C points to the object F uh in the old space and I probably should indicate here here's the original dividing line you know this is the old space over here and this is the new space over there all right and then finally we mark C as having been copied okay as having been moved to the new space and we left a forwarding pointer to it uh in case so we can fix any pointers at point to c that we come across in the future and now uh we have to continue uh scanning objects um that have been copied but not scanned and we can see that there is an object between the scan and the allocation pointer namely C and so we now process all the pointers in C next next we scan C and we discover that it points to F which hasn't been moved yet and so we copy F over uh into the new space and we update the pointer in C and now C has been copied and scanned okay so the scan pointer moves past C and of course F again is a bit forbit copy and so all its pointers into Old space are still pointing to Old space in particular F points to a and the allocation pointer is moved again because we moved f all right and now we have to process F and this will be the last object that we move and what happens well we discover that F points to a okay and a is already marked as having been moved and it has a forwarding pointer so instead of copying a again we simply update the pointer in F that pointed to the old version of a to point to the copy of a okay and so now f is completely scanned uh all the pointers have been processed we didn't allocate any new objects so the allocation pointer didn't move and now the scan pointer and the allocation pointer are equal there are no objects in between them and so our work list is empty and this is the garbage collected Heat this is a complete graph a complete copy I should say of the graph of reachable objects from the old space so now we're done and we simply swap the role of the uh new and old space and we resume the program so and when the program starts running again it will allocate out of this area Okay beyond the allocation pointer until it fills up what is now the old space right and then this will be the new space that will be used for the next garbage collection here's a pseudo code algorithm outlining how stopping copy garbage collection should work so while the scan and allocation pointers are different remember we keep running until the scan pointer catches up with the allocation pointer and they're equal what we're going to do is we're going to look at the object that is at the scan pointer that we call that object o and then for every pointer and O we're going to do the following we're going to find the object o Prime that that pointer points to and then there are two cases one is that there is no forwarding pointer all right and if there's no forwarding pointer then we have to copy that object to new space and that'll involve allocating a new object and updaing the allocation pointer uh then we're going to set here it says the first word I really shouldn't emphasize the first first word set a word so it's a distinguished word that's what's important we have to know which word we're going to use it will always be the same word but anyway we set a word of the old object to point to the new copy um we Mark the old object as copied Mark old object as copied okay so that's so we can tell when if we ever come to a poter to it again we know it's already been moved and then we change p uh the pointer to point to the new copy of Prime all right so if there was that's what we do if there's no forwarding pointer and if there is a forwarding pointer then we simply update the pointer uh to point to the same place as the forwarding pointer and we just repeat this Loop over and over again uh until we've uh scanned all the copied objects so just as was the case with Mark and sweep when we scan an object we have to know how big it is and we also need to know where the pointers in the object are so if we think about this for a minute let's say we're scanning this object so this is our scan pointer and we want now to process all the pointers in it well we have to know where the pointers are so there's a pointer here and there's a pointer here and we need to be able to find those pointers and we don't want to confuse them with other fields of the object that might look like pointers so you know the bit pattern for an integer could look an awful lot like a pointer now this is not a big problem uh because the compiler of course determines the layout of the objects in the Heat and it can store that information somewhere communicated to the garbage collector uh so that it will be able to find the pointers and so you can imagine easily a little bit of uh information uh stored with the program indicating for each type where the pointers are and similarly uh once we scan this object we need to be able to advance our scan pointer uh just past the object so that we can find the beginning of the next object and that's why we need to know this size okay so we need to know that size so that the scan pointer can be uh moved past the object and we can find the beginning of the next object uh another issue is that whenever we do a garbage collection I haven't mentioned this up to this point but it should be clear we also have to scan and copy objects pointed to by the stack and we also have to update pointers in the stack and this can actually turn out to be uh kind of an expensive operation with stop and copy because you know you still have to walk the entire stack uh each time you do a collection in order to make sure that you've copied all the objects pointed to by the stack to conclude a stop and copy I think it's fair to say is generally believed to be the fastest garbage collection technique certainly I believe that variations on stop and copy are the most efficient approaches known to automatic memory management uh allocation is very cheap all right so because all you have to do is increment the heat pointers so you're just moving a a single pointer forward uh to allocate space there's no complicated free list uh to Traverse or decisions to make about where to put the object you know you're just going to allocate it directly at the allocation pointer so you know this this part of memory management is is very inexpensive and at the same time collection is also relatively cheap and and interestingly it's especially cheap if there is a lot of garbage because uh because we're making a copy of the reachable objects uh stop a copy only touches the reachable objects it does not in particular does not touch the garbage so if you think about that for a minute that means that a garbage collection uh is uh in stop and copy is order the size of the live objects so whatever the subgraph is that you're copying that's the cost of a garbage collection and that's in contrast uh to Mark and sweep where the cost is proportional uh to all the memory that you're using because you have the sweep phase where you have to go through and touch every single object whether it's live or garbage okay and so if you have a relatively lot of garbage and a relatively small set of live objects stop and copy is actually much much faster than Mark and Suite now of course the downside of stoping copy is that it moves the objects in some languages in particular C and C++ can't allow you to move objects because uh the address that which an object lives is actually visible exposed in the program and as part of the semantics of the object and so there you really have to use Mark and sweep because you're not allowed to move anything