There are two types of memory available to a program running in a computer, the
stack memory and
heap memory. The operating system allocates a fixed amount of stack memory to a running program, and the heap is extra memory that may be utilized by the program if required. This is especially important to know when using a low-level language like C.
The stack is a
Last In First Out (LIFO) data structure. Items can only be inserted and removed from one end. The insert action is a
push, and the remove action is a
pop. To access an item, all other items on top of it have to be popped from the stack.
To examine this, let's consider the following C program.
#include <stdio.h>
int add(int a, int b)
{
return a+b;
}
int main()
{
int x = 1;
int y = 2;
int sum = add(x, y);
printf("The sum of %d and %d is %d\n", x, y, sum);
return 0;
}
The program above calls a function
add to find the sum of two integers. The variables in the
main function, that is
x and
y, are pushed onto the stack. When the
add function is called, the address of the instruction after the function call is pushed onto the stack, and the execution jumps to the first instruction in
add. Variables local to the add function,
a and
b are also pushed onto the stack.
When the function exits, all variables local to it are popped from the stack, and are replaced by its return value, which is then assigned to the variable sum. The execution is able to continue from where it left off in the main function, since the address of the instruction to execute which had been pushed onto the stack earlier is popped off and execution continues from this address. Here, we've only discussed a high level description of what happens, actual mechanics involved will be illustrated in a later post.
Since the stack size allocated to the program is of a fixed size, there is a limit to the size of variables, and the number of nested function calls that can occur in a program. When the stack becomes full, a condition known as
stack overflow occurs and the program crashes. This may happen if one allocates a very large array, or implements a function that recursively calls itself too many times (deep recursion). The case for deep recursion is illustrated by the following C program.
#include <stdio.h>
#define MAX 1000000000 /*maximum number of times to recurse*/
int recurse(int c)
{
printf("level %d, ", c);
if (c < MAX)
recurse(++c);
}
int main()
{
recurse(1);
return 0;
}
By experimenting with the constant
MAX, one can control the number of times that the function
recurse calls itself.
When there's need to create a large variable, memory from the heap can be used. Stack memory management is automatically handled by the operating system, but memory from the heap has to be manually allocated and freed by the programmer. In C, the functions
malloc and
free from header file
stdlib.h are used for this, as the following snippet demonstrates.
#include <stdlib.h>
...
int *ptr = (int*)malloc(sizeof(int) * 1000000); /*allocate memory for 1000000 integers*/
...
free(ptr); /*free the previously allocated memory*/
...
The programmer, however, has to be careful to free all memory manually allocated by the heap to make it available to other programs. Otherwise a
memory leak occurs, where available memory in the computer decreases to an insufficient level.
The deep recursion problem can be solved by devising an iterative program, i.e. using a loop construct, instead of calling a function recursively, for some repeated computation. The technique, known as
recursion removal, will be discussed in a later post.
