Welcome back. 1
In today's lecture we start our discussion about compacting collectors, which provide better cash locality 2
and also faster memory allocation. 3
Recall the problem we had with a Mark-Sweep collector 4
that is, the external fragmentation, which is left after the collection cycle. 5
The root cause of this fragmentation is related to the fact, that some systems such as C++ have to retain 6
objects at the same location, since those systems expose the pointer semantics, so the objects should 7
stay at the same location, and the free blocks are not moved anywhere, but instead are added to the 8
Free List 9
and what might be the reason of the slower allocation. And the systems which do not expose the pointer 10
semantics, in fact do not need to maintain this invariant. 11
They can easily relocate the objects, compacting the heap, and avoiding the fragmentation. Today we'll be 12
discussing an in-place compacting collector, known as the Mark-Compact. And in the next lecture 13
we'll talk about another compactor, known as the Copying collector. 14
If you haven't watched the Mark-Sweep lecture yet, please address it first, since it is a prerequisite 15
for a better understanding of the Mark-Compact collection. 16
The Marking phase of the Mark-Compact collector is exactly the same as in the Mark-Sweep collector. 17
Let's take the same example we had in the Mark-Sweep lecture, and just briefly see the marking process in action 18
So, the same as previously, let's say, we have lost the connection from A to B object, and 19
what makes the object B, and D as a garbage. As the name suggests, the Mark-Compact collector works in 20
two phases: the Mark phase, which is the actual trace for the alive data. And which is followed by the 21
Compact phase, which already relocates the objects compacting the heap. The Object header in case of the 22
Mark-Compact collector 23
in addition to the Mark-bit, also stores the Forwarding address, that is the new address, where the object 24
will be relocated. 25
So, let's go ahead and trace the object graph from the roots. And our traversal identifies the objects 26
A, C, and E as alive. 27
Now, the compacting phase relocates the objects so, that no fragmentation is left. 28
Let's see the high level picture first before we dive into an actual compacting algorithm. 29
So, the object C is relocated to the place previously occupied by B, and the object E is moved to the 30
previous location of the object C. 31
With this we also get the ability to use the fast Bump-allocator, which allocates objects by just increasing 32
the allocation pointer, the same as in stack. And this Free area will again be correctly defragmented 33
after the next collection cycle. 34
So, again, this is just a high level picture of all Mark-Compact algorithms. 35
There are several actual compacting algorithms for the Mark-Compact. And one of the most used on practice 36
is the Lisp 2 algorithm. 37
So let's dive into the details of this algorithm. 38
This Lisp 2 algorithm works in three steps. 39
The computing new locations. Fixing the child pointers. And finally, relocating the objects. And each step 40
here unfortunately means the full heap traversal. So this is the price, the "tax" we're going to pay for 41
the fast compacted heap, and the fast allocation. 42
Let's focus on each step in detail. 43
On the first step we're going to compute the new locations, where the objects will eventually be moved. 44
we're not moving yet anything on this step, and just compute the relocation addresses. 45
For this the algorithm tracks the three pointers. The Free pointer is the position, where a scanning alive 46
object will be relocated. 47
The Scan pointer is to actually analyze each object. And the End pointer points to the end of 48
the heap. 49
So until the Free pointer has not reached the End pointer, we have work to do. 50
So, the first object we scan is the object A, which is alive, since it has the Mark-bit set. 51
Now, the new location of the object A will be the location, where currently the Free pointer points to. 52
And 53
Just by coincidence, the Free pointer is now set to the same location where the object A is. 54
So the object A will be moved to the same location. 55
That is, it will not be actually moved, and will stay here. 56
So we recorded the Forwarding address in the Object header of A, which points to itself, and advance 57
the Scan and the Free pointers. 58
The next object B which is not alive 59
so we just advanced the Scan pointer, and leave the Free pointer at the same position 60
not moving it forward. 61
So the next alive object will be relocated here. 62
The next object is C, which is alive, and we record 63
its new address to whatever the Free pointer points now 64
that is, to the memory block previously occupied by B. And now since we used the Free pointer we 65
advance both pointers further. The next object is D, which is not alive, and we advance just the Scan pointer. 66
Finally, we record the Forwarding address of the alive object E as the previous location of the object C 67
that is, where the Free pointer is set now. 68
And at this point the first step of the algorithm is completed, since the Scan pointer now reached the 69
end of the heap. 70
Okay, so we have computed the new locations. Let's see the abstract code implementation of this step. 71
So we initialize the `scan` and the `free` pointers to the beginning of the heap, and then, until we reach 72
the end of the heap, we check if the object is alive -- in which case we record its forwarding address to 73
whatever the `free` pointer is set now, and advance the `free` pointer. And we also unconditionally advance 74
the `scan` pointer. Again, the `free` pointer is advanced only if we found an alive object. 75
Okay. 76
The next step is to figure the child pointers, and update them to the new locations, which we have just 77
computed on the first step. 78
So we start from the roots and update the reference A of the Root to point to the new location of A 79
As we said, by coincidence, the new location of A is the same as its old location. 80
So it stays at the same address. 81
Now we're going to analyze again each object on the heap starting from the beginning and until the end. 82
So here should be again the can Scan and End pointers. 83
All right. 84
So the object A is alive, and it has the child pointer to C. 85
So we need to update this reference to the new location of C, and which is the previous location of the 86
object B. The next object B is not alive 87
so we just move forward to the next object. The object C is alive, and it has the child pointer to E, so 88
we update this reference to the new location, and eventually the object E will be moved to the location 89
of the object C. 90
So now the E reference of C points to C itself. The object D is not alive, so we skip it. And the object E 91
doesn't have any child pointers, so their analysis is completed. 92
Let's see the abstract code for this step. 93
So first we handle the roots, and then we go through the whole heap again, updating the child pointers 94
of the alive objects. And the last step of the algorithm is the actual relocation of the objects to 95
the new addresses. 96
So again we analyze the alive object A, and to move it to the forwarding address. 97
In this case as we said that the object just stays at its current position. The object B is not alive 98
so we skip it. The object C is alive, so it should be moved 99
and we relocate it to its forwarding address, that is to the previous location of the object B. 100
Notice, that the C pointer from A now points to the correct location of the object C. The next object D 101
is not alive 102
so we move forward. And the object E is alive, and is moved to its new location, that is to the previous 103
location of the object C. At this point the relocation is completed. 104
And as you can see, the heap is now compacted, and the allocation can proceed with the fast Bump-allocation. 105
Let's complete our code implementation for this step. 106
So again we do the full heap scan. And if an object is alive, we reset its Mark-bit for the 107
future collection cycles, and then relocate the object to its new address. And then proceed to the 108
next object. 109
Okay. 110
Here is the summary of the Mark-Compact collector. 111
Let's take a look. 112
First of all, it is a tracing collector, and has GC pauses identifying alive objects. 113
Again the trace phase is exactly the same as in Mark-Sweep 114
collector 115
It has two phases: the Mark phase, is the actual trace. And the Compacting phase 116
relocating the objects avoiding the fragmentation. Since we relocated the objects 117
It is a moving collector, which means unfortunately it cannot be used by the languages which expose 118
the pointer semantics 119
such a C or C++, but it can be used by languages like JavaScript, Python, etc.. 120
As for allocation this collector allows the fast Bump-allocator, also known as Sequential, as we have 121
discussed in the previous lectures. 122
That is, the same as in stack 123
it just needs to increase the allocation pointer to obtain a new memory block, which of course is much 124
faster than traversing the Free-List as it was in Mark-Sweep. 125
And as an issue of this collector we can mention the slower collection cycle which can require 126
up to 3 times of the heap traversal. 127
So in the next lecture we'll see how we can fix this slower collection problem 128
and at the same time to have the compacted and the fast Bump-allocation. 129
This collector is known as the Copying collector, and which will be discussing in the next video.