Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Storage Allocation in Compiler Design
3.
Static Allocation
3.1.
Global Allocation
3.2.
Local Allocation
3.3.
Parameter Allocation
4.
Dynamic Allocation
4.1.
Stack-Based Allocation
4.2.
Heap-Based Allocation
5.
Hybrid Allocation
6.
Memory Management in Storage Allocation Strategies
6.1.
Garbage Collection
6.2.
Fragmentation Management
7.
Challenges in Storage Allocation Strategies
8.
Frequently Asked Questions
8.1.
What is stack-based allocation?
8.2.
What are the different memory allocation strategies?
8.3.
Why heap-based Allocation is slower than stack-based allocation?
8.4.
Why Storage Allocation is important in Compiler Design?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Storage Allocation Strategies in Compiler Design

Author Riya Singh
3 upvotes
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Welcome to Coding Ninjas; Today, we are going to discuss a very important topic in the subject of compiler design, which is Storage Allocation Strategies in Compiler Design.

In this article, we will discuss what storage allocation is; several strategies of storage allocation that are static, stack-based, heap-based, and hybrid allocation, with their advantages, disadvantages, and coding examples. We will also discuss memory management and the challenges in these allocation strategies.

storage allocation strategies in compiler design

Storage Allocation in Compiler Design

In Computer Science, Storage Allocation means a process of assigning memory addresses to different data structures, such as variables, arrays, and objects. Assigning memory locations in a computer’s memory is one of the important tasks that is performed by compilers and operating systems. 

Choosing the right strategies for storage allocation is very important as a strategy can affect the performance of the software of the computer.

There are several storage allocation strategies in compiler design are following:

  1. Static Allocation
  2. Dynamic Allocation
  3. Hybrid Allocation
     

All of these allocations are done automatically by the compiler. We will discuss each of these strategies in detail with examples in the below sections.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Static Allocation

In Static Allocation, All variables that are created will be assigned to memory locations at compile time, and the addresses of these variables will remain the same throughout the program’s execution. As the size of variables does not vary much so this allocation is easy to understand and efficient, but this allocation is not flexible and scalable.

C, C++, and Java support static allocation through the use of the “static” keyword. 

Advantages:

  • Static Allocation is simple and easy to understand.
     
  • As the memory is being allocated at compile time, so there will be no additional time needed in run time.
     
  • Debugging can be easier for developers as the memory is allocated at compile time.
     

Disadvantages:

  • Variables that are dynamic can not be handled using static allocation.
     
  • No Flexibility and Scalability.
     

Here’s an example of static allocation:

int a = 10;
static int b = 1;
const int x = 9;

// In all the above three examples, the memory will be assigned to each of them at the program startup. and the addresses of these variables will remain the same in the memory throughout the lifetime of the program.


In programming, There are several types of variables, such as local variables, global variables, and parameter variables, and the compiler allocates them in memory based on their types. We will discuss all of these in the below subsections.

Global Allocation

It is a type of allocation that comes under static allocation, where the memory is allocated to the global variables. Global Variables are the variables that are declared outside of any function and can be accessed in the program from any block of the code. A block of memory is allocated to the global variables in the static memory.

Here’s an example of global allocation in C++:

#include<iostream>
using namespace std;

int x = 5;
void func() {
     print(x);
}

int main() {
     print(x);
     return 0;
}

// Here ‘x’ is a global variable that can be accessed from any block of code, and the memory is allocated for ‘x’ in static memory.

Local Allocation

It is a type of allocation that comes under static allocation, where the memory is allocated to the local variables. Global Variables are the variables that are declared in a function, and their lifetime and scope are limited to that function means they can only be accessed within the function. A block of memory is allocated to the local variables in either static memory or stack memory.

Here’s an example of local allocation in C++:

void func() {
     int x = 5;
     print(x);
}

// Here ‘x’ is a local variable that can only be accessed within the function ‘func’, and the memory is allocated for ‘x’ in static memory or stack memory.

Parameter Allocation

It is a type of allocation that comes under static allocation, where the memory is allocated to the parameters. Parameters are the variables that are passed to the functions and can be accessed in the function it passed. A block of memory is allocated to the global variables in the stack memory.

Here’s an example of parameter allocation in C++:

