Welcome back. 1
Before discussing algorithms of collecting the garbage we need to see how this objects which eventually 2
become a garbage are allocated on the heap. 3
In today's lecture we consider mechanisms of memory allocation. 4
This is also a lab session where you will be implementing a memory allocator similar to the one used 5
in `malloc` function. 6
Please address the following URL to find a detailed description of the topic and the lab assignments. 7
In addition we discussed the theory behind the allocators talking about Sequential, also known as the 8
Bump-allocators, and the Free-List allocators. From the previous lecture about the memory layout 9
we remember that to allocate the memory from an operating system means to map more memory for this 10
process. 11
So the heap is located in this region, and as we see grows upwards, towards the higher addresses. And 12
the area in between of the stack and the heap is known as the Unmapped area. Mapping is controlled by 13
the position of the Program break. And to control the position of the break pointer, we can use several 14
system calls. 15
Let's focus on the heap area specifically and call it abstractly just Free instead of Unmapped. And 16
let's display it horizontally, so we can allocate more objects in our examples. 17
Let's also use the abstract Alloc pointer instead of the brk pointer there, which is specific for operating 18
system, showing that here we focus mainly on the theoretical aspects and the generic algorithms. 19
Okay. 20
And now let's allocate an object graph on this heap. 21
So, we allocate object A pointed by the Root. And a root is a known reachable reference such as a variable 22
or a register. From a user code perspective 23
it may look like this 24
So, we allocated the object A and assigned it to the Root variable. 25
Then we allocate the object B, pointed from A. We allocate the object C, pointed 26
let's say, also from A. 27
Then the object D, pointed from B. And 28
finally, the object E, pointed from C. And then, let's say, at some point we have lost the connection from 29
A to B object, here. 30
This makes the object B, as well as its direct child 31
the object D, unreachable, from the root. And they become good candidates for the garbage collection. 32
But yet let's continue allocating the objects. So we allocate the next object 33
F and, as previously, just bumping the allocation pointer. Such allocation strategy is known as the Sequential 34
allocation or the "Bump"-allocation. 35
What this means, we don't try to reuse right the way any of the existing free blocks, such as B or D, and 36
just continue bumping the allocation pointer further. Running forward 37
we should say, that not every system allows using the Bump-allocator, since usually it assumes relocating 38
objects around on the collection cycle. 39
The main advantages of the bump allocation is that is really fast, similar to the stack allocation. 40
However, as we said, systems which expose the pointer semantics, such as C or C++, cannot simply reallocate 41
the objects around and have to reuse previously freed blocks. 42
So let's take a look at this example. 43
So if we need to reuse the free blocks right away we need to add them to what is known as the Free list. 44
That is, the linked list of all available blocks on the heap. 45
Then, when we receive a request to allocate an object F, the Free-List allocator has to search for a block 46
of a suitable size, traversing this Free list. Once the block is found, it's reused again. 47
Such allocation is known as the Free-List allocation. 48
The Free-List allocation is usually slower than the Bump-allocator due to searching overhead. 49
However, there are some optimizations which allow speeding up the search. So to state it in one sentence: 50
The Sequential allocator just increases the allocation pointer, leaving in the garbage behind. A pool 51
allocator is an example of such sequential allocation. And the Free-List allocator has to track the 52
free blocks in a list-like data structure and reuse them. 53
Since implementing a sequential allocator is trivial: we just track the allocation and the end of the 54
heap pointers 55
let's focus on the different algorithms related to the Free-List allocation. 56
Now, there are several strategies how the Free-List search can be implemented. 57
These are: First-fit, Next-fit, Best-fit, and Segregated fit. 58
Let's quickly see the specifics of each of the algorithms and again in the lab assignments you're going 59
to implement all of them. 60
The First-fit strategy and just finds the first block which fits the size. And the Free list is updated 61
accordingly. 62
In addition if a found look is larger than the requested, we can optionally split the block tracking 63
only the chunk of a needed size. 64
Let's take a look at the example from the lab session. So, we traverse all the blocks, starting at the 65
beginning position. And if the size of the analyzing block doesn't fit, we just go to the next block. 66
Otherwise, we return found block, and it can be reused. If nothing is found 67
we return the null-pointer, and this is the sign that we have to request more memory from the operating 68
system. 69
Okay, let's see now at the improvement of the First-fit, known as the Next-fit search. The Next-fit allocation 70
is a variation of the First-fit, but starts the search from the previous successful position. 71
This allows skipping smaller blocks located at the beginning of the heap, and allocating the needed blocks 72
faster. 73
So in this example when we found this block, and then receive a similar request, we start from the 74
previous successful position, skipping traversal of all the blocks at the beginning. When we reached the 75
end of the heap 76
we start over until we reach the start position. 77
So, sometimes the strategy is called Circular First-fit allocation. The implementation of the Next-fit 78
algorithm is left to you as an assignment. 79
So please find the details in the appropriate lab session. 80
Finally, the Best-fit strategy allows us locating a block which size fits the best. 81
Let's say, this block is of size 8, this one is 64, and this one is 16. And we receive a request for 16 bytes. 82
The First- and Next- strategies would return 83
the second block (potentially splitting it), while the Best-fit returns the third block, which fits the best 84
and doesn't require splitting the block, wasting resources and time. 85
Okay, now let's see at the most optimized searching algorithm used in many production allocators. 86
The approach is known as the Segregated list. 87
The problem with the previous strategies we discussed, is that they require traversing the blocks of 88
different sizes, until we find a block of a requested size. This can dramatically slow down the search 89
for blocks of predefined sizes. 90
The idea of the Segregated list is to partition the heap, and group the allocating blocks by size. 91
Then, when we receive a request, say, for 16 bytes, we directly jump to the second bucket and allocate 92
from there. 93
That is, instead of one Free list, we just have multiple Free lists, but each list contains blocks only 94
of a certain size. 95
Okay. 96
Let's do a quick recap of the allocation topic. 97
As we said, there are two major allocation types. 98
The Sequential, that is the Bump-allocator. And the Free-List allocator. The sequential allocator 99
is simple and fast, similar to the stack allocation. 100
However it implies relocating the objects around, which might not be possible if a language exposes the 101
pointer semantics. 102
The Sequential allocator is used by the Mark-Compact, Copying, and Generational collectors, as we will 103
see further in this class. The Free-List allocator has to reuse the freed blocks. 104
And for this it tracks them in a list-like data structure. 105
We also said, there are several strategies for searching these free blocks. 106
These are First-fit, Next-fit, Best-fit, and the Segregated fit. And the Free-List allocator is used in 107
systems with Mark-Sweep, and the Reference counting garbage collectors. And also in system with manual 108
memory management. Now when we know how to allocate objects let's move forward and see how these objects 109
become a garbage. 110
We start the discussion with considering two types of the garbage known as Semantic and Syntactic garbage 111
and which will be discussing in the next video.