4

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.

trincot
  • 317,000
  • 35
  • 244
  • 286
Nika Kurashvili
  • 6,006
  • 8
  • 57
  • 123
  • 1
    Does this answer your question? [Explain the concept of a stack frame in a nutshell](https://stackoverflow.com/questions/10057443/explain-the-concept-of-a-stack-frame-in-a-nutshell) – Paul Sanders Feb 05 '21 at 20:34
  • This is going to be implementation deendant. C++ itself doesn't have a concept of heap and stack except for `std::stack` and `std::make_heap` family. Instead it has automatic and dynamic storage duration and those describe how those objects should be destroyed. In theory it would be perfectly valid to create an implementation that doesn't use a stack and allocates all memory in a heap. – NathanOliver Feb 05 '21 at 20:34
  • @PaulSanders I saw this, but I was hoping for a little bit of more discussion about if my assumption is correct and the actual difference between stack and call stack – Nika Kurashvili Feb 05 '21 at 20:36
  • 1
    Some architectures separate the call stack (return address stack) and a separate data stack for registers (that need restoring) and automatic storage for variables. – Richard Critten Feb 05 '21 at 20:37
  • Re: `I've read that each function execution causes call stack size to increase by 1` - this is not true, or an oversimplification at best. You should read about [calling conventions](https://en.wikipedia.org/wiki/Calling_convention) if you want the gory details, but be aware that you don't need to know this at all for everyday C++ development. – alter_igel Feb 05 '21 at 20:48
  • There's also the standard C++ [`std::stack`](https://en.cppreference.com/w/cpp/container/stack), and the data objects contained therein will be on the heap. (The standard C++ terminology does not presume a stack or heap -- those are implementation details; it has automatic storage and dynamic storage.) – Eljay Feb 05 '21 at 20:53

3 Answers3

4

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.

Mike Robinson
  • 8,490
  • 5
  • 28
  • 41
  • so, stack is one huge one, and it consists of many stack frames(as many as the function calls) , and running process doesn't create differetn stack frames, it just puts everything in the same stack – Nika Kurashvili Feb 05 '21 at 20:49
  • Exactly. "Stack frames" are actually data-structures which point at-least-backwards to one another. "Local variables" live in the space between them. In this way, even when "a [so-called 'recursive'] function calls itself," each so-called "instance" stands alone. The position of "local variables" (versus "global' ones") are defined ***relative*** **to** the "topmost stack-frame" location, always in a direction that is "above it" in the stack. – Mike Robinson Feb 05 '21 at 20:53
  • "Here we go ... let's 'call a function.'" First,we create a new "stack frame" at the top of the stack, then link it to the previous one. Next, we advance the "top-of-stack pointer" to allow for the local variables, after having first stored its previous value so that we can use it to access these variables using *relative offsets.* – Mike Robinson Feb 05 '21 at 20:55
  • some implementations have call stack limit as 1024 let's say. When you call a function with an argument, there's more than 1 items added to the stack. so how does call stack frame increase by 1 ? – Nika Kurashvili Feb 05 '21 at 20:56
  • "If the stack is limited to XXX, and you 'blow it,' then of course you die." But that doesn't happen anymore. Here goes: "Here we go ... let's 'call a function.'" First,we create a new "stack frame" at the top of the stack, then link it to the previous one. Next, we advance the "top-of-stack pointer" to allow for the local variables, after having first stored its previous value so that we can use it to access these variables using *relative offsets.* When it's time to return, we simply chain-backward to the previous stack frame, then use this to reset the "top of stack" accordingly. – Mike Robinson Feb 05 '21 at 20:57
  • What I am asking is if the stack size limit is set to 1024, let's say, why does it let us to call the recursive function by 1024 times ? the function also has local variables, to stack size limit (1024) should have been reached sooner – Nika Kurashvili Feb 05 '21 at 20:59
  • "The stack" can be presumed to be "an unlimited resource," although of course the operating system must know that it isn't. Assume that the "stack size limit" is *really big,* and that if you exceed it ... "you die, that's all." If your stack-size limit is "1024," then you very certainly will die well before you reach "1024 recursive calls." – Mike Robinson Feb 05 '21 at 20:59
2

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.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • some implementations have call stack limit as 1024 let's say. When you call a function with an argument, there's more than 1 items added to the stack. so how does call stack frame increase by 1 ? – Nika Kurashvili Feb 05 '21 at 20:55
  • @NikaKurashvili The "stack limit" of 1024 that you may be thinking of is 1024 kilobytes (that's the default on Windows). When you call a function, the stack pointer is incremented as many bytes as that function frame requires. If there the local variables require X bytes, then the stack pointer is incremented by X bytes. – eerorika Feb 05 '21 at 20:59
  • by 1024, I mean call stack depth. and it's not about kilobytes. and What I am asking is if the stack size limit is set to 1024, let's say, why does it let us to call the recursive function by 1024 times ? the function also has local variables, to stack size limit (1024) should have been reached sooner – Nika Kurashvili Feb 05 '21 at 21:00
  • @NikaKurashvili I've never encountered a C++ implementation that has a hard limit on number of nested function calls. The size of stack is always measured in bytes. – eerorika Feb 05 '21 at 21:02
  • This is in solidity(ethereum smart contract language). I asked in C++, because i knew more people would see this and thought the same context would apply in c++ too.. So in solidity, it doesn't make sense to me still. – Nika Kurashvili Feb 05 '21 at 21:03
0

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.

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
  • Thanks @lajos. There's a solidity language and ethereum virtual machine which states this: `External function calls can fail any time because they exceed the maximum call stack of 1024`. I think, this sentence is misguiding. call stack does even grow when you add new local variables. I think that 1024 is the limit of the recursion depth and not the call stack depth. Don't you agree ? – Nika Kurashvili Feb 06 '21 at 12:17
  • @NikaKurashvili The stack section in memory is where the function calls are stored. However, a call stack is an actual stack of actual calls. So, if you call f1, then you have a small stack of a single item stored in the stack section of memory. When f1 calls f2, then the call stack in question increases from 1 function to two functions. And so on. So, while the stack section in memory remains unchanged in size, its content is changed and your actual call stack increases as embedded function calls occur and decreases as embedded functions get evaluated. – Lajos Arpad Feb 06 '21 at 12:22
  • @NikaKurashvili so, the quoted statement actually tells you that you may effectuate external function calls, but, due to the maximum limit of 1024 for call stacks they might fail. Which implies the possible use of recursions. – Lajos Arpad Feb 06 '21 at 12:23
  • I somehow still don't understand. Even in the debugger, I can see that call stack and stack are completely different things. https://www.collabshot.com/show/cf0702 – Nika Kurashvili Feb 06 '21 at 12:24
  • @NikaKurashvili consider a basket of apples. The basket is the container and the apples are the content. The stack in memory is the container where functions are stored, i.e. the basket in our analogy, while the functions are the content, i.e., the baskets. When we speak about call stack size, we actually wonder about the number of the apples in the basket. The basket may be empty. Or it may contain a single apple, etc. – Lajos Arpad Feb 06 '21 at 13:02
  • I understand that, but as you can see in the image, https://www.collabshot.com/show/cf0702 `call stack` and `stack` are not the same. but i think it's just for better visuality that way. The way I think it works is there's always 1 stack, which contains the stack frames(data for each function call), but when I debug it, I think what it does is, each time, it only shows me only the part of the stack(not the big huge stack which holds all stack frames) for which the current function is being executed. What do you think ? – Nika Kurashvili Feb 06 '21 at 13:06
  • @NikaKurashvili again, the functions are the apples and the stack as the memory is their container, i.e., the basket. The basket is not the same as the apples it contains. As there are multiple programs that may run in the same time, they have separate stacks. Or, in other terms, the stack in memory is the storage space where functions may be stored. Function calls are forming a call stack, which is stored in the section called as stack. Your storage is not the same as its content. – Lajos Arpad Feb 06 '21 at 13:22
  • yes, I think that's what i said. if I write a program, it will have its own stack, but the function calls will be stored in that stack. I said something about debugger, which only shows the part of the stack(the current function) and not the whole stack of my program. – Nika Kurashvili Feb 06 '21 at 13:26