void func(int x) {
     print(x);
}

// Here ‘x’ is a parameter that is passed to the function ‘func’ and can only be accessed within the ‘func’, and the memory is allocated for ‘x’ in stack memory.

Dynamic Allocation

Dynamic Allocation is a type of Storage Strategies in Compiler Design where the memory is allocated to the data structures at run-time, not at compile-time. A data structure can be allocated in memory depending on the program’s need and can be allocated and deallocated at the program’s execution.

In Dynamic Allocation, we have further two allocation strategies, are Stack-Based Allocation and Heap-Based Allocation, explained below:

Stack-Based Allocation

In Stack-Based Allocation, A fixed-sized stack data structure is allocated to a memory location during the run-time execution. A variable is assigned a memory location on the stack when they are declared and can be freed when the variable’s scope goes out.

C and C++ both support the stack-based allocation through the variables declared in the functions, or Standard Library functions can be used, such as “alloca()” and “alloca_array()”.

Advantages:

  • The process of assigning the memory locations is fast.
     
  • Memory Deallocation is also fast in stack-based allocation.
     
  • Function calls can be efficient using stack-based allocation.
     

Disadvantages:

  • The amount of memory is limited for stack-based allocation.
     
  • As the size of the stack is limited, issues like stack overflow can happen.
     

Here’s an example of stack-based allocation:

void fun(int a, int b) {
	int c = a + b;
	print(c);
}

/*
	Whenever the function gets called, a memory location will be assigned to the variable ‘c’ on the stack.
*/

Heap-Based Allocation

In Heap-Based Allocation, Variables that are created and memory will be dynamically allocated in memory (heap) at run-time execution. The variables that use heap-based allocation are generally known as dynamic variables that can be changed anytime during the run-time.

C and C++ both support heap-based allocation, and dynamic data structures can be created using functions like. “malloc()”, “calloc()”, “realloc()”, or “new” keywords.

Java also supports heap-based allocation through the use of new keywords.

Advantages:

  • Dynamic Data Structures can be handled by heap-based allocation.
     
  • Heap-Based Allocation gives more flexibility to a data structure.
     
  • It can also handle large amounts of memory as compared to stack-based allocation.
     

Disadvantages:

  • Heap-Based Allocation is slower than Stack-Based in terms of speed.
     
  • Risk of memory leaks.
     

Here’s an example of heap-based allocation:

int* arr1 = (int* malloc(5 * sizeof(int)));
int* arr1 = new int[5];

/*
In both these examples, the memory will be assigned to each of them at the program startup. and the memory locations will be assigned to both variables ‘arr1’ and ‘arr2’ in the memory pool of the heap.
*/

Hybrid Allocation

This is a type of allocation strategy that is used to achieve multiple memory allocation. A compiler can use static memory allocation for global variables and heap memory allocation for dynamic data structures.

Advantages:

  • The benefits of stack-based allocation and heap-based allocation can be taken.
     
  • Hybrid Allocation is more efficient than any other allocation alone.
     
  • The performance of the program gets better than static allocation and dynamic allocation.
     

Disadvantages:

  • As Hybrid allocation is a sort of combination of allocations, It is more complex.
     
  • Hybrid allocation can be difficult for developers to debug the code.
     

Here’s an example of hybrid allocation:

int x;
void func() {
     int a = 2;
     print(a);
}

int *arr = (int*) malloc(5 * sizeof(int));

/*
‘x’ is a global variable that will be allocated in memory statically.
‘a’ is a local variable with value 2 in a function that will be allocated by stack-based allocation.
‘arr’ is an array of 5, which will be allocated by heap-based allocation.
*/

Memory Management in Storage Allocation Strategies

Managing Memory while allocating and deallocating the data structures is a very important task for a computer. If the memory is managed efficiently, Issues like. memory leaks, fragmentation, and overallocation can be created.

There are two aspects of compilers that help in memory management, Garbage Collection and Fragmentation Management, and both of these are explained below.

Garbage Collection

In Garbage Collection, Compilers automatically handle the process of allocation and deallocation using the techniques such as reference counting or mark-and-sweep algorithms. In programming, garbage collection is done automatically on the variables when they are unused, unreferenced, or the variables with no values.

High-Level Programming Languages support garbage collection, such as Python, C#, and Java.

