1
00:00:03,052 --> 00:00:07,070
In this video we're going to conclude our
discussion of automatic memory management

2
00:00:07,070 --> 00:00:12,083
with the third and last technique we're
going to talk about for garbage collection

3
00:00:12,083 --> 00:00:19,007
called Reference Counting. So the basic
idea behind reference counting is that

4
00:00:19,007 --> 00:00:22,884
rather than waiting for memory to be
completely exhausted, we're going to try

5
00:00:22,884 --> 00:00:26,541
to collect an object as soon as soon as
there are no more pointers to it. So as

6
00:00:26,541 --> 00:00:30,726
soon as we discard the last pointer to an
object and it becomes unreachable, we will

7
00:00:30,726 --> 00:00:35,471
try to collect it at that point in time.
And how can we do this? Well, as the name

8
00:00:35,471 --> 00:00:40,000
suggests we're going to count the number
of references to each object. So in each

9
00:00:40,000 --> 00:00:44,045
object we are going to store the number of
pointers to that object. So if I have an

10
00:00:44,045 --> 00:00:49,078
object in memory, and it has say, three
pointers to it from other objects then

11
00:00:49,078 --> 00:00:54,932
somewhere in this object is going to be a
dedicated field that contains the number

12
00:00:54,932 --> 00:01:00,215
three. And if this number ever drops to
zero, if we discard these pointers and

13
00:01:00,215 --> 00:01:06,044
this number becomes a zero, then we know
that nobody is pointing to this object,

14
00:01:06,044 --> 00:01:11,804
and it can be free. And what this means is
that every assignment has to manipulate

15
00:01:11,804 --> 00:01:16,537
the reference count in order to maintain
an accurate count of the number of

16
00:01:16,537 --> 00:01:21,805
pointers pointing to an object. So
allocating a new object, returns an object

17
00:01:21,805 --> 00:01:26,651
with a reference count of one. So when a
object is created by new it will already

18
00:01:26,651 --> 00:01:32,000
have a reference count of one. The pointer
that is returned is the only reference to

19
00:01:32,000 --> 00:01:36,079
the object. And so we're gonna write the
reference count of an object x is rc of x.

20
00:01:36,079 --> 00:01:42,489
And now when we have an assignment x gets
assigned y we're going to have to update

21
00:01:42,489 --> 00:01:47,589
the reference counts of both the object
that x points to and the object that y

22
00:01:47,589 --> 00:01:53,169
points to before the assignment. So, what
happens here? So, if y points to p, so

23
00:01:53,169 --> 00:01:58,110
let's draw our objects here, so y is a
local variable and it points to some

24
00:01:58,110 --> 00:02:03,726
object p in memory, and x is also a local
variable and it points to some object, o.

25
00:02:03,726 --> 00:02:10,128
Okay? So now x is getting the value of y
and so that's going to move this po inter

26
00:02:10,375 --> 00:02:16,039
from where pointer before, pointing to the
same thing as y. So what's going to

27
00:02:16,039 --> 00:02:20,557
happen, while p's reference count is going
to go up by one, and o's reference count

28
00:02:20,557 --> 00:02:25,230
is going to go down by one. And since we
decremented o's reference counts, as we

29
00:02:25,230 --> 00:02:29,575
dropped this pointer to the object o, we
need to do a check to see if the reference

30
00:02:29,575 --> 00:02:33,613
count has become zero. And if the
reference count has dropped to zero, then

31
00:02:33,613 --> 00:02:38,630
we can free the memory for o. And then in
addition to updating the reference counts

32
00:02:38,630 --> 00:02:42,972
and checking whether the reference count
of o became zero, we actually need to do

33
00:02:42,972 --> 00:02:47,502
the assignment itself, alright? So every
assignment, I want to stress that, every

34
00:02:47,502 --> 00:02:53,093
single assignment in the program it's now
translated into these four operations that

35
00:02:53,093 --> 00:02:59,392
need to be done to maintain the reference
counts. There are tradeoffs in reference

36
00:02:59,392 --> 00:03:03,986
counting. It has advantages and
disadvantages. One of the big advantages

37
00:03:03,986 --> 00:03:09,016
is that it collects garbage incrementally
without large pauses in the execution. So

