Welcome back. 1
In this video we start our discussion about GC algorithms and the first algorithm we're going to consider 2
is the widely used practice, known as Mark-and-Sweep. 3
The Mark-Sweep is a tracing collector, that is, as we know from the previous lectures 4
It identifies alive objects instead of the direct garbage. 5
Let's go ahead and allocate some objects on the heap, so we can have a work use case for our collector. 6
For simplicity we're going to use only one root pointing the first object. 7
So, we allocate the object A pointed by the Root. Then we allocate the object B pointed from A. We allocate 8
object C pointed, let's say, also from A. The object D, pointed from B, and finally, the object E, pointed 9
from C. And then at some point, let's say, we have lost the connection from A to B object, here. 10
This potentially makes the object B a garbage, since it's not reachable from the root. But not only the 11
object B. Also its direct child, the object D, is also becoming a garbage. 12
So let's dive into details how the marks sweep algorithm actually identifies the garbage and reclaims it. 13
As the name suggests, the Mark-Sweep collector works in two phases: the Mark phase, which is actually 14
the trace for the alive objects. And the sweep phase, which already reclaims the garbage. In order to 15
track which objects are alive during the Mark phase, the Mark-Sweep collector stores (in the object header) 16
the Mark-bit. It's just a boolean flag, and if an object is alive, the flag is set. 17
Let's take a look how the marking phase actually finds the alive objects. 18
So, as usually, we start analysis from the roots, and reach the first alive object 19
that is the object A, which is guaranteed to be alive since it's pointed by the root. 20
Then we follow the child pointers of A. 21
In this case is the only pointer to the object C, which now is also identified as alive. With the 22
same success 23
we follow the child pointer of C, and mark the object E as a alive. And at this point the Mark phase is 24
completed. 25
Let's take a look at the abstract code implementation of the Mark-Sweep algorithm. 26
And focus on the Mark phase first. 27
So, as we said, we start from the roots and to initialize our `todo` list. And as long as we still have 28
something in this `todo` list, we check whether the object has already been marked. And if not, we mark it 29
by setting the Mark-bit. And then go deeper to the child pointers of the current object 30
also adding them to our `todo` list. After traversing of this object graph all visited, that is reachable 31
objects will be marked. 32
Okay let's take a look at the Sweep phase. 33
Now, in contrast with the Mark phase, which visited only small portion of the heap, chasing only the 34
alive pointers, the Sweep phase has to traverse the whole heap 35
starting from the very low addresses, and up to the end of the heap. That is, it considers every single 36
object, one by one, increasing the scan pointer by the size of the previous object. 37
Let's take a look at the details. 38
So the first object which check is the object A, and which has the Mark-bit set. 39
This means the object is alive 40
so we just reset its Mark-bit (for the future collection cycles), and proceed to the next object B. 41
Now, the object B doesn't have the Mark-bit set, which means it wasn't visited during the Mark phase, and 42
hence is a garbage. 43
What this means, is that the memory block occupied previously by B, can now be reused in future allocations 44
and for this the block is added to what is known as the Free-List 45
that is, the linked list of all free blocks currently available on the heap. 46
And 47
we proceed to the object C. The object C has the Mark-bit, so it's alive: we reset the Mark-bit and 48
proceed to the next object. 49
The object D is not alive. And the same as the object B, is added to the Free-List. And finally we 50
identity the object E as alive, and just reset its Mark-bit. 51
At this point the full collection cycle is completed, and as you can see, we have reclaimed two memory 52
blocks previously occupied by the objects B and D. 53
Let's get back to our code implementation and see the Sweep phase. 54
So, as we said, we start at the very beginning of the heap, and until we reach the end of the heap, we 55
consider 56
each object: we check, whether the object was visited (that is, its Mark-bit is set), and if so, this 57
object is alive. 58
We just reset its Mark-bit and proceed further. 59
Otherwise, the object was not marked, and it means it's a garbage. 60
So we return it back to the allocator, and as we have seen, the Mark-Sweep uses the Free-List allocator 61
to track all available free blocks. 62
And again we proceed to the next object. 63
This depends on the implementation 64
for example, it might be increasing the `p` pointer by the size of the previous object, or it could be 65
an explicit `next` pointer from the Object header 66
as in this example. And by the end of the Sweep operation all the garbage will be reclaimed and will 67
be reused in the future allocations. 68
Let's briefly talk about the main features of Mark-Sweep collector. 69
First of all, it is a non-moving collector. 70
What it means, is that all objects after the collection cycle stay at exactly the same position, as they 71
were prior the collection cycle. 72
The is true for the free blocks. 73
They are not moved anywhere, but added to the Free-List. Next, to the direct consequence from the first 74
feature, is that for the allocation we use exactly the Free-List abstraction. 75
And this means, that to satisfy an allocation request, we have to first find a block of a needed size 76
traversing the linked list of the free blocks. 77
And this is exactly why the heap allocation is in general considered slower than the stack allocation. 78
And finally, what is also the consequence from the previous two features, is the heap fragmentation. 79
Notice again that the free blocks stay also at the same position. And such fragmented heap is the source 80
of slower allocation, and potential allocation failures, when overall, combined, we would have enough space 81
on the heap 82
but because of this fragmentation, will not be able to find a chunk of needed size. 83
Okay. 84
Here is the small summary of the Mark-Sweep collector. 85
Let's do a quick recap. 86
First, it is a tracing collector, which means it has GC pauses, and has a trace phase to identify 87
alive objects. 88
It has two phases: the Mark phase, which is the actual trace 89
and the Sweep phase, which reclaims the garbage. 90
As we mentioned, it is a non-moving collector, which means it can be used by the languages which expose 91
the pointer semantics, such as C or C++. 92
This is very important that the object stay at exactly same position. For allocation 93
it has to use however the Free-List abstraction, which may slow down the allocation requests. 94
And finally, what is the main issue of this collector 95
is the external heap fragmentation, which is bad for allocation speed and for cache locality 96
Okay. 97
Now when we know how Mark-Sweep collector works, we shall see how we can actually fix this fragmentation 98
problem. 99
This is achieved by the Mark-Compact and Copying collectors, which we are going to discuss in the next 100
lectures.