In this video we're going to start our
discussion of garbage collection or
automatic memory management. This will
take us a few videos to get through and
this first video is just an overview of
the problem. And then we'll talk about
specific techniques in subsequent videos.
To set the stage, let's first talk about
the problem that we're trying to solve.
So, if one has to manage memory manually,
meaning you have to do all the allocation
and deallocation explicitly yourself, that
is a hard way to programming leads to
certain kinds of bugs that are very
difficult to eliminate from programs. So,
in particular, these days you see this
primarily in C and C++ programs. Those are
the main languages that are used that have
manual memory management. And, the kinds
of storage bugs that you can get because
it has manual memory management are things
like forgetting to free unused memory so
that's a, it means a memory leak.
Dereferencing dangling pointers,
overriding parts of a data structure,
unintentionally. And actually there's a
few more things, although these are
probably the three most common problems
that people have and these bugs are really
hard to find. And I want to emphasize that
these kinds of bugs are often some of the
very, very last bugs to be found in, in
complex systems. They often persist into
production and sometimes for a very long
time after the code is in production use.
And why is that? The reason is that these,
these kinds of bugs, storage bugs,
typically have effects that are far away
in time and space from the source and so
how can that happen? Well let's think
about some object in memory and now let's
say only on interesting you might have
some fields, let's say you have a few
fields and I am keeping some pointers to
it. So somewhere on program is a reference
to this particular object and now I come
along and free it. So I am doing my own
memory management like free this object
but I forget that I had this pointer. And
so now what's happen all the storage has
been freed it's no longer really valid
memory but the pointer still exist to it.
And then when I come along and allocate
something else it might allocate the same
piece of memory. So this might now be a
different kind of object, okay. So I might
have a different type here even. In this
memory might be used for something
completely different and now I have a
pointer that says it thinks it's a red
object, it's pointing to a blue object.
And when I come in and write stuff into
this object, of course I'm just writing
nonsense. So I, this, whatever piece of
code holds this pointer thinks it's still
the old kind of object. It will write some
bits in here and when I go in some other
part of the program possibly quite far
away go out and read out, this is a blue
object, I'll just get some random garbage
and that will probably cause my program to
cash. So this is a very, very old problem.
It's been studied since at least the
1950s. It was first thought about
carefully in list. And there are some
well-known techniques for completely
automatic memory management so you don't
have to manage memory yourself. And this
only became mainstream actually in the
1990s so with the popularity of Java.
Prior to that time there was really no
mainstream language that used automatic
memory managements so that's really just
in the last now almost twenty years that
garbage collection and automatic memory
management in general became a popular
mainstream programming technique. So the
basic strategy in automatic memory
management is, is pretty simple. So, when
an object is created, when we allocate a
new object the system, the run time system
will find some unused space for that
object and it will just allocate it. So
whenever you say new of some class name in
Cool. Some memory is automatically
allocated by the system, some previously
unused memory is automatically allocated
by the system for that object. And if you
keep doing this over and over and over
again and after awhile you're going to run
out of space. So eventually there is no
more unused space left for additional obj
ects. And at that point you have to do
something. You have to reclaim some of the
space in order to allocate more objects
and the observation that garbage
collection systems rely upon is that some
of the spaces being used is probably
occupied by objects that will never be
used again. So they, some of these objects
are not going to be referred to again by
the program and if we can figure out which
objects those are, which objects are not
longer going to be used. Then we could
deallocate them and reuse the space for
new objects. So the big question is, how
can we know that an object will never be
used again? And, most of the garbage
collection techniques that are out there
today rely on the following observation,
then that's that a program can only use
the objects that it can find and what do
we mean by that? So I'm going to switch
colors so let's take a look at this piece
of code so what's going to happen? Well
when we execute this the first thing that
happens is we allocate an A object,
alright. And it's assigned x, so x will
have a pointer to that object. And then,
in the body of this let, what's going to
happen well, we're going to assign x, the
value that y points to so y is another
variable. It points to some other objects
in memory, okay. And what's going to
happen, when we execute this assignment is
that we're going to remove the old value
of x and x now is going to point to this
object. Now observe that this object a is
unreachable. Meaning it has no references
to it. There are no longer any pointers to
it. And how do I know that? Well, a brand
new here when it was created. I only
created one pointer to it, x and then I
immediately assigned x to something else.
So I dropped the only pointer to A. There
is no reference to A anywhere in the
program. And so the program will never be
able to find it again. The program, if no
variable or data structure in the program
has a pointer to A, then A can never be
referred to by the program in the future.
So any kind of subsequent execution of the
program has no p ointers to A and
therefore it will never use A again and so
the space ray can be reclaimed and used
for another object. Now it turns out that
we need a more general definition of
object reachability than this example
illustrates so let's take a look at that.
We're going to say that an object x is
reachable if and only if one of the
following two things is true. So either A
register contains a pointer to x. So
either the x is reachable immediately from
some register. Remember that the registers
contain things like the local variables in
there and the intermediate expressions and
they're just you know, the values that the
program has immediate access to or another
reachable object y contains a pointer to
x. And so what does this say? Well, this
says you're going start at the register so
you know the program might be implemented
using a few registers. And then you're
going to look at all the things that those
registers point to, all the objects that
they point to. And you will look at the
pointers in those objects and everything
they can point to, okay. And some of these
things might overlap. I mean, some of
these there might be multiple things which
are reachable by more than one path
starting at the registers. But the
complete side of things that you can
reach, beginning at the registers and
following all the possible pointers, those
are all the reachable objects. And then
the complement of that set, an unreachable
object is one that isn't reachable. So all
the other objects, the ones that you were
not able to reach by recursively starting
at registers and following pointers as far
as you could, those objects can never be
used. Because clearly the implementation
can only access things through registers
and, and then only find additional things
by, you know loading pointers out of
objects that it could reach from the
registers. So anything that it can reach
by some sequence of sub-steps will never
be used again, and is garbage. So let's
take a look at another example that
illustrates some interesting aspects of re
achability and its use in automatic memory
management. So what does this example do?
The first thing it does, it allocates an A
object, on the heap and assigns that to
the variable x. So, x is a pointer to that
object. And then it allocates a B object
and y will point to that object. And then,
it assigns the value of y to x, alright.
So, we'll have this configuration and, and
now let's draw a line here, okay and we'll
come back and let's remember this point in
time, what things look like at this point
in time. And then we're going to go off
and we're going to execute this
conditional. And notice that this
conditional is going to do. It's going to
always be true, alright? So the predicate
will always be true so it'll never take
the false branch. All it's going to ever
do is take the true branch and what's it
going to do there, is immediately going to
overwrite x. And so x is going to wind up
pointing at some other new object. It
doesn't matter what it is. And now, let's
say that at this point right here, is
where we try to do a garbage collection.
So you know, for some reason this is the
point where the program stops and tries to
collect unused memory. And what can it
collect? Well, just like before cuz the
example up to this point is essentially
the same. We can see that this object is
unreachable, okay. So the first A object
becomes unreachable at that point and it
can be collected. Now what about the
second object? Well it is reachable, it's
clearly reachable. It's reachable through
x, okay at that point and it's also
reachable as it happens through y. And so
it's not garbage and it's not going to be
collected but notice that the x value is
always going to be overwritten, okay? So
the program, the compiler doesn't know
that this branch is always going to be
true. So, it doesn't realize that the
value that x has at this point won't ever
be used again but that value is
immediately going to be overwritten, every
time we take this conditional. And
furthermore, if y is not used any place
else in the program, if y i s dead at this
point. Let's say that y is dead here.
Then, neither one of these references to B
is ever gonna be touched again. So in fact
the B value will never be used again even
though it is reachable. And so what this
tells you is that reachability is an
approximation. And by that I mean it's an
approximation for the objects that will
never be used again. What we're really
interested in when we do garbage
collection is collecting objects that will
never be used in the future execution of
the program. Because obviously that space
is wasted and could be put to some other
use that might be better and reachability
approximates that. So if an object is
unreachable it definitely won't be used
again however, just because an object is
reachable it's not a guarantee that it
will be used again. So now let's talk
about how we do garbage collection in
Coolc. So Coolc has a fairly simple
structure. It uses an accumulator in which
of course points to an object and that
object may point to other objects and so
on. So we have to trace all the objects
reachable from the accumulator but we also
have to worry about the stack pointer so
there's also stuff reachable from the
stack. And each stack frame of course may
contain pointers like, and you know for
example the method parameters that are
stored on the stack. Each stack frame may
also contain some non-pointers, alright?
So if I think about the layout of each
activation record there would be some mix
of pointers and non-pointers. Things like
the return address so we have to know the
layout of the frame. But if we do know the
layout and of course the compiler is
deciding on the layout so it naturally
does know the layout, it can find all the
pointers in the frame. Essentially, the
compiler has to keep a record for each
kind of activation record it builds for
each methods. If activation record for a
method foo and let's say that activation
record has four slots then the compiler
would need to keep track of which one of
these were pointers to objects. And
perhaps the second , and the fourth
element of the frame are always pointers
to objects and the other two are always
non-pointers. So the somewhere, the
compiler has to keep track of this
information so that the garbage collector
will know at Run time when it's looking at
an activation record for foo where the
pointers that it needs to follow are. So
in Coolc, we start tracing from the
accumulator and the stack and these are
called the roots, okay. So, in garbage
collection terminology the roots are the
registers from which you begin tracing out
all the reachable objects. And if we do
that here, what we can do, so you see we
have our object, here we have our
accumulator, excuse me and our stack
pointer and so we can just walk through.
This little diagram of memory and find all
the reachable objects so the acummulator
points to object A so we'll mark that as
reachable. And A points to C so we'll mark
it as reachable. C points to E so we'll
mark E as reachable. The stack pointer has
a couple of frames on it. The first frame
has no pointers. The second frame points
to E. We've already touched that one. It's
already marked so we can mark it again but
it doesn't matter as long as it gets
marked by somebody and now everything that
is not marked is unreachable. So what
objects didn't we touch and are traversal
of the reachable objects? Well those are
objects B and D. And so those are,
unreachable objects and they can be
reclaimed and we can reuse their storage.
Now, one interesting thing to note here is
that, just because an object has pointers
to it, it does not mean it is reachable,
so notice here object D. Object D actually
has a pointer to it, okay and yet object D
is unreachable and why is that? Well
because the only pointers to it are from
other unreachable objects. So it's
important here to, you know just
understand that it's not the case that
every unreachable object has no pointers
to it. There will be some unreachable
objects or there may be some unreachable
objects that actually do have pointers to
it, to them but they will on ly come from
other unreachable objects. So every
garbage collection scheme has the
following steps. We're going to allocate
space as needed for new objects, so we
just go ahead and allocate new space as
long as we have space, so whenever we need
it. And when space runs out we need to
compute what objects might be used again.
And generally that's done by tracing
objects reachable from a set of root
registers and then we're going to free the
complement of that set. We're going to
free the space used by the objects not
found in part A. And I want to say that
some strategies do perform garbage
collection before the space actually runs
out and we'll actually look at one of
those in a future video.