38
00:03:09,016 --> 00:03:13,206
for, for kind, for applications where
large pauses would be problematic, say

39
00:03:13,206 --> 00:03:17,512
real time applications or interactive
applications, reference counting can

40
00:03:17,512 --> 00:03:21,987
really help because it minimizes the
length of the longest possible pause.

41
00:03:21,987 --> 00:03:26,167
Okay, so your program will never go to
sleep. And just appear to stop running for

42
00:03:26,167 --> 00:03:30,100
some period of time because it's off
collecting garbage. It always collects the

43
00:03:30,100 --> 00:03:34,332
garbage in small incremental amounts, and
so that you never see a long pause.

44
00:03:34,523 --> 00:03:39,049
Reference counting, or at least a basic
implementation of reference counting is

45
00:03:39,049 --> 00:03:43,469
also quite easy to implement. It's very
straight forward to go through and modify

46
00:03:43,631 --> 00:03:47,912
the code to add reference counts. So you
can easily imagine a code generator that

47
00:03:47,912 --> 00:03:52,804
would simply generate different code for,
for the assignment operation than it

48
00:03:52,804 --> 00:03:57,212
normally did if you were adding reference
counting to an implementation. So really

49
00:03:57,212 --> 00:04:01,323
the, the changes that are needed for a
simple implementation of reference

50
00:04:01,323 --> 00:04:04,999
counting to a compiler are not that
pervasive. Now there are some

51
00:04:04,999 --> 00:04:10,008
disadvantages , to reference counting.
One, is that manipulating the reference

52
00:04:10,008 --> 00:04:14,713
counts at each assignment is really quite
slow. So, if you remember what happens, we

53
00:04:14,713 --> 00:04:20,007
have a couple of updates to reference
counts, so we have to update, you know,

54
00:04:20,007 --> 00:04:24,850
the reference count of two objects. To do
an assignment. This is, this is the code

55
00:04:24,850 --> 00:04:29,024
to do an assignment and then we have an if
statement. And then we actually, do the

56
00:04:29,024 --> 00:04:33,015
assignment itself. So there's two
reference count updates that's has to see

57
00:04:33,015 --> 00:04:37,042
if our reference count became zero and
then we actually do the assignment. So the

58
00:04:37,042 --> 00:04:41,028
overhead here is substantial. You're
taking every single assignment, in the

59
00:04:41,028 --> 00:04:45,050
program and blowing up its cost by at
least four or five times. And that will

60
00:04:45,050 --> 00:04:50,059
have a very noticeable impact on the
performance of many programs. Now it is

61
00:04:50,059 --> 00:04:55,261
possible to optimize reference counting.
So for example, if we had two updates to

62
00:04:55,261 --> 00:05:00,173
the same object, say within a basic block
or even within a control flow graph, a

63
00:05:00,173 --> 00:05:05,023
compiler, a smart optimizing compiler,
could frequently combine those reference

64
00:05:05,023 --> 00:05:10,014
count operations together. So instead of
updating the reference count to the object

65
00:05:10,014 --> 00:05:15,000
two times, it can just update it one time.
And, similarly if there were even more

66
00:05:15,000 --> 00:05:20,021
reference count updates, potentially all
of those could be coalesced within some

67
00:05:20,021 --> 00:05:26,213
region of the program. The problem with
that, is that is becomes very tricky to

68
00:05:26,213 --> 00:05:31,026
get that right. So a, a simple
implementation of reference counting is

69
00:05:31,219 --> 00:05:37,010
quite slow. But easy to get right. A very
sophisticated implementation of reference

70
00:05:37,010 --> 00:05:42,026
counting or highly optimized
implementation of reference counting, is

71
00:05:42,026 --> 00:05:47,629
somewhat faster. Still has a noticeable
performance impact if you're reference

72
00:05:47,629 --> 00:05:52,017
counting all objects but it is
substantially faster. However, it's quite

73
00:05:52,017 --> 00:05:57,681
tricky to get it correct. The other
problem with reference counting is that it

74
00:05:57,681 --> 00:06:03,091
cannot directly collect circular
structures. So to see this let's draw, a

75
00:06:03,091 --> 00:06:09,063
little heap with a circular structure. And
so let's say we have a local variable x

