In this video, we are going to look at the
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, it's 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 there are
some techniques more advance techniques,
for stop-and-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, a fairly
significant fraction of the space has to
be reserved for the garbage collector. Now
the way allocation works is that there's a
heat pointer 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 when it comes time to allocate a
new object, we simply allocate it at the
heap pointers. So, the heap pointer will
simply bump up and some block of space
will be allocated to a, the next object
that we want to do. And it will just keep
marching through the old space allocating
as you allocate more objects. Okay, so
allocation just advances the heap pointer
so one of the advantages, actually, of
stop-and-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 garbage collection will start
GC, will start when the old space is full.
And what it's going to do is 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 the reachable
objects, the garbage is left behind. So,
you simply pickup all the data that you're
using and move it over to the new space
and all the junk that you didn't need
anymore is left behind in the old space.
And then, after you copy stuff to the new
space first of all 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 and 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 a 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 which is this
object A. And so what we're going to do,
well we're going to make a copy of all the
objects reachable from A. We're gonna move
them over to the new space. And what
that's going to look like, well, here it
is, afterward. But let's trace it out. So,
we started A, we follow pointers from A,
we can see there's a pointer to C, okay,
so C is going to be reachable and 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 points back to the
copy of A. So, what we know, when the
object and move their pointers and we
adjust them so that we've really copied
the whole graph of objects over to the
news space. Now, we're using less space so
there's some free space here, okay. And
now, this will become the old space. This
now our old space and this is now the new
space which we will use for the next
garbage collection. To summarize the
discussi on so far, one of the essential
problems in stop-and-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 distinguishes
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, alright. Cuz when you
find an object, of course, you can't see
all the pointers that point into that
object. So, how are we going to do that?
Well, here is an idea. Well, we copy 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 would,
how that looks like. So we have our old
space, we have our new space. And let's
say, we 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 gonna take A and we're going
to reuse its space and we're gonna store
what's called a forwarding pointer in it.
So, we're going to, yeah, 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 with here with a purple bar
something. This is we're marking someway
so that we can tell this object has
already been copied. And then at a. 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 you can go to their
house and if they have moved, you can ask
for the forwarding address. And that's
exactly and then you can go off to their
new house wherever they've wherever
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 in this
object, realize that this object has moved
because we've marked it and the object was
moved. And then we can use the forwarding
pointer to find out where the new object
is and then update this pointer wherever
it is 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 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 to use
with the garbage collectors. The garbage
collector really needs to work in
constants base. And now here is the idea
that will, that is used in stop-and-copy
algorithms to solve the problem. So, we're
going partition in new space and this is
just the new space here into three
contiguous regions. We're going to have
we'll start with the one on the far right.
We're going to have the empty region where
we're allocating new objects. And there's
an allocation pointer 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, 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 that the object 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 yet 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 obje cts. And
so, you can think of this area here,
between the scanned pointer and the
allegation pointer, this is the work
quest. 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 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 only have one root object and it's
A, okay, I just want to point out that A
has one pointer which points to object C,
alright. So, at 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 byte for byte
copy. So, we just take the bytes of A and
we do a copy without, you know, doing any
inspection of the interior of the object,
over to the new space. And how's that
work? Of course, our allocation pointer
isn't in, initially right here at the
beginning of the new space. And then we
add and we copy this one object over. And
then that means allocating an object and
so now, the allocation pointer points to
the first word of memory, beyond the
object that we just allocated, okay. Now
what happens when we copy it over? Well,
because it is just a byte for byte copy,
all the pointers in A still point to the
objects as they pointed to before which
are the objects in old space. And 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 as having
been copied, that's why it's grayed out.
Indicates that this object has already
been moved. And that this dotted line here
indicates that somewhere, we stored a
pointer to the new copy of A. And now,
we're ready to begin the algorithms. And
not ice that we have some objects here
that have been copied but not scanned so
this is our work list. So, now it's going
to repeatedly work off of those objects
and how do we know they're objects in
there? Well, we just compare the scan and
the allocation pointers. So, if they're if
they are different, if there's an object
in between the scan and the allocation
pointer, at least one object between the
two, then there's work to do. There's an
object that needs to be scanned 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 it points to that haven't already
been moved. And so, before we said, you
know, the A, this, this copy of A pointed
to the old copy of C. So, now what we
discover 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 and then the scan pointer moves
over A. We've scanned all the pointers in
A, alright. And the allocation pointer
also moves because we had to allocate
space for C. And of course, C is just a
byte for byte 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 yet, moved yet just point back into
the old space. So, in this case the object
C points to the object F 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, alright.
And finally we mark C as having been
copied, having been moved to the new space
and we left a forwarding pointer to it in
case so we can fix any pointers that point
to C that we come across in the future.
And now we have to continue scanning
objects that have been copied but not
scanned. And we can see that there is an
object between the scan and the allocatio
n pointer namely C and so we'll now
process all the pointers in C. Next, we
scan C. And, we discover that it points to
F. Which hasn't been moved yet and so we
copy F over 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 byte for byte copy and so all
it's 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, alright.
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. All the pointers
in F 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 heap. This
is a complete graph, a complete copy of
its A, of the graph of reachable objects
from the old space. So, now we're done and
we simply swap the role of the new and old
space and we resume the program so that
when the program starts running again, it
will allocate out of this area and it'll
be on the allocation pointer until it
fills up what is now the old space, you
know, 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 stop-and-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'll call that objec t , and then for
every pointer in O, we're going to do the
following. We're going to find the object
O' that, that pointer points to. And then
there are two cases. One is that there is
no forwarding pointer, alright. And if
there's no forwarding pointer, then we
have to copy that object to new space and
that will involve allocating a new object
and updating the allocation pointer. Then
we're going to set and here it says the
first word, they really shouldn't
emphasize the 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 and will always be the
same word. But anyways, we set a word of
the old object to point to the new copy.
We mark the old object as copied. Mark old
object as copied, okay. So, that's so that
we can tell if we ever come to a pointer
to it again, we know it's already been
moved and then we change p, the pointer,
to point to the new copy of O', alright.
So, if there was, that's what we do if
there is no forwarding pointer. And if
there is a forwarding pointer, then we
simply update the pointer to point to the
same place as the forwarding pointer. And
we just repeat this loop over and over
again until we've scanned all the copied
options. So, just as well as 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 and 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'll 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, in a bit pattern for an integer could
look an awful lot like a pointer. Now,
this is not a big problem because the
compiler, of course, in terms of, a lot of
the objects in the heap and it can stor e
that information somewhere communicated to
the garbage collector so that it will be
able to find the pointers. So, you can
imagine easily a little bit of information
stored with the program indicating for
each type where the pointers are. And
similarly once we've scanned this object,
we need to be able to advance our scan
pointer just past the object so that we
can find the beginning of the next object
and that's why we need to know the size,
okay. So, we need to know that size so
that the scan pointer can be moved past
the object and we can find the beginning
of the next object. 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 kind of an expensive operation
with stop-and-copy because, you know, you
still have to walk the entire stack 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
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. Allocation is
very cheap, alright. So, cuz all you have
to do is increment the e-pointer. So,
you're just moving a, a, single pointer
forward to allocate space. There's no
complicated free list future verse 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, because of making a copy
of the reachable objects stop-and-copy
only touches the reac hable object, It is
not, in particular, does not touch the
garbage. So, if you think about that for a
minute, that means that the garbage
collection is in stop-and-copy is order
the size of the live objects. So, whatever
the sub-graph is that you're copying,
that's the cost of a garbage collection
and that's in contrast to mark-and-sweep
were the cost is proportional to all the
memory that you're using cuz 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-sweep. Now, of course
the down side of stop-and-copy is that it
moves the objects in some languages, in
particular C and C++, can't allow you to
move objects because the address that
which an object lives is actually visible
exposed in the program and is 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.