Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Manual memory management
3.
Automatic memory management
4.
Frequently Asked Questions
4.1.
What is garbage collector?
4.2.
What malloc() returns?
5.
Conclusion
Last Updated: Mar 27, 2024

Heap Allocation

Author Malay Gain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Compiler Design

Introduction

The limitations of stack allocation and static allocation are often too restricting: You might want arrays that can be resized or which survive the function invocation in which they are allocated. Hence, most modern languages allow heap allocation, which is also called dynamic memory allocation. Data that is heap-allocated stays allocated until the program execution ends, until the data is explicitly deallocated by a program statement, or until the data is deemed dead by a run-time memory-management system, which then deallocates it.

 

The size of the array (or other data) need not be known until it is allocated, and if the size needs to be increased later, a new array can be allocated, and references to the old array can be redirected to point to the new array. The latter requires that all references to the old array can be tracked down and updated, but that can be arranged, for example, by letting all references to an array go through an indirection node that is never moved. 

 

Languages that use heap allocation can be classified by how data is deallocated: Explicitly by commands in the program or automatically by the run-time memory management system. The first is called “manual memory management” and the latter “automatic memory management” or “automatic garbage collection”.

 Let’s look into both of these in more detail below.

Also See, Top Down Parsing

Manual memory management

Manual memory management means that both allocation and deallocation of heap-allocated objects (arrays etc.) are explicit in the code. In C, this is done using the library functions malloc() and free().

 

Suppose we have called malloc(100) to allocate 100 bytes of memory. malloc will see that the (single) chunk of memory is free, but much larger than the requested size. So, it will split it into one chunk of 100 bytes and one larger chunk with the remaining space. This is achieved by simply writing a new chunk header into the data area after 100 bytes and  then connecting them together into a linked list: 

Manual Memory Management

 

It is possible to get allocation (malloc() time down to logarithmic in the size of memory. Freeing (free()) can be made at constant time, but external fragmentation can be very bad, so it is more common to make free() join blocks to reduce external fragmentation. With such joining, the time for a call to free() also becomes logarithmic in the size of memory. 

 

Manual memory management has two serious problems: 

 

  • Manually inserting calls to free() in the program is error-prone and a common source of errors. If memory is used after it is erroneously freed, the results can be unpredictable and compromise the security of a software system. If memory is not freed or freed too late, the amount of in-use memory can increase, which is called a space leak. 

 

  • The available memory can, over time, be split into a large number of small blocks. This is called (external) fragmentation. 

 

Space leaks and fragmentation can be quite serious in systems that run for a long time, such as telephone exchange systems.

 

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

Automatic memory management

Because manual memory management is error-prone, many modern languages support automatic memory management, also called garbage collection.

 

With automatic memory management, heap allocation is still done in the same way as with manual memory management: By calling malloc() or invoking an object constructor. But the programmer does not need to call free() or object destructors: It is up to the compiler to generate code that frees memory. This is typically not done only by making the compiler insert calls to free() in the generated code, as finding the right places to do so requires a very complicated analysis of the whole program.

 

Automatic memory management needs to distinguish heap-pointers from other values. This can be done by using type information or by having non-overlapping representations of pointers and non-pointers. Newly allocated blocks must be initialised, so they contain no spurious pointers.

 

There are two types of automatic memory management: Reference counting and tracing garbage collection.

 

Reference counting keeps in every block a count of incoming pointers, so adding or removing pointers to a block requires an update of its counter. Reference counting can not (without assistance) collect circular data structures, but it mostly avoids the long pauses that (non-concurrent) tracing collectors can cause.

 

tracing garbage collector determines which blocks are reachable from variables in the program and frees all other blocks, as these can never be accessed by the program. Reachability can handle cycles, so tracing collectors (unlike reference counting) have no problem with circular data structures. A tracing collector maintains an invariant during the reachability analysis by classifying all nodes (blocks and roots) in three categories represented by three colours - white, grey, and black.

You can also read about the memory hierarchy.

Frequently Asked Questions

What is garbage collector?

A garbage collector is a component of the garbage collection system that performs automatic memory management and freeing up memory that is not in use. Its job is to free any unused memory and ensure that no memory is freed while it is still in use.

What malloc() returns?

malloc returns a void pointer to the allocated space or NULL if there is insufficient memory available. To return a pointer to a type other than void, use a type cast on the return value.

 

Conclusion

This article covered heap allocation or heap management.
 Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning!
 

Previous article
Stack Allocation
Next article
Next Use Information in Compiler Design
Live masterclass