76
00:06:09,063 --> 00:06:16,059
and it points to some object in t he heap.
And that object has a pointer to another

77
00:06:16,059 --> 00:06:22,012
object, alright? And that object, that
second object then has a pointer back to

78
00:06:22,012 --> 00:06:26,041
the first object. Okay so here x is
pointing to say a circularly length list

79
00:06:26,194 --> 00:06:30,072
of length two, alright? And if we add in
the reference counts here, what would

80
00:06:30,072 --> 00:06:34,334
those look like? Well, this object down
here the second object here actually one

81
00:06:34,334 --> 00:06:39,281
reference to it so its reference count
will be one. And this first object has two

82
00:06:39,281 --> 00:06:43,783
pointers to it, one from x and one from
the other object and so its reference

83
00:06:43,783 --> 00:06:49,362
count is two. Okay, so here is our little
heap and we can see that there is no

84
00:06:49,362 --> 00:06:53,739
garbage here because all the objects are
reachable from a, a local variable or

85
00:06:53,739 --> 00:07:00,138
variable of the program. Now if we were to
assign a new value to x, lets say that we

86
00:07:00,138 --> 00:07:06,351
have the assignment x gets null. Alright,
so this pointer goes away. But what's

87
00:07:06,351 --> 00:07:11,895
going to happen? Well when we do that
assignment, we're going to change the

88
00:07:11,895 --> 00:07:17,491
reference count here of this object, it's
now gonna be one. And if we look at this

89
00:07:17,691 --> 00:07:23,327
heap we now see that these objects, these
two objects are unreachable. Okay, so

90
00:07:23,327 --> 00:07:28,608
these are unreachable. But notice that the
reference counts are not zero, so we can't

91
00:07:28,608 --> 00:07:34,042
collect them. The garbage collector or the
reference counting implementation, will

92
00:07:34,042 --> 00:07:39,027
check the reference counts and see oh,
these are one and so we can't delete them.

93
00:07:39,027 --> 00:07:44,019
And then, what it can't see is that the
only references to these objects are from

94
00:07:44,019 --> 00:07:49,011
other, unreachable objects. So, the bottom
line is that reference counting can't

95
00:07:49,011 --> 00:07:54,014
collect circular structures and there is
only really two ways to deal with that.

96
00:07:54,014 --> 00:07:59,072
One is if the programmer remembers
whenever a circular structure is going to

97
00:07:59,072 --> 00:08:05,016
become unreadable, to somehow break the
circularity. So for example, before we

98
00:08:05,016 --> 00:08:10,059
clobbered the pointer to x here, we
remembered to go in and say set, you know,

99
00:08:10,059 --> 00:08:15,175
this pointer here to null. If we nulled
out one of the pointers in this cycle, so

100
00:08:15,175 --> 00:08:19,489
that there was no longer a cycle, then the
reference counting would work correctly

101
00:08:19,489 --> 00:08:23,317
because then the reference count of this
object would go to zero when, when this

102
00:08:23,317 --> 00:08:27,831
pointer was dropped from x and that would
cause the reference count of this object

103
00:08:27,831 --> 00:08:33,170
also to go to zero after this object was
deleted, okay? The other possibility is to

104
00:08:33,170 --> 00:08:37,971
back reference counting by some other
garbage collection technique that can

105
00:08:37,971 --> 00:08:42,494
collect cycles. And so, in some reference
counting systems for example most of the

106
00:08:42,494 --> 00:08:47,595
garbage collection is done by reference
counting but every now and again, once in

107
00:08:47,595 --> 00:08:53,091
a very, very while, you might want to mark
and sweep collector to go through and

108
00:08:53,091 --> 00:08:58,231
clean out any circular but unreachable
data structures. We're now ready to wrap

109
00:08:58,231 --> 00:09:02,330
up our discussion of automatic memory
management. And so I just want to make a

110
00:09:02,330 --> 00:09:07,557
few, high level points here. First of all,
there's no question that automatic memory

111
00:09:07,557 --> 00:09:12,799
management is a great thing. It prevents
very serious storage bugs, some of the

112
00:09:12,799 --> 00:09:17,792
most difficult bugs in programming, and
when you're writing in the garbage

113
00:09:17,792 --> 00:09:23,214
collected language you really have just a
whole class of things you don't have to

