1 00:00:02,077 --> 00:00:07,058 In this video we're going to start our discussion of garbage collection or 2 00:00:07,058 --> 00:00:11,773 automatic memory management. This will take us a few videos to get through and 3 00:00:11,773 --> 00:00:17,044 this first video is just an overview of the problem. And then we'll talk about 4 00:00:17,044 --> 00:00:23,056 specific techniques in subsequent videos. To set the stage, let's first talk about 5 00:00:23,056 --> 00:00:28,004 the problem that we're trying to solve. So, if one has to manage memory manually, 6 00:00:28,004 --> 00:00:31,940 meaning you have to do all the allocation and deallocation explicitly yourself, that 7 00:00:31,940 --> 00:00:36,297 is a hard way to programming leads to certain kinds of bugs that are very 8 00:00:36,297 --> 00:00:41,056 difficult to eliminate from programs. So, in particular, these days you see this 9 00:00:41,056 --> 00:00:46,289 primarily in C and C++ programs. Those are the main languages that are used that have 10 00:00:46,289 --> 00:00:50,548 manual memory management. And, the kinds of storage bugs that you can get because 11 00:00:50,548 --> 00:00:55,505 it has manual memory management are things like forgetting to free unused memory so 12 00:00:55,505 --> 00:00:58,559 that's a, it means a memory leak. Dereferencing dangling pointers, 13 00:00:58,559 --> 00:01:03,050 overriding parts of a data structure, unintentionally. And actually there's a 14 00:01:03,050 --> 00:01:07,052 few more things, although these are probably the three most common problems 15 00:01:07,052 --> 00:01:12,341 that people have and these bugs are really hard to find. And I want to emphasize that 16 00:01:12,341 --> 00:01:17,420 these kinds of bugs are often some of the very, very last bugs to be found in, in 17 00:01:17,420 --> 00:01:22,463 complex systems. They often persist into production and sometimes for a very long 18 00:01:22,463 --> 00:01:28,394 time after the code is in production use. And why is that? The reason is that these, 19 00:01:28,394 --> 00:01:33,018 these kinds of bugs, storage bugs, typically have effects that are far away 20 00:01:33,018 --> 00:01:39,010 in time and space from the source and so how can that happen? Well let's think 21 00:01:39,010 --> 00:01:46,251 about some object in memory and now let's say only on interesting you might have 22 00:01:46,251 --> 00:01:49,803 some fields, let's say you have a few fields and I am keeping some pointers to 23 00:01:49,803 --> 00:01:55,018 it. So somewhere on program is a reference to this particular object and now I come 24 00:01:55,018 --> 00:01:58,790 along and free it. So I am doing my own memory management like free this object 25 00:01:58,790 --> 00:02:03,734 but I forget that I had this pointer. And so now what's happen all the storage has 26 00:02:03,734 --> 00:02:08,093 been freed it's no longer really valid memory but the pointer still exist to it. 27 00:02:08,093 --> 00:02:13,080 And then when I come along and allocate something else it might allocate the same 28 00:02:13,080 --> 00:02:18,033 piece of memory. So this might now be a different kind of object, okay. So I might 29 00:02:18,033 --> 00:02:22,071 have a different type here even. In this memory might be used for something 30 00:02:22,071 --> 00:02:26,088 completely different and now I have a pointer that says it thinks it's a red 31 00:02:26,088 --> 00:02:31,010 object, it's pointing to a blue object. And when I come in and write stuff into 32 00:02:31,010 --> 00:02:35,021 this object, of course I'm just writing nonsense. So I, this, whatever piece of 33 00:02:35,021 --> 00:02:39,353 code holds this pointer thinks it's still the old kind of object. It will write some 34 00:02:39,353 --> 00:02:44,063 bits in here and when I go in some other part of the program possibly quite far 35 00:02:44,063 --> 00:02:48,831 away go out and read out, this is a blue object, I'll just get some random garbage 36 00:02:48,831 --> 00:02:55,785 and that will probably cause my program to cash. So this is a very, very old problem. 37 00:02:55,785 --> 00:02:59,922 It's been studied since at least the 1950s. It was first thought about 38 00:02:59,922 --> 00:03:04,356 carefully in list. And there are some well-known techniques for completely 39 00:03:04,356 --> 00:03:09,545 automatic memory management so you don't have to manage memory yourself. And this 40 00:03:09,545 --> 00:03:14,087 only became mainstream actually in the 1990s so with the popularity of Java. 41 00:03:14,087 --> 00:03:18,560 Prior to that time there was really no mainstream language that used automatic 42 00:03:18,560 --> 00:03:23,113 memory managements so that's really just in the last now almost twenty years that 43 00:03:23,113 --> 00:03:29,370 garbage collection and automatic memory management in general became a popular 44 00:03:29,370 --> 00:03:33,484 mainstream programming technique. So the basic strategy in automatic memory 45 00:03:33,484 --> 00:03:38,369 management is, is pretty simple. So, when an object is created, when we allocate a 46 00:03:38,369 --> 00:03:43,237 new object the system, the run time system will find some unused space for that 47 00:03:43,237 --> 00:03:49,254 object and it will just allocate it. So whenever you say new of some class name in 48 00:03:49,254 --> 00:03:53,225 Cool. Some memory is automatically allocated by the system, some previously 49 00:03:53,225 --> 00:03:58,048 unused memory is automatically allocated by the system for that object. And if you 50 00:03:58,048 --> 00:04:02,292 keep doing this over and over and over again and after awhile you're going to run 51 00:04:02,292 --> 00:04:07,041 out of space. So eventually there is no more unused space left for additional obj 52 00:04:07,041 --> 00:04:11,956 ects. And at that point you have to do something. You have to reclaim some of the 53 00:04:11,956 --> 00:04:16,959 space in order to allocate more objects and the observation that garbage 54 00:04:16,959 --> 00:04:22,141 collection systems rely upon is that some of the spaces being used is probably 55 00:04:22,141 --> 00:04:26,896 occupied by objects that will never be used again. So they, some of these objects 56 00:04:26,896 --> 00:04:31,949 are not going to be referred to again by the program and if we can figure out which 57 00:04:31,949 --> 00:04:36,997 objects those are, which objects are not longer going to be used. Then we could 58 00:04:36,997 --> 00:04:42,012 deallocate them and reuse the space for new objects. So the big question is, how 59 00:04:42,012 --> 00:04:46,698 can we know that an object will never be used again? And, most of the garbage 60 00:04:46,698 --> 00:04:51,799 collection techniques that are out there today rely on the following observation, 61 00:04:51,799 --> 00:04:56,117 then that's that a program can only use the objects that it can find and what do 62 00:04:56,117 --> 00:05:00,953 we mean by that? So I'm going to switch colors so let's take a look at this piece 63 00:05:00,953 --> 00:05:05,333 of code so what's going to happen? Well when we execute this the first thing that 64 00:05:05,333 --> 00:05:10,656 happens is we allocate an A object, alright. And it's assigned x, so x will 65 00:05:10,656 --> 00:05:16,716 have a pointer to that object. And then, in the body of this let, what's going to 66 00:05:16,716 --> 00:05:23,431 happen well, we're going to assign x, the value that y points to so y is another 67 00:05:23,431 --> 00:05:29,360 variable. It points to some other objects in memory, okay. And what's going to 68 00:05:29,360 --> 00:05:36,405 happen, when we execute this assignment is that we're going to remove the old value 69 00:05:36,405 --> 00:05:43,905 of x and x now is going to point to this object. Now observe that this object a is 70 00:05:43,905 --> 00:05:50,345 unreachable. Meaning it has no references to it. There are no longer any pointers to 71 00:05:50,345 --> 00:05:55,446 it. And how do I know that? Well, a brand new here when it was created. I only 72 00:05:55,446 --> 00:06:00,241 created one pointer to it, x and then I immediately assigned x to something else. 73 00:06:00,241 --> 00:06:04,635 So I dropped the only pointer to A. There is no reference to A anywhere in the 74 00:06:04,635 --> 00:06:10,010 program. And so the program will never be able to find it again. The program, if no 75 00:06:10,010 --> 00:06:14,061 variable or data structure in the program has a pointer to A, then A can never be 76 00:06:14,061 --> 00:06:19,139 referred to by the program in the future. So any kind of subsequent execution of the 77 00:06:19,139 --> 00:06:24,057 program has no p ointers to A and therefore it will never use A again and so 78 00:06:24,057 --> 00:06:29,934 the space ray can be reclaimed and used for another object. Now it turns out that 79 00:06:29,934 --> 00:06:33,867 we need a more general definition of object reachability than this example 80 00:06:33,867 --> 00:06:38,633 illustrates so let's take a look at that. We're going to say that an object x is 81 00:06:38,633 --> 00:06:42,615 reachable if and only if one of the following two things is true. So either A 82 00:06:42,615 --> 00:06:47,319 register contains a pointer to x. So either the x is reachable immediately from 83 00:06:47,319 --> 00:06:51,915 some register. Remember that the registers contain things like the local variables in 84 00:06:51,915 --> 00:06:57,151 there and the intermediate expressions and they're just you know, the values that the 85 00:06:57,151 --> 00:07:02,003 program has immediate access to or another reachable object y contains a pointer to 86 00:07:02,003 --> 00:07:06,907 x. And so what does this say? Well, this says you're going start at the register so 87 00:07:06,907 --> 00:07:11,709 you know the program might be implemented using a few registers. And then you're 88 00:07:11,709 --> 00:07:16,904 going to look at all the things that those registers point to, all the objects that 89 00:07:16,904 --> 00:07:21,569 they point to. And you will look at the pointers in those objects and everything 90 00:07:21,569 --> 00:07:25,989 they can point to, okay. And some of these things might overlap. I mean, some of 91 00:07:25,989 --> 00:07:30,981 these there might be multiple things which are reachable by more than one path 92 00:07:30,981 --> 00:07:35,009 starting at the registers. But the complete side of things that you can 93 00:07:35,009 --> 00:07:39,058 reach, beginning at the registers and following all the possible pointers, those 94 00:07:39,058 --> 00:07:44,007 are all the reachable objects. And then the complement of that set, an unreachable 95 00:07:44,007 --> 00:07:48,485 object is one that isn't reachable. So all the other objects, the ones that you were 96 00:07:48,485 --> 00:07:53,705 not able to reach by recursively starting at registers and following pointers as far 97 00:07:53,705 --> 00:07:58,709 as you could, those objects can never be used. Because clearly the implementation 98 00:07:58,709 --> 00:08:03,774 can only access things through registers and, and then only find additional things 99 00:08:03,774 --> 00:08:08,229 by, you know loading pointers out of objects that it could reach from the 100 00:08:08,229 --> 00:08:13,570 registers. So anything that it can reach by some sequence of sub-steps will never 101 00:08:13,570 --> 00:08:19,153 be used again, and is garbage. So let's take a look at another example that 102 00:08:19,153 --> 00:08:25,271 illustrates some interesting aspects of re achability and its use in automatic memory 103 00:08:25,271 --> 00:08:31,177 management. So what does this example do? The first thing it does, it allocates an A 104 00:08:31,177 --> 00:08:37,102 object, on the heap and assigns that to the variable x. So, x is a pointer to that 105 00:08:37,102 --> 00:08:43,136 object. And then it allocates a B object and y will point to that object. And then, 106 00:08:43,136 --> 00:08:51,090 it assigns the value of y to x, alright. So, we'll have this configuration and, and 107 00:08:51,090 --> 00:08:57,682 now let's draw a line here, okay and we'll come back and let's remember this point in 108 00:08:57,682 --> 00:09:01,696 time, what things look like at this point in time. And then we're going to go off 109 00:09:01,696 --> 00:09:05,439 and we're going to execute this conditional. And notice that this 110 00:09:05,439 --> 00:09:10,026 conditional is going to do. It's going to always be true, alright? So the predicate 111 00:09:10,026 --> 00:09:14,013 will always be true so it'll never take the false branch. All it's going to ever 112 00:09:14,013 --> 00:09:18,075 do is take the true branch and what's it going to do there, is immediately going to 113 00:09:18,075 --> 00:09:21,992 overwrite x. And so x is going to wind up pointing at some other new object. It 114 00:09:21,992 --> 00:09:26,001 doesn't matter what it is. And now, let's say that at this point right here, is 115 00:09:26,001 --> 00:09:30,471 where we try to do a garbage collection. So you know, for some reason this is the 116 00:09:30,471 --> 00:09:35,056 point where the program stops and tries to collect unused memory. And what can it 117 00:09:35,056 --> 00:09:39,528 collect? Well, just like before cuz the example up to this point is essentially 118 00:09:39,528 --> 00:09:44,449 the same. We can see that this object is unreachable, okay. So the first A object 119 00:09:44,449 --> 00:09:48,932 becomes unreachable at that point and it can be collected. Now what about the 120 00:09:48,932 --> 00:09:53,232 second object? Well it is reachable, it's clearly reachable. It's reachable through 121 00:09:53,232 --> 00:09:57,545 x, okay at that point and it's also reachable as it happens through y. And so 122 00:09:57,545 --> 00:10:02,598 it's not garbage and it's not going to be collected but notice that the x value is 123 00:10:02,598 --> 00:10:06,895 always going to be overwritten, okay? So the program, the compiler doesn't know 124 00:10:06,895 --> 00:10:10,979 that this branch is always going to be true. So, it doesn't realize that the 125 00:10:10,979 --> 00:10:15,471 value that x has at this point won't ever be used again but that value is 126 00:10:15,471 --> 00:10:19,835 immediately going to be overwritten, every time we take this conditional. And 127 00:10:19,835 --> 00:10:24,300 furthermore, if y is not used any place else in the program, if y i s dead at this 128 00:10:24,300 --> 00:10:30,026 point. Let's say that y is dead here. Then, neither one of these references to B 129 00:10:30,026 --> 00:10:35,205 is ever gonna be touched again. So in fact the B value will never be used again even 130 00:10:35,205 --> 00:10:40,197 though it is reachable. And so what this tells you is that reachability is an 131 00:10:40,197 --> 00:10:46,427 approximation. And by that I mean it's an approximation for the objects that will 132 00:10:46,427 --> 00:10:50,095 never be used again. What we're really interested in when we do garbage 133 00:10:50,095 --> 00:10:54,711 collection is collecting objects that will never be used in the future execution of 134 00:10:54,711 --> 00:10:59,351 the program. Because obviously that space is wasted and could be put to some other 135 00:10:59,351 --> 00:11:03,304 use that might be better and reachability approximates that. So if an object is 136 00:11:03,304 --> 00:11:07,426 unreachable it definitely won't be used again however, just because an object is 137 00:11:07,426 --> 00:11:11,861 reachable it's not a guarantee that it will be used again. So now let's talk 138 00:11:11,861 --> 00:11:17,116 about how we do garbage collection in Coolc. So Coolc has a fairly simple 139 00:11:17,116 --> 00:11:22,132 structure. It uses an accumulator in which of course points to an object and that 140 00:11:22,132 --> 00:11:26,160 object may point to other objects and so on. So we have to trace all the objects 141 00:11:26,160 --> 00:11:30,723 reachable from the accumulator but we also have to worry about the stack pointer so 142 00:11:30,723 --> 00:11:35,037 there's also stuff reachable from the stack. And each stack frame of course may 143 00:11:35,037 --> 00:11:38,715 contain pointers like, and you know for example the method parameters that are 144 00:11:38,715 --> 00:11:43,269 stored on the stack. Each stack frame may also contain some non-pointers, alright? 145 00:11:43,269 --> 00:11:47,323 So if I think about the layout of each activation record there would be some mix 146 00:11:47,323 --> 00:11:51,907 of pointers and non-pointers. Things like the return address so we have to know the 147 00:11:51,907 --> 00:11:56,362 layout of the frame. But if we do know the layout and of course the compiler is 148 00:11:56,362 --> 00:12:00,445 deciding on the layout so it naturally does know the layout, it can find all the 149 00:12:00,445 --> 00:12:04,528 pointers in the frame. Essentially, the compiler has to keep a record for each 150 00:12:04,528 --> 00:12:09,182 kind of activation record it builds for each methods. If activation record for a 151 00:12:09,182 --> 00:12:13,440 method foo and let's say that activation record has four slots then the compiler 152 00:12:13,440 --> 00:12:17,076 would need to keep track of which one of these were pointers to objects. And 153 00:12:17,076 --> 00:12:20,894 perhaps the second , and the fourth element of the frame are always pointers 154 00:12:20,894 --> 00:12:25,023 to objects and the other two are always non-pointers. So the somewhere, the 155 00:12:25,023 --> 00:12:29,520 compiler has to keep track of this information so that the garbage collector 156 00:12:29,520 --> 00:12:35,517 will know at Run time when it's looking at an activation record for foo where the 157 00:12:35,517 --> 00:12:41,374 pointers that it needs to follow are. So in Coolc, we start tracing from the 158 00:12:41,374 --> 00:12:46,103 accumulator and the stack and these are called the roots, okay. So, in garbage 159 00:12:46,103 --> 00:12:51,061 collection terminology the roots are the registers from which you begin tracing out 160 00:12:51,061 --> 00:12:55,337 all the reachable objects. And if we do that here, what we can do, so you see we 161 00:12:55,337 --> 00:12:58,368 have our object, here we have our accumulator, excuse me and our stack 162 00:12:58,368 --> 00:13:02,825 pointer and so we can just walk through. This little diagram of memory and find all 163 00:13:02,825 --> 00:13:07,057 the reachable objects so the acummulator points to object A so we'll mark that as 164 00:13:07,057 --> 00:13:11,081 reachable. And A points to C so we'll mark it as reachable. C points to E so we'll 165 00:13:11,081 --> 00:13:16,030 mark E as reachable. The stack pointer has a couple of frames on it. The first frame 166 00:13:16,030 --> 00:13:20,070 has no pointers. The second frame points to E. We've already touched that one. It's 167 00:13:20,070 --> 00:13:24,088 already marked so we can mark it again but it doesn't matter as long as it gets 168 00:13:24,088 --> 00:13:29,007 marked by somebody and now everything that is not marked is unreachable. So what 169 00:13:29,007 --> 00:13:33,036 objects didn't we touch and are traversal of the reachable objects? Well those are 170 00:13:33,036 --> 00:13:36,274 objects B and D. And so those are, unreachable objects and they can be 171 00:13:36,274 --> 00:13:41,662 reclaimed and we can reuse their storage. Now, one interesting thing to note here is 172 00:13:41,662 --> 00:13:47,336 that, just because an object has pointers to it, it does not mean it is reachable, 173 00:13:47,336 --> 00:13:51,934 so notice here object D. Object D actually has a pointer to it, okay and yet object D 174 00:13:51,934 --> 00:13:56,649 is unreachable and why is that? Well because the only pointers to it are from 175 00:13:56,649 --> 00:14:00,180 other unreachable objects. So it's important here to, you know just 176 00:14:00,180 --> 00:14:04,682 understand that it's not the case that every unreachable object has no pointers 177 00:14:04,682 --> 00:14:08,458 to it. There will be some unreachable objects or there may be some unreachable 178 00:14:08,458 --> 00:14:12,758 objects that actually do have pointers to it, to them but they will on ly come from 179 00:14:12,758 --> 00:14:17,075 other unreachable objects. So every garbage collection scheme has the 180 00:14:17,075 --> 00:14:22,123 following steps. We're going to allocate space as needed for new objects, so we 181 00:14:22,123 --> 00:14:26,422 just go ahead and allocate new space as long as we have space, so whenever we need 182 00:14:26,422 --> 00:14:31,160 it. And when space runs out we need to compute what objects might be used again. 183 00:14:31,160 --> 00:14:35,079 And generally that's done by tracing objects reachable from a set of root 184 00:14:35,079 --> 00:14:39,000 registers and then we're going to free the complement of that set. We're going to 185 00:14:39,000 --> 00:14:43,763 free the space used by the objects not found in part A. And I want to say that 186 00:14:43,763 --> 00:14:48,291 some strategies do perform garbage collection before the space actually runs 187 00:14:48,291 --> 00:14:52,050 out and we'll actually look at one of those in a future video.