1 00:00:02,060 --> 00:00:08,017 In this video, we are going to look at the second garbage collection technique, stop 2 00:00:08,017 --> 00:00:14,038 and copy. In stop-and-copy garbage collection memory is organized into two 3 00:00:14,038 --> 00:00:18,405 areas. We have an old space that's used for allocation and so all of the data that 4 00:00:18,405 --> 00:00:23,395 the program is currently using lives in this area called the old space. And then 5 00:00:23,395 --> 00:00:28,778 there's a new space which is reserved for the garbage collector. And so, this is not 6 00:00:28,778 --> 00:00:33,894 used by the program, it's just for the GC. And so the first decision in stop-and-copy 7 00:00:33,894 --> 00:00:38,429 garbage collection is that the program can only use half the space. And there are 8 00:00:38,429 --> 00:00:43,483 some techniques more advance techniques, for stop-and-copy garbage collection that 9 00:00:43,483 --> 00:00:47,903 allow the program to use more than half the space. So, this isn't as bad as it 10 00:00:47,903 --> 00:00:51,845 sounds but fundamentally, a fairly significant fraction of the space has to 11 00:00:51,845 --> 00:00:57,307 be reserved for the garbage collector. Now the way allocation works is that there's a 12 00:00:57,307 --> 00:01:02,073 heat pointer here in the old space and everything to the left of the heat pointer 13 00:01:02,073 --> 00:01:06,512 is currently in use. This is where all the objects have already been allocated in 14 00:01:06,512 --> 00:01:12,023 this area that I just shaded here in red. And then when it comes time to allocate a 15 00:01:12,023 --> 00:01:16,679 new object, we simply allocate it at the heap pointers. So, the heap pointer will 16 00:01:16,679 --> 00:01:21,499 simply bump up and some block of space will be allocated to a, the next object 17 00:01:21,499 --> 00:01:26,837 that we want to do. And it will just keep marching through the old space allocating 18 00:01:27,026 --> 00:01:31,352 as you allocate more objects. Okay, so allocation just advances the heap pointer 19 00:01:31,352 --> 00:01:36,295 so one of the advantages, actually, of stop-and-copy is a very simple and fast 20 00:01:36,295 --> 00:01:42,508 allocation strategy. Now eventually, of course, if we allocate over and over 21 00:01:42,508 --> 00:01:46,548 again, we're going to fill up the old space and so garbage collection will start 22 00:01:46,692 --> 00:01:51,800 GC, will start when the old space is full. And what it's going to do is going to copy 23 00:01:51,800 --> 00:01:56,509 all the reachable objects, all the reachable objects from the old space into 24 00:01:56,509 --> 00:02:00,487 the new space. And the beauty of this idea is that when you copy the reachable 25 00:02:00,487 --> 00:02:05,420 objects, the garbage is left behind. So, you simply pickup all the data that you're 26 00:02:05,420 --> 00:02:10,177 using and move it over to the new space and all the junk that you didn't need 27 00:02:10,359 --> 00:02:15,063 anymore is left behind in the old space. And then, after you copy stuff to the new 28 00:02:15,063 --> 00:02:19,443 space first of all since you left the garbage behind, you're using less space 29 00:02:19,443 --> 00:02:24,050 than you did before the collection. So, there's some space available now in the 30 00:02:24,050 --> 00:02:29,006 new space for allocating new objects. And then, you simply swap the roles of the old 31 00:02:29,006 --> 00:02:33,035 and new space. So, the old and new spaces are reversed what was old becomes the new, 32 00:02:33,035 --> 00:02:38,847 and what was new becomes the old, and then the program resumes. So, let's take a look 33 00:02:38,847 --> 00:02:44,207 at a quick example here just to get a idea of how this works. Let's say we have our 34 00:02:44,207 --> 00:02:48,080 old space over here, this is the old space, and we have one root which is this 35 00:02:48,080 --> 00:02:53,053 object A. And so what we're going to do, well we're going to make a copy of all the 36 00:02:53,053 --> 00:02:58,002 objects reachable from A. We're gonna move them over to the new space. And what 37 00:02:58,002 --> 00:03:02,382 that's going to look like, well, here it is, afterward. But let's trace it out. So, 38 00:03:02,382 --> 00:03:06,386 we started A, we follow pointers from A, we can see there's a pointer to C, okay, 39 00:03:06,386 --> 00:03:11,509 so C is going to be reachable and there's a pointer to F , okay. And then F points 40 00:03:11,509 --> 00:03:16,796 back to A, and that's all the reachable objects so we copy them. And notice when 41 00:03:16,796 --> 00:03:21,628 we copy them, we also copy their pointers, and now the pointers have all been 42 00:03:21,628 --> 00:03:26,099 changed. So, in the copy of A, it now points to the copy of C, okay. And of 43 00:03:26,099 --> 00:03:32,049 course, C will point to the copy of F and there's a little issue here, this line is 44 00:03:32,049 --> 00:03:37,684 not in the right place so it should look like that. And then F points back to the 45 00:03:37,684 --> 00:03:41,657 copy of A. So, what we know, when the object and move their pointers and we 46 00:03:41,657 --> 00:03:46,386 adjust them so that we've really copied the whole graph of objects over to the 47 00:03:46,386 --> 00:03:52,084 news space. Now, we're using less space so there's some free space here, okay. And 48 00:03:52,084 --> 00:03:57,557 now, this will become the old space. This now our old space and this is now the new 49 00:03:57,557 --> 00:04:02,731 space which we will use for the next garbage collection. To summarize the 50 00:04:02,731 --> 00:04:08,200 discussi on so far, one of the essential problems in stop-and-copy is to make sure 51 00:04:08,200 --> 00:04:12,665 that we find all the reachable objects and we saw this same problem with 52 00:04:12,665 --> 00:04:16,893 mark-and-sweep garbage collection. Now, the thing that really distinguishes 53 00:04:16,893 --> 00:04:20,995 stop-and-copy is that we're going to copy these objects. So, when we find a 54 00:04:20,995 --> 00:04:26,147 reachable object we copy it into the new space. And that means that we have to find 55 00:04:26,147 --> 00:04:30,485 and fix all the pointers that point to that object and this is actually not 56 00:04:30,485 --> 00:04:34,350 obvious how to do, alright. Cuz when you find an object, of course, you can't see 57 00:04:34,531 --> 00:04:39,216 all the pointers that point into that object. So, how are we going to do that? 58 00:04:39,216 --> 00:04:44,345 Well, here is an idea. Well, we copy the object, we're going to store in the old 59 00:04:44,345 --> 00:04:49,332 version of it, it was called, a forwarding pointer to the new copy. So, let's take a 60 00:04:49,332 --> 00:04:54,144 look at what that would how that would, how that looks like. So we have our old 61 00:04:54,144 --> 00:04:58,696 space, we have our new space. And let's say, we discover some reachable object A 62 00:04:58,696 --> 00:05:02,960 in the old space. So, what we're going to do is we're going to make a copy of it 63 00:05:02,960 --> 00:05:07,779 over here in the new space and that's easy enough to do. But now what we're going to 64 00:05:07,779 --> 00:05:12,434 do is we're gonna take A and we're going to reuse its space and we're gonna store 65 00:05:12,434 --> 00:05:16,849 what's called a forwarding pointer in it. So, we're going to, yeah, first of all, 66 00:05:16,849 --> 00:05:20,460 we're going to mark somehow that this has been copied. So, this will have some 67 00:05:20,460 --> 00:05:24,415 special mark on it which I'll just, you know, indicate with here with a purple bar 68 00:05:24,415 --> 00:05:28,191 something. This is we're marking someway so that we can tell this object has 69 00:05:28,191 --> 00:05:32,071 already been copied. And then at a. At a distinguished location in the object, 70 00:05:32,071 --> 00:05:36,243 we're going to store the forwarding pointer. And you can think of this as like 71 00:05:36,243 --> 00:05:39,778 a forwarding address. So, if you know where somebody lives you can go to their 72 00:05:39,778 --> 00:05:43,366 house and if they have moved, you can ask for the forwarding address. And that's 73 00:05:43,366 --> 00:05:47,928 exactly and then you can go off to their new house wherever they've wherever 74 00:05:47,928 --> 00:05:52,071 they've gone to and presumably find them. And so, that's what's going to happen 75 00:05:52,071 --> 00:05:56,211 here. If we have a pointer that points into this object later on and maybe much 76 00:05:56,211 --> 00:06:01,207 later on in the garbage collection, we may discover this pointer, we may follow this 77 00:06:01,207 --> 00:06:05,338 pointer, find out it points in this object, realize that this object has moved 78 00:06:05,338 --> 00:06:10,360 because we've marked it and the object was moved. And then we can use the forwarding 79 00:06:10,360 --> 00:06:14,657 pointer to find out where the new object is and then update this pointer wherever 80 00:06:14,657 --> 00:06:20,624 it is to point to the new object. Now, just like with mark-and-sweep, we still 81 00:06:20,624 --> 00:06:25,077 have the issue of how to implement the traversal of the object graph without 82 00:06:25,077 --> 00:06:31,329 using any extra space. Again, when these garbage collection algorithms, they only 83 00:06:31,329 --> 00:06:36,470 get used, they only get run in low memory situations. And you can't assume that you 84 00:06:36,470 --> 00:06:42,021 can build unbounded data structures to use with the garbage collectors. The garbage 85 00:06:42,021 --> 00:06:47,079 collector really needs to work in constants base. And now here is the idea 86 00:06:47,283 --> 00:06:52,526 that will, that is used in stop-and-copy algorithms to solve the problem. So, we're 87 00:06:52,526 --> 00:06:57,009 going partition in new space and this is just the new space here into three 88 00:06:57,009 --> 00:07:02,162 contiguous regions. We're going to have we'll start with the one on the far right. 89 00:07:02,162 --> 00:07:06,481 We're going to have the empty region where we're allocating new objects. And there's 90 00:07:06,481 --> 00:07:11,558 an allocation pointer that points to the beginning of that region. So this is the 91 00:07:11,558 --> 00:07:15,752 region that we're filling up with objects that we're copying over and this is just 92 00:07:15,752 --> 00:07:20,754 empty unused space. Now, immediately to the left of that region are the objects 93 00:07:20,754 --> 00:07:28,184 that have already been copied, but not scanned, okay? This is copied and not 94 00:07:28,184 --> 00:07:33,649 scanned. And, what does that mean? Well, that means that the object has been copied 95 00:07:33,649 --> 00:07:37,427 over. And so, we've actually, you know, made a copy of the object into the new 96 00:07:37,427 --> 00:07:41,280 space. But we haven't yet looked at its pointers. We haven't yet looked at the 97 00:07:41,280 --> 00:07:45,059 pointers inside the object to see where they go. And then, to the left of that, 98 00:07:45,059 --> 00:07:49,033 are the objects that have been copied and scanned. These are objects that have been 99 00:07:49,033 --> 00:07:53,077 copied over. And we've also processed all the pointers inside of those obje cts. And 100 00:07:53,077 --> 00:07:56,776 so, you can think of this area here, between the scanned pointer and the 101 00:07:56,776 --> 00:08:00,606 allegation pointer, this is the work quest. So, these are the objects that 102 00:08:00,606 --> 00:08:04,780 still need to be processed. These are the objects that have been copied over but 103 00:08:04,780 --> 00:08:09,439 might yet still point to objects that haven't been copied. And so, these are the 104 00:08:09,439 --> 00:08:13,484 objects where we have to look at their pointers to see whether they point to 105 00:08:13,484 --> 00:08:19,477 something that still needs to be copied over to finish the garbage collection. 106 00:08:19,477 --> 00:08:24,971 Returning to our little example, I'm now going to walk through how a stop-and-copy 107 00:08:24,971 --> 00:08:29,698 garbage collector would collect this particular heap step by step. So, notice 108 00:08:29,698 --> 00:08:35,419 that we only have one root object and it's A, okay, I just want to point out that A 109 00:08:35,419 --> 00:08:40,691 has one pointer which points to object C, alright. So, at the very first step, what 110 00:08:40,691 --> 00:08:45,699 we're going to do is we're going to copy the A object over to the new space, okay. 111 00:08:45,699 --> 00:08:50,543 And this is literally a byte for byte copy. So, we just take the bytes of A and 112 00:08:50,543 --> 00:08:55,964 we do a copy without, you know, doing any inspection of the interior of the object, 113 00:08:55,964 --> 00:09:00,543 over to the new space. And how's that work? Of course, our allocation pointer 114 00:09:00,543 --> 00:09:05,131 isn't in, initially right here at the beginning of the new space. And then we 115 00:09:05,131 --> 00:09:10,328 add and we copy this one object over. And then that means allocating an object and 116 00:09:10,328 --> 00:09:15,125 so now, the allocation pointer points to the first word of memory, beyond the 117 00:09:15,125 --> 00:09:19,601 object that we just allocated, okay. Now what happens when we copy it over? Well, 118 00:09:19,601 --> 00:09:23,733 because it is just a byte for byte copy, all the pointers in A still point to the 119 00:09:23,733 --> 00:09:28,713 objects as they pointed to before which are the objects in old space. And notice 120 00:09:28,713 --> 00:09:33,165 now that this copy of A points to the object C in the old space. The other thing 121 00:09:33,165 --> 00:09:38,291 we do is we leave a forwarding pointer in the old copy of A. So, we mark A as having 122 00:09:38,291 --> 00:09:43,139 been copied, that's why it's grayed out. Indicates that this object has already 123 00:09:43,139 --> 00:09:48,529 been moved. And that this dotted line here indicates that somewhere, we stored a 124 00:09:48,529 --> 00:09:53,338 pointer to the new copy of A. And now, we're ready to begin the algorithms. And 125 00:09:53,338 --> 00:09:58,546 not ice that we have some objects here that have been copied but not scanned so 126 00:09:58,546 --> 00:10:03,094 this is our work list. So, now it's going to repeatedly work off of those objects 127 00:10:03,094 --> 00:10:08,010 and how do we know they're objects in there? Well, we just compare the scan and 128 00:10:08,010 --> 00:10:12,383 the allocation pointers. So, if they're if they are different, if there's an object 129 00:10:12,538 --> 00:10:16,654 in between the scan and the allocation pointer, at least one object between the 130 00:10:16,654 --> 00:10:21,196 two, then there's work to do. There's an object that needs to be scanned that and, 131 00:10:21,196 --> 00:10:25,510 and possibly resulting in more objects being moved and allocated. So, what 132 00:10:25,510 --> 00:10:31,471 happens next? So, object, we, we process A, so we walk over A and find all the 133 00:10:31,471 --> 00:10:37,168 pointers in A. And we copy any objects that it points to that haven't already 134 00:10:37,168 --> 00:10:42,502 been moved. And so, before we said, you know, the A, this, this copy of A pointed 135 00:10:42,502 --> 00:10:47,471 to the old copy of C. So, now what we discover the C object, it hasn't been 136 00:10:47,471 --> 00:10:53,735 moved, it's still in the old space. So, we copy it over and we update the pointer in 137 00:10:53,735 --> 00:10:58,811 A to point to the new copy of C. Now, of course and then the scan pointer moves 138 00:10:58,811 --> 00:11:03,206 over A. We've scanned all the pointers in A, alright. And the allocation pointer 139 00:11:03,206 --> 00:11:07,765 also moves because we had to allocate space for C. And of course, C is just a 140 00:11:07,765 --> 00:11:12,796 byte for byte copy of what was in the old space. And so it, any pointers that it has 141 00:11:12,952 --> 00:11:17,362 that point to objects that haven't been moved yet, moved yet just point back into 142 00:11:17,362 --> 00:11:22,584 the old space. So, in this case the object C points to the object F in the old space. 143 00:11:22,584 --> 00:11:26,758 And I probably should indicate here, here's the original dividing line, you 144 00:11:26,758 --> 00:11:31,586 know, this is the old space over here and this is the new space over there, alright. 145 00:11:31,586 --> 00:11:35,834 And finally we mark C as having been copied, having been moved to the new space 146 00:11:35,834 --> 00:11:40,383 and we left a forwarding pointer to it in case so we can fix any pointers that point 147 00:11:40,383 --> 00:11:45,996 to C that we come across in the future. And now we have to continue scanning 148 00:11:45,996 --> 00:11:51,495 objects that have been copied but not scanned. And we can see that there is an 149 00:11:51,495 --> 00:11:56,277 object between the scan and the allocatio n pointer namely C and so we'll now 150 00:11:56,277 --> 00:12:02,662 process all the pointers in C. Next, we scan C. And, we discover that it points to 151 00:12:02,662 --> 00:12:08,384 F. Which hasn't been moved yet and so we copy F over into the new space and we 152 00:12:08,384 --> 00:12:13,554 update the pointer in C. And now C has been copied and scanned, okay. So, the 153 00:12:13,554 --> 00:12:19,075 scan pointer moves past C and of course, F again is a byte for byte copy and so all 154 00:12:19,075 --> 00:12:24,234 it's pointers into old space are still pointing to old space, in particular F 155 00:12:24,234 --> 00:12:29,677 points to A and the allocation pointer is moved again because we moved F, alright. 156 00:12:29,677 --> 00:12:35,217 And now, we have to process F. And this will be the last object that we move. And 157 00:12:35,217 --> 00:12:41,317 what happens, well, we discover that F points to A, okay. And A is already marked 158 00:12:41,317 --> 00:12:46,996 as having been moved and it has a forwarding pointer. So, instead of copying 159 00:12:46,996 --> 00:12:52,891 A again, we simply update the pointer in F that pointed to the old version of A to 160 00:12:52,891 --> 00:12:58,378 point to the copy of A, okay. And so, now F is completely scanned. All the pointers 161 00:12:58,378 --> 00:13:03,088 in F have been processed. We didn't allocate any new objects so the allocation 162 00:13:03,088 --> 00:13:07,713 pointer didn't move and now the scan pointer and the allocation pointer are 163 00:13:07,713 --> 00:13:12,435 equal. There are no objects in between them and so our work list is empty and 164 00:13:12,435 --> 00:13:17,372 this is the garbage collected heap. This is a complete graph, a complete copy of 165 00:13:17,372 --> 00:13:22,796 its A, of the graph of reachable objects from the old space. So, now we're done and 166 00:13:22,796 --> 00:13:28,194 we simply swap the role of the new and old space and we resume the program so that 167 00:13:28,194 --> 00:13:33,654 when the program starts running again, it will allocate out of this area and it'll 168 00:13:33,654 --> 00:13:38,705 be on the allocation pointer until it fills up what is now the old space, you 169 00:13:38,705 --> 00:13:43,934 know, and then this will be the new space that will be used for the next garbage 170 00:13:43,934 --> 00:13:50,021 collection. Here's a pseudo code algorithm outlining how stop-and-copy garbage 171 00:13:50,021 --> 00:13:53,712 collection should work. So, while the scan and allocation pointers are different, 172 00:13:53,712 --> 00:13:57,581 remember, we keep running until the scan pointer catches up with the allocation 173 00:13:57,581 --> 00:14:01,426 pointer and they're equal. What we're going to do is we're going to look at the 174 00:14:01,426 --> 00:14:05,321 object that is at the scan pointer. That we'll call that objec t , and then for 175 00:14:05,321 --> 00:14:10,019 every pointer in O, we're going to do the following. We're going to find the object 176 00:14:10,019 --> 00:14:14,459 O' that, that pointer points to. And then there are two cases. One is that there is 177 00:14:14,459 --> 00:14:18,160 no forwarding pointer, alright. And if there's no forwarding pointer, then we 178 00:14:18,160 --> 00:14:22,292 have to copy that object to new space and that will involve allocating a new object 179 00:14:22,292 --> 00:14:25,898 and updating the allocation pointer. Then we're going to set and here it says the 180 00:14:25,898 --> 00:14:29,479 first word, they really shouldn't emphasize the first word. Set a word. So, 181 00:14:29,479 --> 00:14:33,443 it's a distinguished word, that's what's important. We have to know which word 182 00:14:33,443 --> 00:14:37,131 we're going to use and will always be the same word. But anyways, we set a word of 183 00:14:37,131 --> 00:14:43,776 the old object to point to the new copy. We mark the old object as copied. Mark old 184 00:14:43,776 --> 00:14:50,636 object as copied, okay. So, that's so that we can tell if we ever come to a pointer 185 00:14:50,636 --> 00:14:55,973 to it again, we know it's already been moved and then we change p, the pointer, 186 00:14:55,973 --> 00:15:01,383 to point to the new copy of O', alright. So, if there was, that's what we do if 187 00:15:01,383 --> 00:15:05,844 there is no forwarding pointer. And if there is a forwarding pointer, then we 188 00:15:05,844 --> 00:15:11,731 simply update the pointer to point to the same place as the forwarding pointer. And 189 00:15:11,731 --> 00:15:18,039 we just repeat this loop over and over again until we've scanned all the copied 190 00:15:18,039 --> 00:15:23,104 options. So, just as well as the case with mark-and-sweep. When we scan an object, we 191 00:15:23,104 --> 00:15:27,036 have to know how big it is and we also need to know where the pointers and the 192 00:15:27,036 --> 00:15:30,996 object are. So, if we think about this for a minute, let's say we're scanning this 193 00:15:30,996 --> 00:15:35,223 object, so this is our scan pointer and we want now to process all the pointers in 194 00:15:35,223 --> 00:15:39,024 it, well, we have to know where the pointers are. So, there's a pointer here 195 00:15:39,024 --> 00:15:42,943 and there's a pointer here and we'll be able to find those pointers and we don't 196 00:15:42,943 --> 00:15:46,963 want to confuse them with other fields of the object that might look like pointers. 197 00:15:46,963 --> 00:15:50,966 So, in a bit pattern for an integer could look an awful lot like a pointer. Now, 198 00:15:50,966 --> 00:15:55,974 this is not a big problem because the compiler, of course, in terms of, a lot of 199 00:15:55,974 --> 00:16:00,799 the objects in the heap and it can stor e that information somewhere communicated to 200 00:16:00,799 --> 00:16:05,244 the garbage collector so that it will be able to find the pointers. So, you can 201 00:16:05,244 --> 00:16:10,035 imagine easily a little bit of information stored with the program indicating for 202 00:16:10,035 --> 00:16:14,014 each type where the pointers are. And similarly once we've scanned this object, 203 00:16:14,014 --> 00:16:18,657 we need to be able to advance our scan pointer just past the object so that we 204 00:16:18,657 --> 00:16:23,067 can find the beginning of the next object and that's why we need to know the size, 205 00:16:23,067 --> 00:16:27,150 okay. So, we need to know that size so that the scan pointer can be moved past 206 00:16:27,150 --> 00:16:32,011 the object and we can find the beginning of the next object. Another issue is that 207 00:16:32,011 --> 00:16:36,151 whenever we do a garbage collection, I haven't mentioned this up to this point 208 00:16:36,151 --> 00:16:40,334 but it should be clear, we also have to scan and copy objects pointed to by the 209 00:16:40,334 --> 00:16:45,219 stack. And we also have to update pointers in the stack. And this can actually turn 210 00:16:45,219 --> 00:16:49,541 out to be kind of an expensive operation with stop-and-copy because, you know, you 211 00:16:49,541 --> 00:16:54,499 still have to walk the entire stack each time you do a collection in order to make 212 00:16:54,499 --> 00:17:00,794 sure that you've copied all the objects pointed to by the stack. To conclude 213 00:17:01,043 --> 00:17:06,008 stop-and-copy, I think it's fair to say, is generally believed to be the fastest 214 00:17:06,008 --> 00:17:10,091 garbage collection technique. Certainly, I believe that variations on stop-and- copy 215 00:17:10,091 --> 00:17:15,770 are the most efficient approaches known to automatic memory management. Allocation is 216 00:17:15,770 --> 00:17:19,764 very cheap, alright. So, cuz all you have to do is increment the e-pointer. So, 217 00:17:19,764 --> 00:17:23,948 you're just moving a, a, single pointer forward to allocate space. There's no 218 00:17:23,948 --> 00:17:28,439 complicated free list future verse or decisions to make about where to put the 219 00:17:28,439 --> 00:17:32,540 object, you know, you're just going to allocate it directly at the allocation 220 00:17:32,540 --> 00:17:36,858 pointer. So, you know, this, this part of memory management is, is very inexpensive. 221 00:17:36,858 --> 00:17:41,483 And at the same time, collection is also relatively cheap. And, and interestingly 222 00:17:41,483 --> 00:17:47,191 it's especially cheap if there is a lot of garbage because, because of making a copy 223 00:17:47,191 --> 00:17:53,667 of the reachable objects stop-and-copy only touches the reac hable object, It is 224 00:17:53,667 --> 00:18:00,276 not, in particular, does not touch the garbage. So, if you think about that for a 225 00:18:00,276 --> 00:18:06,558 minute, that means that the garbage collection is in stop-and-copy is order 226 00:18:06,558 --> 00:18:12,115 the size of the live objects. So, whatever the sub-graph is that you're copying, 227 00:18:12,115 --> 00:18:17,872 that's the cost of a garbage collection and that's in contrast to mark-and-sweep 228 00:18:17,872 --> 00:18:23,608 were the cost is proportional to all the memory that you're using cuz you have the 229 00:18:23,608 --> 00:18:28,070 sweep phase where you have to go through and touch every single object whether it's 230 00:18:28,070 --> 00:18:33,006 live or garbage, okay. And so, if you have a relatively lot of garbage and a 231 00:18:33,006 --> 00:18:37,034 relatively small set of live objects, stop-and-copy is actually much, much 232 00:18:37,034 --> 00:18:42,022 faster than mark-and-sweep. Now, of course the down side of stop-and-copy is that it 233 00:18:42,022 --> 00:18:46,079 moves the objects in some languages, in particular C and C++, can't allow you to 234 00:18:46,079 --> 00:18:51,067 move objects because the address that which an object lives is actually visible 235 00:18:51,067 --> 00:18:56,054 exposed in the program and is part of the semantics of the object. And so there, you 236 00:18:56,054 --> 00:19:02,042 really have to use mark-and-sweep because you're not allowed to move anything.