0
$\begingroup$

While learning stack allocation, I came across this paragraph in the textbook (Programming Language Pragmatics - 3rd Edition):

Even in a language without recursion, it can be advantageous to use a stack for local variables, rather than allocating them statically. In most programs the pattern of potential calls among subroutines does not permit all of those subroutines to be active at the same time. As a result, the total space needed for local variables of currently active subroutines is seldom as large as the total space across all subroutines, active or not. A stack may therefore require substantially less memory at run time than would be required for static allocation.

I would appreciate if anyone could explain how stack allocation would save memory when used for allocating local variables. I tried reading this many times. But I can't understand the author meant.

$\endgroup$
1
$\begingroup$

Consider the following program:

f1();
f2();

If local variables are allocated statically, there's a space in memory that's reserved for the local variables of f1, and a separate space for the local variables of f2. If f1 needs $n_1$ bytes of memory for its local variables and f2 needs $n_2$ bytes, the program above needs $n_1 + n_2$ bytes.

If local variables are allocated on a stack, the same stack space is first used for the local variables of f1, then reused for the local variables of f2. The program only needs $\max(f_1, f_2)$ bytes of memory.

With more functions in a program, the amount of static memory grows linerarly with the number of functions and the size of their local variables. The amount of stack memory only grows as fast as the depth of the call chain.

In addition, static allocation does not permit recursion or concurrency: if f1 is already active, you can't invoke it again since the second invocation would overwrite the local variables used by the first invocation. Stack allocation does.

Stack allocation has been standard practice since the very early days of computers.

$\endgroup$
  • $\begingroup$ Thanks! But what about the case where a function calls another function, say f1(){ f2(); } ? I guess there won't be a significant improvement in this case over static allocation. $\endgroup$ – Pranav Dinesh Sep 21 '19 at 11:29
  • $\begingroup$ @PranavDinesh In this case, the cost is the same: $n_1 + n_2$. $\endgroup$ – Gilles 'SO- stop being evil' Sep 21 '19 at 16:45
  • $\begingroup$ @PranavDinesh: However, I think the case of a non-trivial program where there is a chain of nested calls involving every function in the program is pretty rare. $\endgroup$ – rici Sep 22 '19 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.