CODEWITHSUNDEEP
c++memorystackheap-memorycallstack
Nika Kurashvili
Nika Kurashvili

Reputation: 6462

what's the difference between callstack and stack?

I think I might be asking a very wrong question, but I really tried to understand it by googling, but with no luck.

As we know, we have a stack and heap. Heap for the dynamically allocated ones, stack for local variables and e.t.c.

Let's say I have the following c++ code.

void bla(int v1, int v2, int v3) {
    int g = v1 + v2+ v3;
}

void nice(int g){
    int z = 20;
    int k = 30;
    bla(g, z, k);
}

int main(){
    cout<<"Hello World";
    nice(40);
}

Now, let's imagine there's a stack. I understand that for example values z,k,g will be stored on stack. But when I call the function nice which calls bla where are those stored ? I've read that each function execution causes call stack size to increase by 1. I'd say that even creating local variables also causes call stack to be increased by 1.

So, how are those(callstack, stack) related at all ?

Here is my assumption:

When we call nice, completely new stack gets created. In there, we store z and k. When nice calls bla , now another stack gets created for bla and this second stack stores v1,v2,v3,g. and so on. each function needs its own callstack,but we can call this stack too.

Upvotes: 5

Views: 2848

Answers (3)

Lajos Arpad
Lajos Arpad

Reputation: 76601

Stack denotes a data structure which consists of a set of usually similar items and has the following abilities:

  • push: adds an item to the "top" of the stack, which will become the new top
  • pop: removes the item from the top, thus the item which was previously the top will be the top again; this operation returns the item you remove
  • top: gets the top item of the stack, without modifying your stack

Your memory has a section called "the stack", where, as you correctly understood, functions are stored. That is the call stack. However, stack and call stack are not 100% equivalent, since stacks are used in many other cases, basically whenever you need a LIFO (Last In First Out) processing. It's used at the LIFO policy of the CPU, for example, or, when you do a depth-first search in a graph. In short, stack is a data structure, which can be applied in many cases, the call stack in memory being a prominent example.

So, why stack is in use to store function calls in memory. Let's take into consideration embedded function calls, like:

f1(f2(...(fn(x))...))

It's a rule of thumb that in order to evaluate fi, 1 <= i < n, you need to evaluate fj, where 1 < j <= n, assuming that i < j. As a result, f1 is the first to be called, but the last to be evaluated. Hence, you have a LIFO processing, which is best done via using a stack.

Upvotes: 1

eerorika
eerorika

Reputation: 238361

So, how are those(callstack, stack) related at all ?

They are very much related. They are the same thing. It is also called the execution stack.

This "callstack" is not to be confused with the general concept of "stack" data structure. The callstack called a stack because that describes the structure of the callstack.

causes call stack size to increase by 1

By "1" sure, but what it the unit of the increase? When you call a function, the stack pointer is incremented one stack frame. And the size (measured in bytes) of the stack frame varies. The frame of a function is big enough to contain all local variables (the parameters may also be stored on the stack).

So, if you wish to measure the increment in bytes, then it is not 1, but some number greater than or equal to 0.

I'd say that even creating local variables also causes call stack to be increased by 1.

As I described, having a local variable affects how the stack pointer is incremented when the function is called.

When we call nice, completely new stack gets created.

No, the same stack is shared by all function calls in the entire thread of execution.

Pretty much none of this is specified by the C++ language, but rather are implementation details that apply to most C++ implementations in typical case, but are simplified for easier understanding.

Upvotes: 2

Mike Robinson
Mike Robinson

Reputation: 8945

Each running process is allocated a chunk of memory which it calls "the stack." And, this area of memory is used both to represent the "call/return sequence" (through what are known as "stack frames"), and the so-called "local variables" that are used by each routine that is called. They are one and the same.

Usually, different CPU registers are used to point simultaneously to each thing. One register points to the "local variable" values, while an entirely different register points to the "stack frame." (In interpreters, a similar mechanism is used.) There's also a third register which indicates the current "top of stack."

At the beginning of executing each new function, the "top of stack" is simply moved ahead to account for the local variables, after the "local variables pointer" remembers what it used to be.

When a "return from subroutine" occurs, the "top-of-stack pointer" is reverted to some previous value, and everything that once existed "above it" is now, literally, forgotten. Because it no longer matters.

Upvotes: 4

Related Questions