In this video we're going to conclude our
discussion of automatic memory management
with the third and last technique we're
going to talk about for garbage collection
called Reference Counting. So the basic
idea behind reference counting is that
rather than waiting for memory to be
completely exhausted, we're going to try
to collect an object as soon as soon as
there are no more pointers to it. So as
soon as we discard the last pointer to an
object and it becomes unreachable, we will
try to collect it at that point in time.
And how can we do this? Well, as the name
suggests we're going to count the number
of references to each object. So in each
object we are going to store the number of
pointers to that object. So if I have an
object in memory, and it has say, three
pointers to it from other objects then
somewhere in this object is going to be a
dedicated field that contains the number
three. And if this number ever drops to
zero, if we discard these pointers and
this number becomes a zero, then we know
that nobody is pointing to this object,
and it can be free. And what this means is
that every assignment has to manipulate
the reference count in order to maintain
an accurate count of the number of
pointers pointing to an object. So
allocating a new object, returns an object
with a reference count of one. So when a
object is created by new it will already
have a reference count of one. The pointer
that is returned is the only reference to
the object. And so we're gonna write the
reference count of an object x is rc of x.
And now when we have an assignment x gets
assigned y we're going to have to update
the reference counts of both the object
that x points to and the object that y
points to before the assignment. So, what
happens here? So, if y points to p, so
let's draw our objects here, so y is a
local variable and it points to some
object p in memory, and x is also a local
variable and it points to some object, o.
Okay? So now x is getting the value of y
and so that's going to move this po inter
from where pointer before, pointing to the
same thing as y. So what's going to
happen, while p's reference count is going
to go up by one, and o's reference count
is going to go down by one. And since we
decremented o's reference counts, as we
dropped this pointer to the object o, we
need to do a check to see if the reference
count has become zero. And if the
reference count has dropped to zero, then
we can free the memory for o. And then in
addition to updating the reference counts
and checking whether the reference count
of o became zero, we actually need to do
the assignment itself, alright? So every
assignment, I want to stress that, every
single assignment in the program it's now
translated into these four operations that
need to be done to maintain the reference
counts. There are tradeoffs in reference
counting. It has advantages and
disadvantages. One of the big advantages
is that it collects garbage incrementally
without large pauses in the execution. So
for, for kind, for applications where
large pauses would be problematic, say
real time applications or interactive
applications, reference counting can
really help because it minimizes the
length of the longest possible pause.
Okay, so your program will never go to
sleep. And just appear to stop running for
some period of time because it's off
collecting garbage. It always collects the
garbage in small incremental amounts, and
so that you never see a long pause.
Reference counting, or at least a basic
implementation of reference counting is
also quite easy to implement. It's very
straight forward to go through and modify
the code to add reference counts. So you
can easily imagine a code generator that
would simply generate different code for,
for the assignment operation than it
normally did if you were adding reference
counting to an implementation. So really
the, the changes that are needed for a
simple implementation of reference
counting to a compiler are not that
pervasive. Now there are some
disadvantages , to reference counting.
One, is that manipulating the reference
counts at each assignment is really quite
slow. So, if you remember what happens, we
have a couple of updates to reference
counts, so we have to update, you know,
the reference count of two objects. To do
an assignment. This is, this is the code
to do an assignment and then we have an if
statement. And then we actually, do the
assignment itself. So there's two
reference count updates that's has to see
if our reference count became zero and
then we actually do the assignment. So the
overhead here is substantial. You're
taking every single assignment, in the
program and blowing up its cost by at
least four or five times. And that will
have a very noticeable impact on the
performance of many programs. Now it is
possible to optimize reference counting.
So for example, if we had two updates to
the same object, say within a basic block
or even within a control flow graph, a
compiler, a smart optimizing compiler,
could frequently combine those reference
count operations together. So instead of
updating the reference count to the object
two times, it can just update it one time.
And, similarly if there were even more
reference count updates, potentially all
of those could be coalesced within some
region of the program. The problem with
that, is that is becomes very tricky to
get that right. So a, a simple
implementation of reference counting is
quite slow. But easy to get right. A very
sophisticated implementation of reference
counting or highly optimized
implementation of reference counting, is
somewhat faster. Still has a noticeable
performance impact if you're reference
counting all objects but it is
substantially faster. However, it's quite
tricky to get it correct. The other
problem with reference counting is that it
cannot directly collect circular
structures. So to see this let's draw, a
little heap with a circular structure. And
so let's say we have a local variable x
and it points to some object in t he heap.
And that object has a pointer to another
object, alright? And that object, that
second object then has a pointer back to
the first object. Okay so here x is
pointing to say a circularly length list
of length two, alright? And if we add in
the reference counts here, what would
those look like? Well, this object down
here the second object here actually one
reference to it so its reference count
will be one. And this first object has two
pointers to it, one from x and one from
the other object and so its reference
count is two. Okay, so here is our little
heap and we can see that there is no
garbage here because all the objects are
reachable from a, a local variable or
variable of the program. Now if we were to
assign a new value to x, lets say that we
have the assignment x gets null. Alright,
so this pointer goes away. But what's
going to happen? Well when we do that
assignment, we're going to change the
reference count here of this object, it's
now gonna be one. And if we look at this
heap we now see that these objects, these
two objects are unreachable. Okay, so
these are unreachable. But notice that the
reference counts are not zero, so we can't
collect them. The garbage collector or the
reference counting implementation, will
check the reference counts and see oh,
these are one and so we can't delete them.
And then, what it can't see is that the
only references to these objects are from
other, unreachable objects. So, the bottom
line is that reference counting can't
collect circular structures and there is
only really two ways to deal with that.
One is if the programmer remembers
whenever a circular structure is going to
become unreadable, to somehow break the
circularity. So for example, before we
clobbered the pointer to x here, we
remembered to go in and say set, you know,
this pointer here to null. If we nulled
out one of the pointers in this cycle, so
that there was no longer a cycle, then the
reference counting would work correctly
because then the reference count of this
object would go to zero when, when this
pointer was dropped from x and that would
cause the reference count of this object
also to go to zero after this object was
deleted, okay? The other possibility is to
back reference counting by some other
garbage collection technique that can
collect cycles. And so, in some reference
counting systems for example most of the
garbage collection is done by reference
counting but every now and again, once in
a very, very while, you might want to mark
and sweep collector to go through and
clean out any circular but unreachable
data structures. We're now ready to wrap
up our discussion of automatic memory
management. And so I just want to make a
few, high level points here. First of all,
there's no question that automatic memory
management is a great thing. It prevents
very serious storage bugs, some of the
most difficult bugs in programming, and
when you're writing in the garbage
collected language you really have just a
whole class of things you don't have to
worry about and so it is certainly a more
productive way to program. So if, if your
problem, your program is really a good fit
for automatic memory management then you'd
be crazy not to use a system that provided
that kind of support. Now, the
disadvantage of automatic memory
management is that it reduces programmer
control. So you don't have control anymore
over the layout of data and memory, and
you don't have control over when the
memory is reallocated. So, you neither
have control over where the data is in
memory and you have only a very limited
amount of control over how much memory
your program is using, okay? And so if
these two things don't matter, if your, if
your application is not extremely data
intensive where the precisely out of data
memory and how much data is residing in
memory is important then garbage
collection will likely work very well. But
there are applications particularly high
end data processing and scientific
applications which use a lot of data and
need to make very, very efficient use of
the memory where garbage collection
actually becomes too inefficient to do a
good job and people in those domains still
use manual memory management. But there
are some other issues. So, in real time
applications the pauses can be
problematic. So, if you have a program
that needs to meet guaranteed deadlines,
many embedded systems that are interacting
with the outside world say controlling
dangerous machinery and things like that
they have to have response times that are
guaranteed to make sure that nothing
terrible happens. And, and you know,
introducing a automatic memory management
system that might pause for arbitrary
amounts of time you know, makes that a
very problematic things guaranty. So, you
don't always see garbage selection used in
real time applications. Although there has
been a lot a progress in the last several
years on real time garbage collectors.
Another issue for every programmer who
uses automatic memory management probably
will have to face is the problem of memory
leaks. So, while automatic memory
management prevents you from corrupting
your memory, it really doesn't prevent you
from hanging on to too much data and
possibly affecting the performance of your
program dramatically. So, memory leaks are
possible in garbage collected languages
and I would say they are even likely.
Said, you know, the fact that you're not
as aware or not as forced to be aware of
how the memory is being used makes it
easier to have memory leaks. And the kind
of memory leak that you will have in say,
a Java program is that you'll have some
you know, some variable say x that points
to some data structure and this data
structure is gigantic, okay? So lets say
that this is the abstract syntax tree, in
a compiler, alright? Now there may come a
point in the computation where you don't
need the abstract syntax tree anymore. So
let's say that we have converted to an
intermediate language and from the
abstract syntax tree and now all our
processing for the rest of the compilation
is going t be on the intermediate language
representation and generating code from
that, we never go back and look at the
abstract syntax tree again. Well, the
compiler I mean, excuse me, the, the
garbage collector doesn't know that you
are not going to use the abstract syntax
tree again in the future. And if you have
a variable that's pointing to this
gigantic data structure even if you are
not using it, it's gong to hang around and
is going to be using up memory. And so the
right thing to do is when you reach a
point in program where you are not going
to use this data structure anymore is to
assign x the null value. You want to
assign x to null at that point and
essentially dropping this pointer to the
data structure. And now the garbage
collector, whatever form it is, mark and
sweeps, Stop and copy or reference
counting will be able to see that this is
no longer reachable and will collect that
big structure. And this is very, very
common in, in production Java programs to
have these kinds of memory leaks where you
just have pointers that you forgot about
to data that you're no longer going to
use. So as a whole, I have conveyed in the
last few lectures, garbage collection is a
very important technique. Every programmer
should be aware of its benefits and costs
and it's also very interesting aspect of
programming language implementation. There
are much more advanced garbage collecting
algorithms than we have discussed in these
lectures and the primary dimensions along
which people have thought about improving
garbage collection, that is making garbage
collection concurrent. That means allowing
the program to continue to run while other
collection is happening. So the collector
is working in the background actively
while the program is running. Another
thing that's very common actually in, in
production collectors is to what's called
a generational collector. And the basic
idea here is that we don't want to keep
going over lo oking at objects that are
very long lived on every collection. So,
collections happen very frequently and
there will be some objects that just live
for very long time, the big data
structures that hang around for most of
the program. And once we have seen them,
in a couple of collections we probably can
assume that they're going to be around for
a few more collections. And so in a
generational collection sorry in a
generational collector older objects,
objects that have been around for a while
are put in a seperate area and they're
collected less frequently. And this just
allows the collector to focus on the
objects that are most likely to be garbage
which are the recently allocated objects.
We already talked a little bit about
Realtime. So there are collectors that try
to bound the length or the, bound the
length of the maximum pause, the maximum
interruption to the program. And finally
parallel collectors. So collector systems
where the garbage, there's actually
several garbage collectors running at the
same time and somehow coordinating their
actions.