Welcome to the first session of the garbage collectors class where we discuss techniques for the automatic 1
memory management. 2
Before we dive into garbage collection algorithms we shall see different allocation types used in programming 3
languages. 4
Most of the languages today provide Static, Stack, and Heap allocations. 5
Let's briefly discuss features, and pros and cons of each allocation type, and see also where the garbage 6
collector fits here. 7
The Static allocation is the simplest allocation type, and was supported since early 50th starting in 8
Fortran programming language. All memory was allocated at compile time, and all variables where statically 9
bound to initial memory locations. As a direct consequence from this 10
the programs with the Static allocation were the most robust: no runtime allocations -- no memory issues. 11
The execution was also very fast 12
since there is no any memory mechanism involved to manage at runtime. Compiler could even emit direct 13
memory addresses, excluding intermediate step, going from a variable name to memory location. 14
However, being robust and fast, the Static allocation has also noticeable disadvantages. 15
First of all, the sizes of all data structures should be known at compile time. 16
This means we can only use a fixed-length arrays, no linked lists, trees, and similar dynamic data structures. 17
And secondly, and more importantly: even though Function abstraction was supported, it was not possible 18
to do recursive calls. Every consequent invocation of the same function would overwrite the values of 19
the local variables and parameters. To fix this 20
the concept of the Stack was introduced. The Stack abstraction introduced also in 50th in Algol programming 21
language allowed implementing recursive functions, through the mechanism of the Stack frames 22
(also known as the Activation records) 23
Every time a function is called, even if recursively, a Stack frame is allocated, and pushed onto 24
the stack. When a function returns, the stack frame is deallocated. 25
This allowed also passing parameters of different types, resulting just in two different Stack frame sizes. 26
In higher programming languages, starting from C, the stack memory is fully automatic. As programmers, we 27
do not worry about explicit allocation of the stack frames. 28
We simply call functions, and the stack frames are automatically pushed to store arguments and local 29
variables, and popped, removing all the temporary data, when the function returns. In lower-level languages 30
such as Assembly, the stack frames are usually controlled manually through the Stack pointer and 31
the Base pointer registers. 32
Once we have introduced dynamic memory allocation, even though fully automatic such as the Stack, the 33
robustness of our programs reduced dramatically. The well-known Stack Overflow issue 34
even today indicates the problems in the program logic. 35
In addition, the sizes of the data structures still should be known at compile time. 36
This was a limitation for the Factory or Constructor functions, which create objects by allocating memory 37
and returning it from the Callee to a Caller. To support this use case 38
the Heap allocation was introduced. With the heap memory 39
we've got this ability to allocate any chunk of memory of needed size, and return a pointer to it 40
from a Callee back to a Caller. That is, in contrast with the stack 41
we don't have the requirements for the allocation and deallocation order. 42
The direct advantages of the heap allocation include of course the variable size 43
data structures, where the size is not required to be known at compile time. 44
Now, another advantage of using the heap allocation might be avoiding the Stack Overflow issue. 45
Consider this example of a recursive function. 46
It allocates some local variables for own purposes: one is allocated on the stack, the other one is allocated 47
on the heap. And if the size of the Node structure is large 48
this recursion can quickly cause the Stack Overflow issue due to a lot of stack allocations. While in 49
the second case, where we allocate this object on the heap 50
the recursion might be much deeper. In contrast with the Static and the Stack allocations which are completely 51
automatic 52
the management of the heap memory became a user problem. And this quickly resulted to real problems producing 53
the well-known Memory Leaks and the Dangling pointer issues. 54
So, in the next video we're going to discuss these manual memory issues in detail, identify their root 55
cause and eventually will design the solutions in form of the automatic memory management known as the 56
garbage collection.