Welcome back. 1
In this video we're going to talk about the last basic GC algorithm, known as the Reference Counting. 2
The Reference counting is a direct collector, that is, recall from the previous lectures 3
it identifies directly the garbage, instead of the alive objects, as do the tracing collectors. 4
So, let's dive into details of the Reference counting collector, and see, how it reclaims the garbage. 5
The basic idea of a direct collector is that, instead of waiting while we run out of memory, and spawning 6
a tracing phase, what if we could just directly reclaim the garbage right at the moment it's identified? 7
And that's the first feature of the direct Reference counting collector: 8
It doesn't have explicit GC pauses, and in fact is deeply integrated into the Mutator. To identify 9
which object is a garbage, the direct collector tracks number of alive references to this memory block. 10
Hence the name -- Reference counting. 11
And when this counter drops to zero, the object can be reclaimed right away. 12
Let's consider the following example. 13
So let's say we have allocated the object A. From the compiler perspective 14
it looks as the name `a` is now bound to the heap-allocated object A, that is the variable `a` is a pointer. 15
Then we do the same with the object B, and to sign it to the `b` pointer. The Object header in case of 16
the Reference counting collector stores 17
as we said, the number of all alive strong references to this objects. 18
And again the _strong_ references is important here, since as we know, there are also weak references which 19
do not increase the reference counter. 20
So the counter of both objects A and B is set to 1 on the initial assignment. 21
And then, let's say, at some point we decide to rebind the `b` pointer to the same memory location 22
that is, to the object A. 23
This may seem a very trivial operation, and it's true -- assignment is the most frequently used operation 24
in our code 25
But let's see what's happening under the hood of such assignment 26
when we work in the Reference-counted system. The Reference counting collector works exactly by 27
overloading operations of assignment and deletion of the objects. 28
In fact, the trivial assignment from above under the hood is translated to the following four actions. 29
First of, all since the object pointed by the variable `a`, that is the object A, is receiving now a new extra 30
reference, through the variable `b` 31
we have to increase the reference counter of A, and set it to 2. Next, since the object previously pointed 32
by the variable `b`, is now losing the reference, we need to decrease the reference counter of the object B 33
and now it's set to 0. Next action 34
we need to check, whether the counter of B is now 0, and if so (and it is so in our case) we just reclaim 35
the object B 36
right away without waiting for any GC cycles, pauses etc. This algorithm a very simple and efficient 37
however, as we'll see shortly, it has some caveats. 38
And once it's done, the final action -- we are now allowed to update the actual pointer value of the 39
variable `b` 40
So, now both variables point to the same memory allocation, and what is correctly reflected in the reference 41
counter of the object A 42
As we said, there is a caveat in the basic algorithm which we have discussed. In the case when we identify 43
the reference counter as 0, before we are allowed to remove this garbage 44
we have to handle first the child pointers of this object. 45
What this means, we have to go deeper into the child pointers 46
and since those children will be losing the reference from the parent object, we have to decrease their 47
reference counter as well 48
But before that we have to go deeper to the children of the children, and repeat the whole process for 49
them as well 50
That is, the reclamation process is deeply recursive, and can itself take a lot of time. And can even 51
be considered as sort of a "GC pause". As you can see, all the objects have been recursively removed, and 52
we don't have any memory leaks 53
Now let's take a more complex example, and have a large tree of the objects 54
So, let's say, we decide to remove this object. Following the algorithm which we've just discussed 55
it spawns recursive delete of the whole large sub-tree, resulting to a real-time GC pause. 56
So, if the reclaiming sub-tree is really large, with a lot of clean up, the user code may stuck not 57
doing any useful work, while the collector is reclaiming the garbage. 58
Okay, now let's take a look at the major problem on this collector. 59
Let's say, we're a move now this object. 60
Again, it causes removing of the whole sub-tree, and here we've got one problem. 61
Take a look at the last object which have a cyclic reference to its parent. 62
This reference makes the parent reference counter to be never dropped to zero. 63
It always stays with the value 1, and we get a memory leak here. 64
This is a well-known problem of the Reference counting collector, and it cannot do anything with such 65
cyclic references 66
So, unfortunately the fact that we have a garbage collector doesn't mean yet that we won't have memory leaks. 67
Again let's take a look at the problem of cycles on the simplified example. 68
So, we have some root pointing the object A, which points the object B, which in turn points back to object A. 69
The reference counter of A is now 2. And then, let's say, we have lost the connection from the 70
root 71
This leaves the ref-counter of A forever as 1, and it cannot be reclaimed, becoming a memory leak. 72
And if you think that such cyclic structures are uncommon, this is actually not true. 73
We deal with them every time when have for example doubly-linked lists, trees, when child nodes keep references 74
back to the parent, etc. And the solution here might be having an extra tracing collector. For example 75
Marks-Sweep, which runs occasionally to clean up the cycles 76
Let's take a look at the abstract code implementation of the Reference counting collector. 77
As we said, all the assignment and deletion operations have to be tracked to manipulate the reference 78
counter 79
We should also mention that the counter manipulation should be an atomic operation -- in order to avoid 80
race conditions and to be thread-safe 81
So, on assignment we increase the counter of the source object. And then we have to decrease the counter 82
of the destination object, which is now losing the reference. 83
This is done through the generic `reclaim` procedure, which handles also the deletion of the objects. 84
So, we decrease the RC, check if we can free the object, and go recursively deeper reclaiming the child objects. 85
Finally, we can free the object itself, and update the actual pointer. Here's the small summary of the 86
Reference counting collector 87
Let's take a look. As we can see, it's a direct collector, that is, in contrast with the tracing collectors 88
it identifies explicitly the garbage, and don't have explicit GC pauses. The phases of this collector 89
include manipulation of the reference counter on several objects, and recursive analysis 90
of the child pointers, which as we said, can be considered as a "GC pause" in case of the large sub-trees. 91
It is a non-moving collector, which means, it can be used by the languages which expose the pointer semantics 92
such as C or C++ 93
In fact, the `std::shared_ptr` type in C++ is nothing but a primitive Reference counting collector. 94
As a result of being non-moving collector 95
it requires the slower Free-List allocator, when we have to traverse the free blocks, until we find 96
the chunk of a needed size. 97
And finally, main issues of this collector are: the cyclic references, which it simply can't handle 98
producing the memory links 99
and also we can mention the overhead on the Mutator, since every assignment and delete operations have to 100
be overloaded to consider the Collector's work. 101
Notice, that even non-destructive assignments, such as in the for-loops, have to be handled as well. 102
For example, we traverse the collection `foo`, and then each element of this collection during the traversal 103
will be receiving a you reference through this `bar` variable 104
So, a basic implementation will be doing a lot of useless increment and decrement counter operations. 105
A more optimized compiler would avoid manipulating the counter in such cases. 106
Okay. 107
At this point we have discussed all the basic GC algorithms, and are now ready to talk about more advanced 108
topics 109
So far we've been talking about single-threaded blocking collectors, which operate on the whole heap. 110
This can be pretty slow if the heap is large, and we have a lot of garbage. 111
So many modern production collectors involve different techniques to reduce these GC pauses, and make 112
the collectors faster 113
The first advanced topic we're going to talk about is the Generational garbage collection, and which 114
we'll be discussing in the next video.