Welcome back. 1
Now we're getting closer to the discussion of the actual GC algorithms. Before this however we need 2
to discuss two main collector types, which are the Tracing and the Direct collectors. 3
So let's start with a Tracing collector first. 4
Let's consider the following object graph on the heap. To make the explanation simpler 5
usually in our discussions we're going to use only one or maximal two roots. In a real program 6
of course there might be more of them. 7
And recall also from the previous lectures that a GC root is a known reachable reference, which is hold 8
by a register or a variable on the stack. 9
So this object graph can represent a tree or a similar directed graph. 10
And let's say at some point we have lost the connection from the B to D object. 11
This means the object D, as well as its direct child 12
the object E, unreachable (unreachable from any root) 13
And at this point that they become good candidates for the garbage collection. 14
Notice here that despite having an actual reference to it, from object D, the object E is still considered 15
a garbage. 16
That is, exactly the concept of reachability, what is used in the tracing collection. 17
So, let's see how a tracing collector actually identify object D and E as a garbage. 18
And the first interesting thing here, is that regardless being called the "garbage" collectors, the tracing 19
collectors actually do not directly identify the garbage. 20
Instead it's quite the opposite. 21
They scan the heap to search for the alive objects. And everything else, by extension, they treat 22
as the garbage. A tracing collector always starts its analysis from the roots. 23
In this case as we said we have only one root. So the object A is guaranteed to be alive since it's 24
reachable from the root. And then the collector goes recursively deeper to the child pointers, traversing 25
the object graph further. So, it visits the object B, which now is also identified as alive. And with the 26
same success, the object C is also alive. 27
This traversal path is known as the Trace, and that's why such collectors are known as the tracing collectors 28
in a Stop-the-World algorithm, which we mentioned in the previous lectures 29
the trace happens exactly during the GC parts. 30
That is, when the Mutator threads are completely blocked. In a concurrent collector the trace may happen 31
in parallel with Mutator threads. And as we said, everything else, that is the objects D and E, by extension 32
are now identified as a garbage and can be safely removed. 33
Now let's see what the alternative approach known as the Direct collection proposes. 34
Now, the main thing or the Direct collector is that in contrast with the tracing collectors, it doesn't 35
have explicit GC pauses. 36
In fact, the Direct collector is deeply integrated into the Mutator, and reclaims the garbage exactly 37
at the moment it's identified. 38
That is the Direct collector explicitly, or directly, identifies the garbage (hence the name direct) and 39
not alive objects, as it was in the tracing collectors. 40
Let's consider the object graphs from the previous lecture devoted to the manual memory management and 41
recall also how we accidentally removed the object B, and then the object C became a memory leak. 42
Well, the good news are is that with a garbage collector we can safely remove the A->B pointer, and the 43
collector automatically understands that it has to follow the child pointer of B, and to reclaim the 44
object C first. And once it's removed, it will safely reclaim the object B as well. And -- no memory leaks. 45
In the second case 46
recall we had two roots, and what eventually caused the Dangling pointer issue. In this case the Direct 47
collector, also known as the Reference counting collector, will store a special value in the object header 48
known as the reference counter, that is, the total number of alive references to this object. 49
And once we try to remove B pointer from the first root, the collector just decreases the reference 50
counter of the object B, and prevents the dangling pointer from the Root 2, as it was previously in the manual 51
management issue. 52
Okay now when we distinguish the Tracing and the Direct collectors, we can name the actual GC algorithms 53
used today on practice. 54
So, today if we consider any existing programming language (to repeat, any existing), a garbage collector 55
in this language will reduce to one of the following four algorithms. 56
So, these are: the Mark-Sweep collector, Mark-Compact, Copying collector, and the Reference counting collector. 57
Notice that the Generational property of a collector, or whether it should run in parallel with Mutator 58
doesn't relate to the actual collection algorithm. 59
For example, it might be a Generational Concurrent Mark-Sweep collector, and still will have only four 60
actual algorithms. With this the first three collectors are the tracing collectors. And only the Reference 61
counting is the direct collector. 62
So, in the next lectures we're going to discuss each of these algorithms in detail, defined the actual 63
implementations, and see also how they differ when we consider concurrent or generational features 64
of these algorithms. 65
We start the analysis from the Mark-Sweep algorithm -- a widely used on practice tracing collector 66
(probably the most used algorithm), and which will be discussing in the next video.