Heap Allocation

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: 

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.