Advantages:

  • Garbage Collection improves the efficiency of the program.
     
  • The computer gets more memory to use.
     
  • Dynamic Data Structures or variables are allowed.
     

Disadvantages:

  • While executing the program, delays or pauses can happen.
     
  • Garbage Collection is slower than stack-based allocation.
     

Here’s an example of Garbage Collection in Java:

List<int>* list = new List<int>();
list->Add(5);
delete list;

/*
‘list’ is created using the ‘new’ keyword, which is empty initially, but we added one element 5 to this ‘list’, and ‘list’ is deleted using the ‘delete’ keyword, 	which is an example of garbage collection, where a memory will be deallocated automatically when ‘list’ is no longer needed.
*/

Fragmentation Management

Fragmentation Management is one of the aspects that affect the performance of the program in terms of speed and efficiency. In fragmentation, the memory divides into smaller parts, and these sections can not be used. Issues like these can create when allocation and deallocation are done at run-time.

But If the data structures are allocated statically, problems like fragmentation will not arise.

We have some techniques by which we can reduce the fragmentation. 

First Technique is to move the allocated memory blocks that will free up the space in memory. This free space can be used for the allocation and deallocation of the next data structures. Even though moving allocated memory blocks will help us to reduce the fragmentation, this approach is complex and time-consuming, which will ultimately affect the performance. 

The second Technique can use the memory pooling approach, where a pre-allocated block of memory will be provided, and this block of memory can be used later for allocating new data structures. This approach will help us to reduce fragmentation and will not affect the performance of the program.

Challenges in Storage Allocation Strategies

Several challenges in storage allocation strategies can affect the performance of the program. There are two significant challenges are discussed below:

  1. Overhead: It is a limitation that can arise where processing time and memory usage required to manage allocations and deallocations are extra. Depending on the allocation strategies, they have different levels of overhead. The stack-based allocation has a low overhead. The heap-based allocation has a higher overhead. Overhead mostly occurs during the execution when the memory is to be allocated at run-time.
     
  2. Memory Usage: This is also one of the challenges encountered when the allocation and deallocation are done with the wrong amount of memory blocks to the data structures. Depending on the allocation strategies, different strategies have different limits on the amount of memory. As the size of the stack is limited, the stack-based allocation has a limit very limited.

If the right storage allocation strategies are chosen, the issues such as memory leaks, fragmentation, and overallocation can be reduced, and the performance of the program can be increased.

Frequently Asked Questions

What is stack-based allocation?

In Stack-Based Allocation, A fixed-sized stack data structure is allocated to a memory location during the run-time execution. A variable is assigned a memory location on the stack when they are declared and can be freed when the variable’s scope goes out.

What are the different memory allocation strategies?

The primary role of the memory management system is to satisfy requests for memory allocation. At other times, processes explicitly request memory. Either way, the system must locate enough unallocated memory and assign it to the process. Memory allocation strategies include stack, heap, and global/static.

Why heap-based Allocation is slower than stack-based allocation?

In Heap-Based Allocation, the data structure is created dynamically so that it is allocated in memory at the run-time, which means the data of the data structure can be changed anytime. This means more time will be taken to update the data in a memory location, which slows the execution time in heap-based allocation.

Why Storage Allocation is important in Compiler Design?

By doing storage allocation, we can determine how a program utilizes memory (if it's efficient or inefficient); assigning memory locations in a computer’s memory is one of the important tasks that is performed by compilers and operating systems.

Conclusion

Storage Allocation is a process of assigning memory addresses to different data structures, such as variables, arrays, and objects. This article was all about the Storage Allocation Strategies in Compiler Design, where we discussed what storage allocation is and several strategies of storage allocation that are used by the compiler automatically with their examples. We also discussed memory management and the challenges in these allocation strategies.

I will recommend you read about the Basic Blocks in Compiler Design, Basic Blocks in Compiler Design, and Lexical Analysis in Compiler Designby clicking here; this will grow your understanding of Compiler Design.

Do check out The Interview Guide for Product Based Companies, as well as some of the Popular Interview Problems from Top companies like AmazonAdobeGoogleUberMicrosoft, etc., on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMS, and System Design, etc. as well as some Contests, Test SeriesInterview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Live masterclass