automatic memory allocation

Question

Global variables are given fixed addresses in main memory by the C compiler, called static memory allocation. Function local variables are created on the stack, this is called automatic memory allocation.

Why is it done this way?

Answer 1

There are three types of memory in C: static (global variables), automatic (stack) and dynamic (heap). All three are needed to express programs conveniently and efficiently.

Why static memory is necessary

Why you can't have just automatic and dynamic memory: It's mostly possible — after all, a local variable in main is almost as good as a global variable. (The heap is no good for global variables because there's no way to get a name for a part of the heap, only a name for a pointer to a part of the heap.) However, there are a few reasons why this would be inconvenient:

• Language design: sometimes it's convenient to access the same data from multiple places in a program without having to pass a variable via function arguments. Global variables allow this. With a variable in main, you'd have to pass its address through all function calls.
• Language design: global variables are available in atexit-registered functions which perform cleanup after main returns.
• Language design, with multiple threads: static variables are shared between threads. If they're on the stack of a particular thread, you'd have to keep that stack in memory even if the thread exits.
• Memory optimization: the initial values of variables have to be stored somewhere when the program starts. You might as well use the same memory if the variables are modified.
• Safety of memory management: the size of the stack is typically limited for several reasons, including keeping the memory usage reasonable when there are many threads. By making global variables a separate thing, you don't need to take them into account when calculating the stack size of the initial thread.

Why automatic memory is necessary

Why you can't have just static and dynamic memory: where do you put the local variables of a function? Some very early programming languages reserved an area in memory for every function. This had a lot of limitations, so most languages adopted the concept of stack for a function's local variables. If each function has a dedicated memory area:

• If there are a lot of functions in the program, then at any given time, most of the functions are not being called, so their memory is not used. This wastes a lot of memory. The compiler might be able to optimize, e.g. if it sees that f1 never calls (directly or indirectly) f2 and vice versa then f1 and f2 can use the same memory area. But it's rarely possible to guarantee this kind of exclusion.
• A function may never call itself directly or indirectly, i.e. no recursion is possible. Recursive function calls are not that common in C programs, but they are possible, and some algorithms are essentially impossible to implement without using or faking recursion (it's of course possible to avoid recursion by managing your own stack when you need one, but it's inconvenient).

Using dynamic memory for the local variables of a function wouldn't be possible because you can't give a name to a part of the heap: you'd have to access everything through pointers — which themselves couldn't have names, so the only possible names would be global variables. That includes a function's arguments: functions could not have arguments, so you'd need to pass data through global variables, which has the same problems as using static memory to implement local storage for functions that I explained just above.

Why heap memory is necessary

With automatic memory, you have to declare how much memory a piece of code is going to use before calling that code. In particular, a memory allocation can never travel upwards: you can't have a function allocating memory that its caller can then use. This is extremely restrictive. It turns the language into a Turing tarpit: it's technically possible to implement algorithms that require an amount of storage that can't be calculated at the beginning, but you have to basically try, and if you run out of memory, try again from scratch with more memory.

Answer 2

Because functions can be recursive.
Since a function may call itself (in)directly, the compiler needs to ensure that the nested invocation gets its own variables. And the stack is the most simple solution for that.

As a matter of fact, early FORTRAN did not allow for recursive functions. And guess what, that allowed the compiler to statically allocate memory for all functions. You don't see this requirement in modern languages because not having recursive functions is a price most programmers are not prepared to pay.

Answer 3

Global variables exist as unique instances, which are known at program compilation and can be preallocated some space.

Local variables are only needed if the functions are called. So

• they are not allocated in advance,

• if there are recursive calls or mutually recursive calls (A calls B and B calls A), there can be several instances of the same variables existing at the same time. The stack implements a convenient mechanism to allocate these instances. This must be done dynamically, as it is not possible to predict program execution.

You will soon learn that there is another form of dynamic allocation, which is managed explicitly by the programmer, in a memory zone called the heap. It provides maximum flexibility to allocate space of a size and layout not known in advance.