Garbage Collection in Modern Languages | Memory Allocation

This is the second part of Garbage Collector Series.

There are mainly three allocation types in any programming language:

• Static Allocation
• Stack Allocation
• Heap Allocation

Static Allocation Type: Static allocation type is around since 1950’s. This is the fastest way to allocate variables as the static allocations are carried out during compile time of a program.

Since Static Allocation happens at the compile time, it only supports fixed size data structures as our compiler has to deduce the data structure at compile time and allocate memory accordingly. This mechanism can also be a drawback of Static allocation since we can’t use data structures that grow during run time (eg. Lists, Graphs, etc.)

Also, due to the fixed-size restriction, recursion is not ideal for static data types as it results in overriding the previous values in every recursion step. (More about Static types can be found here.)

Stack Allocation Type: Some of the limitations in Static Allocation type can be eliminated with Stack Allocations. Stack allocation uses the concept of stack frames (also known as activation records) to store data into continuous chunks of memory. Every-time a function is called (including recursive functions which is supported in stack allocation) a new stack frame is allocated and pushed back into the stack. When the function is returned, stack frame is deallocated and necessary book-keeping is carried out.

In lower-level languages like x86-assembly we have to take care of stack and stack pointers(pointers pointing to the newly created stack). But with the introduction of higher-level languages such as C, C++, Java; the stack allocation is carried out automatically with every function call.

Hold your horses!, Do we get rid of the Fixed-size data structures issue with Stack allocated types? NO!

The compiler still has to know the size of data structure at compile time!! but Why? I will write a separate article to cover that. But as of now, just remember that the compiler needs the size of underlying data structure during stack allocation.

Moreover, there is one major issue with Stack allocated types. When the runtime allocation is introduced, robustness of Stacks decrease due to the Stack Overflow probability. And this happens to be one of the major concerns with stack allocated types.

Heap Allocated Type: The issues raised by Static and Stack allocated types can be somewhat addressed using Heap allocated type objects (Yes! Heap allocated objects are slower, we will address that in a different article).

One of the primary benefits of using Heap allocated objects is that we can allocate a chunk of memory of any size and return a pointer to the caller from a callee (The pointer returned is of type void*, which can be further casted into a data type by the caller). The advantage of heap allocation is consumption of memory space on demand. We will discuss the memory model of a process in next article and discuss how heap differs from other two types.

Due to the benefit of consuming memory space on demand, we get the flexibility of having variable type data structures that can grow during the run-time of a program (Compile time information of data structure size is not needed).

Heap allocated type also provide protection (not always) from the stack overflow issue, as the heap memory is considerably larger in size than the stack memory (generally 1MB-8MB of stack memory). The extra memory space comes at the cost of speed, stack allocation is much faster than the heap allocation. Also, there are few major issues with the heap allocated memory as discussed below.

The benefit of (almost) infinite memory space of heap allocation comes with the cost of responsibility. We must take ownership of the heap allocated objects and properly discard them by freeing up the memory space it is currently using. This leads us to the discussion of memory management where heap allocated objects when not used properly result in two issues:

• Memory Leaks: Forget to free the memory
• Dangling Pointers: Freeing memory too early

In the next article we will dive deep in these issues and discuss possible solutions in more detail.

Thank you for reading.