Welcome back. 1
In today's lecture we'll consider one of the modern GC algorithms, known as the Mark-Region 2
and in particular one of its implementations -- the Immix collector. 3
First we should mention that the Mark-Region and the Immix are not a separate 4
algorithm type 5
It's rather a combination of the existing algorithms 6
So we still have the four basic algorithms, and the Mark-Region is built on top of them 7
The Mark-Region is a tracing collector, so let's recall specifics and the issues of each tracing collector type 8
The mark sweep, as we know, has the problem of the slower allocation due to the Free-list allocator 9
since the objects stay at the same location, and to find a free space 10
we have to traverse the list of the free blocks 11
However, it has a relatively fast collection cycle -- only one heap traversal on the sweep phase 12
The Mark-Compact fixes the fragmentation issue 13
so it allows the fast Bump-allocator 14
However, it does it in a price of a slower collection cycle, and requires up to 3 times of the 15
heap traversal 16
And the Copying (or Semi-space) collector 17
is also fragmentation-free 18
that is, with the fast Bump-allocator 19
It also has the faster collection cycle 20
in contrast with the Mark-Compact. However, does it in the price of taking half of the heap for the 21
collectors purposes 22
In other words, if we consider each tracing algorithm from the perspective of these three criteria: 23
the Space efficiency, Mutator overhead, and the Speed of the reclamation, we see that only two of them 24
are possible at the same time 25
The Mark-Sweep doesn't require extra space, and has relatively fast collection cycle, but suffers from 26
the fragmentation which eventually brings overhead on the mutator 27
The Mark-Compact again fixes the fragmentation, and is also space-efficient: relocates objects in place 28
but has the slower collection cycle 29
And the Copying collector is also fragmentation-free 30
It's also very fast: that the evacuation happens on the tracing phase, but requires half of the heap 31
to be reserved 32
that is, it's not space-efficient 33
So, the Mark-Region is an attempt to achieve all three at the same time 34
It allows the fast Bump-allocation, that is Mutator doesn't have much of the overhead 35
It also has the fast reclamation, and at the same time tries to be space-efficient 36
So let's see details of this algorithm 37
As we already mentioned, the Mark-Region is a combination of the existing algorithms 38
In particular, it's a combination of the Mark-Sweep, and the Copying collector. From the first it's got 39
the tracing algorithm: to mark the objects, and eventually to sweep them. From the second it's got the 40
ability to evacuate the objects to different reusable regions, and hence fix the fragmentation. And this 41
ability -- to evacuate to reusable regions instead of reserving the half of the heap, as did the original 42
Copying collector, allows Mark-Region to stay space-efficient. And it achieves this through the heap partitioning 43
In fact, the Generational collector, which we've discussed early in this course, also uses partitioning 44
technique for its generations, and to improve GC performance 45
It also can use different collection algorithms per generation. So the components of the algorithm are 46
rather similar 47
However Mark-Region uses even more granular partitioning. And as we said, one of the modern examples 48
of the Mark-Region is the Immix collector 49
So let's discuss it in detail 50
The Immix was introduced in the paper called: "Immix: A Mark-Region Garbage Collector with Space Efficiency, 51
Fast Collection, and Mutator Performance", so you can get detailed description of this algorithm there as well 52
To understand Immix collector 53
let's first quickly recall how basic Mark-Sweep identifies, and reclaims the garbage 54
So, having the following object graph, we see that only these objects (by chasing the alive pointers) are 55
identified as a life 56
And 57
This is the tracing phase of the Mark-Sweep. All the other objects are the garbage 58
However, to reclaim this garbage, Mark-Sweep has to traverse the whole heap now. Starting from the very 59
beginning of the heap, and up until the end of it 60
It has to consider every single object, which makes the collection cycle slower. So for objects which 61
were identified as alive, it resets the mark-bit (for the future collection cycles) and preserves them 62
If an object wasn't marked, is reclaimed. That is, added to the Free-list, and reused in the next allocation 63
Every. Single. Object. Is checked until it reaches the end of the heap. And once the Sweep phase is down 64
the full collection cycle is completed 65
Now let's see what Immix brings to fix the slower scanning of each object 66
First of all, Immix partitions the heap by the following granularity. It allocates a Block -- a larger 67
chunk of memory, in which it can do the fast Bump-allocation 68
It can either pre-allocate several blocks, or do this on-demand, when a current block is exhausted 69
Further it segregates each block into Lines. Usually the size of a block is 32Kb 70
and the size of a Line is 128 bytes, but -- it's up to implementation. A block can either be Free, that is all 71
its lines are free, which makes the block itself free. It can be a Recyclable block, that is having several 72
free lines, into which objects can still be allocated. Or it can be an Occupied or Used block, which means 73
an Allocator can't place objects there 74
Some of the objects during the lifecycle stay alive, some normally become a garbage 75
So let's see how Immix deals with them 76
We start first with the allocation. Before requesting a full new block, Immix tries to reuse recyclable 77
blocks 78
So let's take for example the Block 2 79
Here we have 4 free lines, into which we can still allocate the objects. To do this 80
Immix uses two cursors: the beginning and the end of the allocation area. And then just applies the fast 81
Bump-allocation in this region. So it allocates the first object, and bumps the pointer. Then it allocates the 82
next object 83
again advancing the pointer -- plain simple. Once the line is occupied, the cursor is moved to the next line 84
and the allocation proceeds there. Immix can also allocate at cross-line boundary 85
For example, if an object is large enough, it can occupy several lines 86
So this is just one object. Sometimes an object can be larger than the space available in the 87
current line 88
In this case Immix has nothing to do but switch to another line 89
unfortunately, leaving this hole of unused memory. That is, it may have this slight fragmentation at the 90
allocation time 91
The good news though, is that this fragmentation will be fixed later at evacuation stage 92
Finally, when all lines in the recyclable block are in use, Immix requests a full new block from the Global Allocator 93
And once the block is available 94
the allocation cursors are just set to the new location, and we can normally proceed allocating objects 95
from there 96
Eventually this block will also be occupied, and a new block will be requested 97
Pretty simple and fast allocation approach 98
Now let's see the collection cycle in action, and start from the marking phase first. As in the simple Mark-Sweep 99
the marking is done during the trace 100
The only difference here is that we're going to mark also a region to which an object belongs to 101
So let's say we have the following graph 102
And starting from the roots, we reach the first object. As was said, in Mark-Region collectors 103
we operate exactly on the regions granularity. And the first region we mark is the line of object 104
If an object is alive, its line is alive as well 105
However this is not the end yet, since we have another region we need to mark for this object -- its block 106
That is, if a line is alive, the block is alive as well 107
The second object belongs to the same line 108
however the line is already marked, so we continue further 109
This object belongs to another line, which is not marked yet. So we mark it, and the block 110
we have already marked 111
Finally, the second root marks the line number 5 112
and at this point the trace is completed. All the other objects are the garbage and will be reclaimed 113
Now let's see at the Sweep phase, and how Immix optimizes it 114
The Sweep phase is much more optimized in Immix than in the basic Mark-Sweep 115
Instead of going through every single object, here we're going to sweep by regions 116
First we consider the block region. If it block was marked as alive (as in the first case), we have to go 117
deeper and consider each line of this block 118
So we go to the first line, which is also alive 119
in this case we reset the mark bit of the line (for the future collection cycles), and continue to the 120
next line 121
Okay 122
this line is also alive, so: reset the mark-bit, and move further. The line number 3 however is not alive 123
which means, none of the objects in this line are alive. So we can reclaim the whole line at once altogether 124
This is where the sweep optimizations already started to come into play with Immix. With the 125
same success 126
we free the next line 127
This line is alive, so we skip it. And finally, we free 128
the last three lines, not touching individual objects inside of those lines 129
Okay, great. 130
we have reclaimed the five lines in the first block, which makes this block now recyclable 131
That is, we'll be able to Bump-allocate 132
the new objects there. However, the Sweep phase is not finished yet 133
we have to consider the second block. And here where the Mark-Region collector again shows a better 134
performance than the basic Mark-Sweep. Since the second block wasn't marked at all 135
this means, neither of its lines is alive. And which means, the whole block can be reclaimed right away 136
without going even into the lines here. In the pseudocode 137
the Sweep phase looks pretty simple 138
We go through each block 139
If it wasn't marked, we just reclaim it 140
Otherwise, we go into each line and to do the same check 141
freeing the line if needed 142
Now there is a slight problem after reclaiming the first block. These holes left after garbage objects 143
since we sweep only by the line granularity, eventually would make the heap fragmented. So the Immix involves 144
the Copying collector into play, and provides the heap defragmentation, evacuating the objects to the 145
free lines 146
Let's take a look. For this Immix determines Source and the Destination blocks, and starts copying 147
the objects. In the original Immix implementation 148
it provides what is called "Opportunistic defragmentation" 149
This means, it moves only those objects which pointers are not exposed to the user code 150
For example, in C# there is a concept of the "Pinned" objects, which cannot be moved 151
In this case Immix keeps them "as is", and other objects can be moved. For simplicity we assume 152
that all of our objects are movable 153
So we start the evacuation to the destination block directly from the roots. To evacuate 154
we just use the same Bump-allocation mechanism 155
So the first object is copied, and as in any moving collector we store the Forwarding address 156
Then we evacuate the second object, store the Forwarding address, and update the pointer. With the same success 157
the third object is copied, and the pointers are updated 158
Finally, we copy the last object, and at this point the evacuation is completed. As we see, all of the objects 159
are now dense-allocated 160
And 161
there is no any fragmentation. The source block can now be fully reclaimed, and we get a new free block 162
here 163
Okay, that was the Mark-Region, and the Immix collector 164
Let's do a quick recap. As we said, the Mark-Region is not a separate algorithm, but rather a combination 165
of the existing basic algorithms 166
In particular, it's a Mark-Sweep, involving the Copying collector for defragmentation, and partitioning 167
the heap into regions. The partitioning can be done in any way 168
However the classic one is to segregate the heap by Blocks and Lines, and that's specifically what Immix does 169
Since the heap is defragmented, Immix can use the fast Bump-allocation, which is as we know faster 170
than the Free-list allocation 171
And finally, what makes Immix faster at the reclamation phase, is the ability to reclaim by the whole 172
regions instead of by individual objects 173
Okay 174
that's it for today, and in the next lectures we'll continue discussing further optimization techniques 175
used to improve GC performance 176
Thanks, and see you in the class