1
00:00:03,003 --> 00:00:07,011
In this very short video, I'm going to say
a few words about a technique called

2
00:00:07,011 --> 00:00:13,288
Conservative Garbage Collection that can
be used for languages like C and C++. To

3
00:00:13,288 --> 00:00:18,524
review, Automatic Memory Management relies
on being able to find all the reachable

4
00:00:18,524 --> 00:00:22,908
objects. And it also needs to be able to
find all the pointers in an object. Now,

5
00:00:22,908 --> 00:00:26,743
the difficultly with doing garbage
collection for a language like C or C++ is

6
00:00:26,743 --> 00:00:31,607
that it's very difficult or even
impossible to identify the contents of

7
00:00:31,607 --> 00:00:37,121
objects in memory with 100 percent
reliability. So if we see, two words in

8
00:00:37,121 --> 00:00:41,801
memory, you know, it might be a list cell
that has, a data and next field. So we see

9
00:00:41,801 --> 00:00:47,276
just two words here. And there are some
bit patterns in here, 0's and 1's. Okay

10
00:00:47,276 --> 00:00:51,900
how do we know whether these are both
pointers? It could be that one is a

11
00:00:51,900 --> 00:00:55,716
pointer and the, the other is not in the
case of a list cell. So one of these

12
00:00:55,716 --> 00:00:59,084
fields is just data like an injure and
another one is a pointer. Or it could be

13
00:00:59,084 --> 00:01:04,363
something like a binary tree node where
both of these words are pointers. And

14
00:01:04,363 --> 00:01:10,004
because of this weakness really in the C
and C++ type systems, we just can't

15
00:01:10,004 --> 00:01:15,204
guarantee that we know where all the
pointers are. Now it turns out that it is

16
00:01:15,204 --> 00:01:19,689
possible to extend garbage collection
techniques to work with languages like C

17
00:01:19,689 --> 00:01:24,939
and C++. And the basic idea, or insight,
is that it's always okay to be

18
00:01:24,939 --> 00:01:29,051
conservative. And if we're not sure
whether something might be used in the

19
00:01:29,051 --> 00:01:33,013
future, then we will just keep it around.
And remember that graph reachability is

20
00:01:33,013 --> 00:01:37,591
already a conservative technique. What we
really want is to keep around the objects

21
00:01:37,591 --> 00:01:42,664
that will just be used in the future, but
the reachability in the object graph is an

22
00:01:42,664 --> 00:01:46,631
approximation to that, so because
reachable objects might be used. And now,

23
00:01:46,631 --> 00:01:50,533
the problem with C and C++ is that we
don't know where the pointers are. We

24
00:01:50,533 --> 00:01:54,303
don't have a guarantee from the type
system about where the pointers are. And

25
00:01:54,303 --> 00:01:58,308
so the basic trick is that, if something
looks like a pointer, then we will treat

26
00:01:58,308 --> 00:02:03,163
it as a pointer. All we have to do is be
conservative, and if we are not sure wh

27
00:02:03,163 --> 00:02:07,101
ether a given word of memory is a pointer.
Then we can just treat it as a pointer,

28
00:02:07,101 --> 00:02:11,590
and keep whatever it points to around. If
we, and as long as we are not going to

29
00:02:11,590 --> 00:02:16,001
move it or change it, that would be okay.
And so, how, how do we decide whether a

30
00:02:16,001 --> 00:02:20,038
particular word of memory is a pointer?
Well, it should be a line, meaning, you

31
00:02:20,038 --> 00:02:23,714
know, it should end in some zeros to
indicate that it was pointing, if it was a

32
00:02:23,714 --> 00:02:27,490
pointer it was pointing to a word
boundary. And then, whatever pattern it

33
00:02:27,490 --> 00:02:31,657
is, if we interpret it as an address, it
has to be a valid address. So, it should

34
00:02:31,657 --> 00:02:35,414
point to the data segment. And Noah said,
you know, these two conditions will rule

35
00:02:35,414 --> 00:02:41,701
out all kinds of data and memory. So for
example, any small integer is probably not

36
00:02:41,701 --> 00:02:45,967
going to be interpretable as a valid
address in the data segment. So, you know,

37
00:02:45,967 --> 00:02:50,732
most likely, only things that are
pointers, or very few things that are not

38
00:02:50,732 --> 00:02:54,171
pointers will be treated as pointers. And
what we're going to do then, is, if it

39
00:02:54,171 --> 00:02:57,922
looks like a pointer, we're going to
consider it to be a pointer. We'll follow

40
00:02:57,922 --> 00:03:01,873
it, and then we'll end up overestimating
the set of reachable objects. We may keep

41
00:03:01,873 --> 00:03:07,288
around some stuff, that isn't reachable at
all. But that's alright, it's always okay

42
00:03:07,288 --> 00:03:11,530
to keep around more stuff than necessary.
Now, we still can't move the object,

43
00:03:11,530 --> 00:03:15,192
alright? Because we can't update the
pointers to them. If we don't know that

44
00:03:15,192 --> 00:03:18,754
something is a pointer, we certainly don't
want to change it, okay? And, you know,

45
00:03:18,754 --> 00:03:21,569
for example, if we thought something was a
pointer, and it was actually an account

46
00:03:21,569 --> 00:03:25,116
number, and then we updated the pointer,
when we move the object, we would just

47
00:03:25,116 --> 00:03:29,532
completely change what the program does.
So, this only really works when you mark

48
00:03:29,532 --> 00:03:30,037
this way.