From an interview: what's the benefit of the stack in C?

Question

I was asked about heap and stack memory structure in an interview. The guy asked me what's the benefit of having the stack? I wasn't sure what he was getting at. What others ways are there to set up address space to execute a c program?

Answer 1

The benefit of the stack is that it allows recursion, both direct and indirect. In stackless languages (like Fortran), each function's local variables are globally allocated, so if you call a function twice without returning from it, you clobber your return address and you're in trouble. Additionally, Fortran's allocation of memory to each procedure is not very efficient if you'll only be using some of them at a given time.

The benefit of the stack over a heap is, as Murali pointed out, more efficient allocation and deallocation. Technically, the stack can refer to either the conceptual dynamic (call) stack or its section of memory, so languages can have a call stack that is allocated in dynamic heap space, which might make it easier to implement coroutines, continuations, and closures.

Answer 2

I just did a quick search on my C specification and word "stack" appears exactly 0 times. As you might expect, the existence of a stack is an implementation choice. I've never heard of an implementation that didn't have a stack, mind you. Using a stack is just the easiest way to use & reuse space for variables with automatic storage duration, I guess.

Your compiler could just as easily allocate global space for every automatic variable in your program if it wanted to, but it would increase your memory footprint pretty quickly. It would probably cause you some hiccups if you had a recursive function, too.

Answer 3

The question could have referred to a few things. He might have been referring to the call stack, the "stack" stack (i.e. where parameters and local variables are stored), or generically, the data structure.

The call stack is extremely useful because it allows one to trace the execution of a program. Contrast this with early computing, where everything was a jump instruction or goto statement for "higher" level languages. You had to know from where your "routine" was invoked so that you could return control to it, as well as agree on a standard means of passing arguments between them. In contrast, you can now pop the stack and return control of the application to the previous caller without knowledge of who that caller is.

The advantages/benefits to using the stack for local variables is numerous. Let's say the compiler determined a specific slice of memory for local variable use (as is the case in C for a static local variable). If you were to call your function again recursively, you would not have separate space in RAM for the local variables and you would overwrite your local variables from the caller. The only other way to accomplish this would be to dynamically allocate RAM as needed for each call, at significant performance penalty.

Stacks in general are a useful means to handle first in, last out forms of data. In contrast to a queue (FIFO), a stack means you can handle the most recent data first while leaving old data last.

Answer 4

I've seen some helpful answers here.

My twopennyworth:

• A stack is an implementation decision so not part of C.
• CPUs have stack instructions built in, which makes for efficient stack use.
• Calling a subroutine starts a stack frame which holds the calling parameters and subroutine's local variables. These can now be addressed as small offsets from a Stack Pointer register on the CPU.
• Similarly, nested calls build more stack on the stack, allowing good management of variable and parameter scope.
• Garbage collection is simplified. Just returning from the routine/function puts the previous frame address into the Stack Pointer and the unwanted stack frame effectively disappears.
• Heaps are great for dynamic data storage, but each variable must be referenced by its own pointer and its creation and destruction (garbage collection) has more overhead.