Welcome back. 1
In this video we start our discussion about optimization techniques used to reduce GC pauses and 2
improved GC performance. 3
And the first topic we're going to talk about is the Generational garbage collection. 4
So recall the problem you had with the Mark-Sweep collector, specifically on the Sweep phase, when we 5
had to traverse the whole heap. And this whole heap traversal might be the source of the longer GC pauses. 6
The basic idea of a Generational collector is to partition the heap, and split it on so-called Generations 7
and then to collect each generation independently: the smaller a generation in size, the faster 8
the scan of this heap region 9
So once again, instead of traversing the whole heap, we traverse only a smaller portion of it. The generational 10
collector exploits so-called Weak generational hypothesis, which states that most of the objects in our 11
programs die young 12
What this means 13
well, mostly this relates to the temporary variables, which are allocated on the heap, and stay there 14
until the collection cycle 15
even if the function has already returned. So such temporary, or young, objects as we call them, usually 16
do not survive one function activation. In the basic form a generational collector has the Young generation 17
(sometimes it's called Eden), and the Old generation (sometimes it's called Tenured) 18
As we can see, the Young generation is much smaller than the Old generation. 19
Usually all the new objects are allocated in the Young generation, and the only way to get to the 20
Old generation is by promotion 21
If an objects survived long enough, for example, several collection cycles, it's got promoted. 22
As we have said earlier, the Young generation is collected much more frequently than the Old generation. 23
And periodically the collection cycles happens for the Old generation. 24
The collection of the Young vs. Old generation are known as the Minor and the Major cycles accordingly. 25
So let's take a look at this example. 26
Let's allocate an object graph in the Young generation. And then, let's say, at some point we have lost 27
the connection from B to D object. Analyzing the object graph from the root 28
we see that only objects A, B, and C are alive. And the objects D and E are the potential garbage. 29
And let's also say, the objects A, B, and C survived long enough, and it is a good time to promote them to 30
the Old generation. 31
At this point the objects are copied to the Old generation, with all the consequences of the Copying 32
collector, which we have discussed in the previous lectures 33
that is, fixing the child pointers, updating the root addresses, etc. So we can say that a Generational 34
collector is actually a natural extension of the Copying collector. 35
And finally, the Young generation is fully reclaimed for future allocation. And the same as in Copying 36
collector 37
this naturally reclaims the objects D and E. 38
Okay. 39
So far so good. 40
Now let's say we have allocated objects, which do not survive the collection cycle. 41
So they just got reclaimed in the Minor cycle, and we didn't even touch the larger portion of the heap. 42
Okay let's do one more example. 43
Now we have objects X, Y, and Z. 44
And similarly, let's say, we have lost the connection from Y to Z object. 45
Again this potentially makes the object Z has a garbage. 46
But now here's what's happened. 47
Somehow we've got a connection from the object C to Z. That is, from an object from the Old generation 48
to the objects in the Young generation. Is the object Z now a garbage? 49
Well, obviously not. 50
However, since we collect only Young generation, we don't have any roots from this generation which would 51
point to the object Z 52
So eventually in the Minor cycle it will be identified as a garbage, and incorrectly reclaimed. That is 53
will be breaking heap invariants by removing an alive object. 54
So what should we do here? 55
Somehow we have to treat the object C as another virtual root for this Minor cycle. 56
But how? 57
Here's the algorithm. 58
First of all, such pointers as from C to Z are known as the Intergenerational pointers. And to handle 59
such pointers 60
Generational collectors use what is called the Write-barrier. 61
We will talk about GC Barriers in detail in the next lectures 62
however, now we should say that the Write barrier is a hook, an event handler if you will, for all the 63
"Store pointer" operations. That is, whenever we try to store an intergenerational pointer, such as from 64
C to Z, at this exact moment we catch this event, and put the object C to the root set of the collection 65
cycle 66
Now we have one more root pointing the object Z, and it's of course not a garbage anymore. 67
After that the whole graph is again promoted to the Old generation, and the heap invariants are 68
preserved 69
Let's briefly talk about the actual implementation techniques used to determine the virtual roots set 70
through the Write barrier 71
The canonical implementation is known as the Card table. This is basically an array of bits, where 72
each bit is assigned to a certain region of memory 73
in the Old generation. The regions are usually grouped by the size, and usually of 4Kb 74
but it might be up to the implementation 75
This is done as an optimization technique in order to cover multiple objects with one entry 76
in the Card table 77
Whenever we have an intergenerational pointer, and the fact that it's stored in the old object, we set 78
the bit in the Card table, that this region is now considered dirty 79
That is, it has the write to the Young generation. 80
And then on the collection cycle this Card table is checked 81
in addition to the actual roots set. Every object from the regions marked by the Card table is considered 82
now a virtual root, and will be tracked for their life objects. Here's the small summary of the generational 83
collector 84
Let's take a look. 85
First of all, it is a tracing collector 86
that is, it has GC pauses 87
Advantage here though, is that we trace only smaller portion of the heap, but not the whole heap as it 88
was in a non-generational collector. 89
Usually a generation collector has Minor and Major collection cycles. 90
However, this can depend on the implementation 91
for example, Java's generational collector has 5 generations. 92
Next, is a moving collector, which means we can't use it in languages which expose the pointer semantics 93
such as C or C++, but we can use it for JavaScript. 94
Python, and other languages. 95
The interesting part, is that for the allocation and for actual collection algorithms we can use 96
different techniques based on the generation. 97
For example, it can be a Free-List allocator in the Young generation, but also use the Bump-allocator 98
in the Old generation, and vice-versa. 99
The same for the collection. 100
It can use the marking technique from Mark-Sweep collector, but to be Copying collector when we evacuate 101
that is, promote, the objects. And as we have said, there is an actual overhead on the Mutator 102
by using this Write barrier. When implemented purely at software level, such barriers can add significant 103
performance hit, so sometimes support from the hardware and operating system can be used. 104
For example, setting memory protection flags on certain regions, and the catching the Write to those 105
memory regions. To repeat again 106
the generational property of a collector doesn't relate to the actual collection algorithm. 107
For example, it might still be a Mark-Sweep or a Copying collector, and the generational property relates 108
mostly to the heap partitioning. 109
Okay now when we have clarified the ideas of the generational collector 110
we are ready now to move forward to other optimization techniques 111
and in the next lectures we'll talk about Parallel, Incremental, and Concurrent collectors.