114
00:09:23,214 --> 00:09:28,602
worry about and so it is certainly a more
productive way to program. So if, if your

115
00:09:28,602 --> 00:09:34,706
problem, your program is really a good fit
for automatic memory management then you'd

116
00:09:34,706 --> 00:09:39,165
be crazy not to use a system that provided
that kind of support. Now, the

117
00:09:39,165 --> 00:09:43,025
disadvantage of automatic memory
management is that it reduces programmer

118
00:09:43,025 --> 00:09:47,618
control. So you don't have control anymore
over the layout of data and memory, and

119
00:09:47,618 --> 00:09:51,996
you don't have control over when the
memory is reallocated. So, you neither

120
00:09:51,996 --> 00:09:56,586
have control over where the data is in
memory and you have only a very limited

121
00:09:56,586 --> 00:10:01,417
amount of control over how much memory
your program is using, okay? And so if

122
00:10:01,417 --> 00:10:06,467
these two things don't matter, if your, if
your application is not extremely data

123
00:10:06,467 --> 00:10:11,365
intensive where the precisely out of data
memory and how much data is residing in

124
00:10:11,365 --> 00:10:16,030
memory is important then garbage
collection will likely work very well. But

125
00:10:16,030 --> 00:10:21,203
there are applications particularly high
end data processing and scientific

126
00:10:21,203 --> 00:10:26,560
applications which use a lot of data and
need to make very, very efficient use of

127
00:10:26,560 --> 00:10:32,116
the memory where garbage collection
actually becomes too inefficient to do a

128
00:10:32,116 --> 00:10:37,037
good job and people in those domains still
use manual memory management. But there

129
00:10:37,037 --> 00:10:41,652
are some other issues. So, in real time
applications the pauses can be

130
00:10:41,652 --> 00:10:46,271
problematic. So, if you have a program
that needs to meet guaranteed deadlines,

131
00:10:46,271 --> 00:10:51,811
many embedded systems that are interacting
with the outside world say controlling

132
00:10:52,020 --> 00:10:57,228
dangerous machinery and things like that
they have to have response times that are

133
00:10:57,228 --> 00:11:01,074
guaranteed to make sure that nothing
terrible happens. And, and you know,

134
00:11:01,074 --> 00:11:06,072
introducing a automatic memory management
system that might pause for arbitrary

135
00:11:06,072 --> 00:11:11,347
amounts of time you know, makes that a
very problematic things guaranty. So, you

136
00:11:11,347 --> 00:11:17,222
don't always see garbage selection used in
real time applications. Although there has

137
00:11:17,222 --> 00:11:22,465
been a lot a progress in the last several
years on real time garbage collectors.

138
00:11:22,465 --> 00:11:27,345
Another issue for every programmer who
uses automatic memory management probably

139
00:11:27,345 --> 00:11:32,119
will have to face is the problem of memory
leaks. So, while automatic memory

140
00:11:32,119 --> 00:11:37,237
management prevents you from corrupting
your memory, it really doesn't prevent you

141
00:11:37,237 --> 00:11:42,273
from hanging on to too much data and
possibly affecting the performance of your

142
00:11:42,273 --> 00:11:47,264
program dramatically. So, memory leaks are
possible in garbage collected languages

143
00:11:47,264 --> 00:11:51,979
and I would say they are even likely.
Said, you know, the fact that you're not

144
00:11:51,979 --> 00:11:56,948
as aware or not as forced to be aware of
how the memory is being used makes it

145
00:11:56,948 --> 00:12:01,853
easier to have memory leaks. And the kind
of memory leak that you will have in say,

146
00:12:01,853 --> 00:12:07,740
a Java program is that you'll have some
you know, some variable say x that points

147
00:12:07,740 --> 00:12:13,257
to some data structure and this data
structure is gigantic, okay? So lets say

148
00:12:13,257 --> 00:12:19,339
that this is the abstract syntax tree, in
a compiler, alright? Now there may come a

149
00:12:19,339 --> 00:12:24,719
point in the computation where you don't
need the abstract syntax tree anymore. So

150
00:12:24,719 --> 00:12:29,216
let's say that we have converted to an
intermediate language and from the

151
00:12:29,216 --> 00:12:32,858
abstract syntax tree and now all our
processing for the rest of the compilation

