Welcome back. 1
In this lecture we continue our discussion about the tracing collectors, and consider one more algorithm 2
known as the Copying collector. Recall the issues of the previous two collectors we have discussed. 3
The Mark-Sweep collector works on a fragmented heap, and has the slower Free-List allocator. The Mark-Compact 4
collector fixes 5
this fragmentation, and allows the faster Bump-allocator. 6
However, it does it in a price of a slower collection cycle, and depending on the algorithm can require 7
up to 3 times of the heap traversal in order to compact the heap. 8
So today we'll discuss how we can achieve the same fast Bump-allocator, and to avoid the fragmentation 9
as in Mark-Compact, and at the same time to have a faster collection cycle. And this faster collection 10
cycle comes of course also not without a price. 11
In this case we're go into trade storage for speed. And that's the first issue of the Copying collector 12
it requires half of the heap to be reserved for the Collector purposes. Such collector is known as 13
Semi-Space collector 14
The area on the left is known as the From space 15
sometimes it's called the Old space. And all allocations happen exactly and only in this From space. 16
The area on the right is called the To space (or the New space), and is reserved for the garbage collector. 17
Okay so as usually let's allocate an object graph which we can work with. So we allocate the object A 18
pointed by the Root. Then we allocate the object B pointed from A. 19
The objects C pointed 20
let's say, also from A. The object D pointed from B. 21
And finally, the object E, pointed from C. And also let's have a reverse connection back from E to C. 22
And here we've got the first issue. 23
We actually ran out of memory. Despite having the half of the actual heap still available 24
we cannot use it, since as we agreed, it is reserved only for the garbage collector. 25
And again to repeat, this is the price, the "tax" we're going to pay for the faster collection and allocation. 26
And then let's say at some point we have lost the connection from A to B object, here. 27
This makes the object B unreachable 28
that is, it becomes a garbage. And the same is true for its direct child, the object D. 29
So let's see how a Copying collector reclaims this garbage and provides a fast compacted heap with 30
no fragmentation. 31
The Copying collector works in four stages. 32
Let's consider them in detail. The tracing stage of this collector is known as the Copy stage or Evacuation. 33
What it means, is that we're going to traverse the object graph, chasing only the alive pointers, and copy 34
the alive objects to the New space, while we traverse the graph. 35
So as in a casual trace, we start analysis from the roots, and the reach the first object A, which is 36
guaranteed to be alive, since it's pointed by the root. We go ahead and copy the object A to the new 37
area, using just the Bump-allocation mechanism in the New space. 38
The next step: in the old copy of A we're going to store what is known as the Forwarding address, that is 39
the new address where we've just copied the object A. Why is it needed? 40
Well, the idea here is similar to the forwarding address used in post offices. 41
When you move to a new home, and can just redirect all your incoming main to this new address. So someone 42
later will be looking for the object A, and they will be able to find it in the new location using 43
this forwarding address. We can keep the forwarding address either in the object header or actually directly 44
in the old copy of A, since it's already has been evacuated, and we can overwrite any data in the old 45
copy for our own purposes. 46
Okay, so we have stored the forwarding address. Next action: after we have copied the object A to the 47
new space 48
we've got a slight problem here. 49
Notice that this is literally a bit-for-bit copy. What it means, all the child pointers of A in the 50
new copy still point of the old locations. 51
So we have to fix this child pointers to point to the new location. 52
This stage is known as Scanning of the copied objects for the child pointers, and for this there should 53
be here. 54
the Scan pointer. And while the Scan pointer doesn't equal to the Allocation pointer 55
we still have work to do. So as we can see, the old object A points to the old object C. As well 56
as the new A points to the old object C. And we need the new A to point to the new C. 57
But where is the new C? 58
It hasn't yet been copied. And since something alive, that is the new copy of A, is now pointing the old 59
object C, this is actually the good news for the object C: it means, it is also alive. 60
So we have to repeat now the algorithm for the object C. The same as with the object A, we evacuated the 61
object C to the New space. And once it has been copied 62
we can now update, that is fix, the pointer from A to the new copy of C. 63
Next, we keep the forwarding address in the old copy of C, and again have to scan the copied object and 64
fix its child pointers. As we can see, it still points to the old copy of E, and this is good news for 65
the object E, because it's now also identified as alive. So we evacuate the object E now. Fix the pointer 66
in C to point to the new E. We keep the forwarding address in the old copy of E, and have to fix its 67
child pointers 68
The only child pointer of E is the reverse pointer back to C. And we have to evacuate the object C. 69
But, the object C has already been evacuated. 70
And here is where the Forwarding address comes into play. 71
The presence of the Forwarding address in the old copy is the sign, that the object has already been 72
copied, and that we don't need to double-copy it. 73
Otherwise, we would be breaking the heap invariants by allocating more memory than we need. 74
So we just update the child pointer in the new copy of E to point to the new copy of C, and we take this 75
new address exactly from the Forwarding address store in the old object. At this point we don't have 76
any other child pointers to fix. What it means 77
the Scan pointer is now reached the Allocation pointer, and this means that the evacuation is completed. 78
Now the final stage in this algorithm is that we swap the To and From space in the roles. The To space 79
is becoming now the new From space, and the previous From space is now becoming the new To space, reserved 80
for the garbage collector. 81
Notice how we didn't even touch the B and D garbage, and how they naturally got reclaimed by abandoning 82
the Old space completely. 83
That's why this collector can the faster than the Mark-Sweep, since it doesn't need to traverse the whole 84
heap to reclaim the garbage. 85
Notice also how we have the naturally compacted heap in the allocation area, and in contrast with the Mark-Compact 86
which required up to 3 times of the heap traversal for this, with the Copying collector we 87
did it just in one pass during the tracing phase, and visiting only small portion of alive objects on the heap. 88
Taking into account these details, the Copying collector can probably be considered the fastest 89
collector, which allows also the fast Bump-allocation. And as we have said, the price for this faster 90
speed, is the half of the heap to be reserved for the garbage collector, which in some cases can actually 91
be a pretty high price. 92
For example, in some embedded system, when you have only a small amount of memory available. Here is 93
the abstract code implementation of Copying collector. 94
So we start by copying the roots. And then as long as we still have the copied objects to analyze 95
that is, the Scan pointer hasn't reached yet the Allocation pointer 96
we go ahead and analyze the child pointers, evacuating them as well. 97
If a child object has already been copied, that is it has the forwarding address set 98
we just update the child pointer to the new value, stored in this forwarding address. And we advance 99
scanning to the next object. 100
Otherwise, we copy the child object, and store the forwarding address. 101
Here is the small summary of the Copying collector. 102
Let's take a look. 103
First of all, it is a tracing collector 104
that is, it has GC pauses, and identifies alive objects. 105
The main advantage of the Copying collector again, is that it does everything exactly on the tracing stage 106
not even touching the garbage. So it has to evacuate alive objects to the New space and, to fix the 107
child pointers, repeating the evacuation process for the children. The same as the Mark-Compact 108
It is a moving collector 109
that is, unfortunately it cannot be used by the languages which exposed the pointer semantics such a 110
C or C++, but it can normally be used by the languages like JavaScript, Python, etc. With the Copying collector 111
we can use the fast Bump-allocator, and to have a naturally compacted heap with no external 112
fragmentation. And as an issue of this collector we can point the "storage tax", when we have 113
to reserve the half of the heap for the collectors purposes. 114
So if you compare the tracing collectors, we can see the following picture. 115
The Marks-Sweep is the simplest but has the external fragmentation, and slower allocation. The Mark-Compact 116
fixes the fragmentation, and provides faster allocation, but has slower GC cycles. 117
The Copying collector doesn't have the fragmentation, and provides the faster allocation, and also may 118
have faster GC cycles, but requires half of the heap to be reserved. Which tracing collector to choose? 119
Well, it's really up to your use case, and the environment 120
you have to work with. If you have to expose pointers, as in C or C++, then you really can't use none 121
of the moving collectors, such as the Mark-Compact or the Copying collector. 122
If you have a few memory where each byte counts, then you can't use the fast Copying collector. 123
So, choose wisely considering all the related factors and trade-offs. 124
Okay at this point we have described all the tracing collectors, and are now ready to talk about 125
the Direct collector known as the Reference counting. 126
It's also widely used on practice 127
for example, C++, Python, Objective-C, etc, and which will be discussing in the next video.