152
00:12:32,858 --> 00:12:36,476
is going t be on the intermediate language
representation and generating code from

153
00:12:36,476 --> 00:12:41,149
that, we never go back and look at the
abstract syntax tree again. Well, the

154
00:12:41,149 --> 00:12:45,119
compiler I mean, excuse me, the, the
garbage collector doesn't know that you

155
00:12:45,119 --> 00:12:49,171
are not going to use the abstract syntax
tree again in the future. And if you have

156
00:12:49,171 --> 00:12:52,847
a variable that's pointing to this
gigantic data structure even if you are

157
00:12:52,847 --> 00:12:57,209
not using it, it's gong to hang around and
is going to be using up memory. And so the

158
00:12:57,209 --> 00:13:01,937
right thing to do is when you reach a
point in program where you are not going

159
00:13:01,937 --> 00:13:05,985
to use this data structure anymore is to
assign x the null value. You want to

160
00:13:05,985 --> 00:13:10,026
assign x to null at that point and
essentially dropping this pointer to the

161
00:13:10,026 --> 00:13:13,880
data structure. And now the garbage
collector, whatever form it is, mark and

162
00:13:13,880 --> 00:13:18,657
sweeps, Stop and copy or reference
counting will be able to see that this is

163
00:13:18,657 --> 00:13:22,576
no longer reachable and will collect that
big structure. And this is very, very

164
00:13:22,576 --> 00:13:27,083
common in, in production Java programs to
have these kinds of memory leaks where you

165
00:13:27,083 --> 00:13:32,797
just have pointers that you forgot about
to data that you're no longer going to

166
00:13:32,797 --> 00:13:38,860
use. So as a whole, I have conveyed in the
last few lectures, garbage collection is a

167
00:13:38,860 --> 00:13:43,094
very important technique. Every programmer
should be aware of its benefits and costs

168
00:13:43,094 --> 00:13:47,445
and it's also very interesting aspect of
programming language implementation. There

169
00:13:47,445 --> 00:13:52,087
are much more advanced garbage collecting
algorithms than we have discussed in these

170
00:13:52,087 --> 00:13:56,595
lectures and the primary dimensions along
which people have thought about improving

171
00:13:56,595 --> 00:14:00,535
garbage collection, that is making garbage
collection concurrent. That means allowing

172
00:14:00,535 --> 00:14:04,906
the program to continue to run while other
collection is happening. So the collector

173
00:14:04,906 --> 00:14:09,532
is working in the background actively
while the program is running. Another

174
00:14:09,532 --> 00:14:15,118
thing that's very common actually in, in
production collectors is to what's called

175
00:14:15,118 --> 00:14:20,706
a generational collector. And the basic
idea here is that we don't want to keep

176
00:14:20,864 --> 00:14:25,347
going over lo oking at objects that are
very long lived on every collection. So,

177
00:14:25,347 --> 00:14:30,205
collections happen very frequently and
there will be some objects that just live

178
00:14:30,205 --> 00:14:34,312
for very long time, the big data
structures that hang around for most of

179
00:14:34,312 --> 00:14:39,389
the program. And once we have seen them,
in a couple of collections we probably can

180
00:14:39,389 --> 00:14:43,332
assume that they're going to be around for
a few more collections. And so in a

181
00:14:43,332 --> 00:14:47,692
generational collection sorry in a
generational collector older objects,

182
00:14:47,692 --> 00:14:52,374
objects that have been around for a while
are put in a seperate area and they're

183
00:14:52,374 --> 00:14:56,474
collected less frequently. And this just
allows the collector to focus on the

184
00:14:56,474 --> 00:15:00,837
objects that are most likely to be garbage
which are the recently allocated objects.

185
00:15:01,006 --> 00:15:05,703
We already talked a little bit about
Realtime. So there are collectors that try

186
00:15:05,703 --> 00:15:09,803
to bound the length or the, bound the
length of the maximum pause, the maximum

187
00:15:09,929 --> 00:15:14,317
interruption to the program. And finally
parallel collectors. So collector systems

188
00:15:14,317 --> 00:15:18,586
where the garbage, there's actually
several garbage collectors running at the

189
00:15:18,586 --> 00:15:23,002
same time and somehow coordinating their
actions.