“Anything beats an expensive stack of papers” Larry Niven
Before reading this section we’re assuming you already familiar with functions.
Let’s say we’re reading an article and on the page 10, there’s a reference to another article that needs to be read and that is a prerequisite to the rest of this first-article.
So we stop at the page 10 of the first article, find the second one and bring it on top of the first article and start to read.
Note: basically we’ve created a stack of two articles.
While at the second article, we realize at the page 13 there’s another reference to an article and we need to read that article first before proceeding to the rest of this second article.
So we find the third article and start to read it.
Note: now there are three articles sacked on top of each other.
Fortunately there’s no reference in the third article and we read all of it so it’s now off the stack.
Now we’re back to the second article right at page 13 and keep reading the rest of the article.
The second article also finished without any reference to another external resource and so it’s off the stack as well.
Back to the first article, we keep reading from the page 10 (where the second article showed up) and as we progressed, in the page 18 there’s another reference to another article.
So again we find the article and start reading it.
Note: while we’re reading this reference article, the first one is at the page 18 and waiting for its turn (after the referenced article is finished).
After a while the reference-article is finished and off the stack. So we’re back to the first article right in the page 18 and keep reading to the end of the article.
Fortunately there wasn’t any other external reference and the first article finished as well.
—————————-
Alright, let’s jump into C++ programming and see how the story above relates to stack and heap:
In computers in general section, we mentioned that the CPU is at the heart of a computer and is in charge of running programs.
But what is it that CPU runs in a program? Well, it’s the instructions of the programs (every declarations, expressions, initializations, conditions that involved in a program, line by line, statement by statement, from top to bottom). You can think of a program as the article in our story.
Like any article that has the beginning page and we read from this page (which is considered as the entry point to the article), a program has an entry as well and CPU starts from there.
The main() function is considered to be the entry point of a program in C++.
When the OS loads the memory with our program, the CPU will find the main() function of the program and will start to execute the instructions within the body of this function.
Note: The execution of instructions of a program is statement by statement from top to bottom. This means the CPU will not start from the first line of the main() function and then randomly jump to another line! No, it will read the first line, then the next one below it and so one…
Let’s see an example:
#include <iostream>
int main() {
int a = 20 ;
int b = 30;
int c = 40 ;
int d = 50;
int res = (a+b) * d; // (20+30) * 50
return 0;
}In this example, the CPU will start from the first statement which is declaring and initializing the a variable, then move on to the next statement which again declaring and initializing a variable named b. The next two statements are also declaring and initializing two variables named c and d by assigning the values 40 and 50 respectively.
Then the CPU will move on to the fifth statement which is declaring another variable named res and assigning the result of the expression (a+b) * d; to this variable.
Note: spaces are removed at compile time.
The next statement in this example is return 0; which will cause the termination of the function and returns the value 0 to the operating system.
We say the value of the return keyword will be sent to the Operating System because the OS is considered as the caller of the program.
Note: when we say a line of instruction, it doesn’t mean if a program has 10 lines then there’re 10 instructions in that program!
For example if we had:
#include <iostream>
int main() {
int a = 10 ;int b = 20;int c = 30 ;int d = 40;
int result = (a+b) * d; // (10+20) * 40
return 0;
}The int a = 10 ;int b = 20;int c = 30 ;int d = 40; is 4 instructions for the CPU to run!
Also if we had a line of instruction like:
a
=
10
;This is still considered one line of instruction even though it took 5 editor’s line!
Basically semicolon is one factor of separating lines of instructions from each other.
Memory:
A program at first is stored in the hard-disk. When we want to run this program, the OS will move it from the hard-disk to the memory (RAM) so that the CPU can take the instructions of this program and start to execute them.
This is like we’re bringing an article from library and place it on a table and start to read. In this analogy, the library is the hard-disk, the article is the program, the table is the memory (RAM) and the CPU is actually the person that wants to read the article.
The memory part is divided into multiple segments and three of them that are related to this section are:
-
Stack: stack is the region of the memory that a function takes
place when it is being called.
To use an analogy, stack would be the region on the table that we put an article there to read.
It is called stack, because when a caller function calls another function (called-function) it is like putting the called-function on top of the caller function so the execution of the instructions of the caller function will be stopped for a while and the CPU will move on to the called function to run its instructions. So while the called-function is running by the CPU, the caller-function is stand still.
This is like when we had one article and another reference came up so we stopped the first article and started to read the second one.
A couple of notes to remember here:
-
If one function called another function, the second one will take
its own place in the stack memory and won’t replace the memory space of
the first function. This means both functions will hold their local
variables and data.
But when the second function or any other function finished its work (all the instructions in the body of the function executed), the memory space allocated to this function is taken back and so any data in the body of the function will be destroyed after the function is ended.
-
This means as long as a function is in the stack-memory, so are
its local data (variables etc.) -
You should know that the stack-memory space is a limited area and
so we can’t store large amount of data in functions.
-
Data: `data` segment is the place where all non-constant
variables that are declared outside of functions will be stored
there.
Note: non-constant means a type of variable that its content can be changed (like all the variables that we saw so far). (Read the const section for more information)For example:
#include <iostream>
int ext = 1000;
int main() {
int a = 10 ;
int b = 20;
return 0;
}In this example, the ext variable is declared as non-constant and outside of all functions so its memory space comes from data-segment.
The difference of this data-segment compared to stack is that, any variable that has its memory-space in this region, will live for as long as the program is running.
-
Heap: heap is the region of the memory that we
can dynamically allocate a memory space from this region to a variable
via the call to functions like `malloc`, `calloc` and also
`new` statement. This space is larger compered to `data-segment`
and `stack-segment`.
Also if we don’t explicitly release the memory space that we got from this region, it will stay with the program for as long as the program is running.
This is called (memory-leaked) and is explained in more detail in free() section.
Generally speaking, a variable with dynamic-memory space is accessible within the body of any function in a source code. (There are however some exceptions to this which we will get into the details in later sections (linkage, storage, scope)).
The memory space that is allocated from this area is called dynamic-memory because anytime during the program’s execution, we can take a portion of the memory of this heap-area and release it when we no-longer need it.
Note: there's another segment of the memory called `text-segment` or `code-segment` where source-code of the program is there (including constant data). This segment is read-only.
Let’s run an example to see how stack memory allocation works in practice:
#include <iostream>
using namespace std;
int sum(int , int);
int main() {
int a = 10 ;
int b = 20;
int result = sum (a, b);
cout<<"The result is: "<< result;
return 0;
}
int sum (int valueOne , int valueTwo){
return valueOne + valueTwo;
}
Output:The result is: 30
In the example above, considering that the entry point of C++ programs is the main() function, the CPU will start by running the instructions within the body of this function.
Note: when the main function is called, a memory space in the stack is set aside for it and any local data (variables etc.) of this function will be stored in there. Basically the main() function is the first function that will come to the stack.
Also because this function is at the bottom of the stack, it will be the last one to leave as well which in this case it is considered the end of the program.
The first two lines of instructions is to declare two variables named a and b and then assign the values 10 and 20 to these variables respectively.
So these two variables are now the local variable of the main() function and are stored in the memory space allocated to the function in the stack-segment.
On the third line of instructions things get more interesting!
First, the instruction is to declare a variable named result. So this variable will be declared and then it’s time to run the assignment part of this variable.
The instruction here is to call another function named sum().
This is like we are at some page of an article and then we face a reference that is needed to be read first in order to be able to continue with the rest of the article.
So what happens here is that the first function main will stop executing the rest of its instructions by the CPU and the CPU will start to run the instructions within the body of sum() function.
Note: before this function gets the chance of running, part of the memory in stack will be allocated to this function and every local variable and their values in this function will be stored in the allocated memory space within the stack. (int valueOne and int valueTwo are the two variables that are considered to be the local variable of the sum function).
When we called the sum function in the body of main function, we put two arguments in the function and as explained in the function section these arguments will be the values assigned to each parameter of the function. So now the valueOne variable has the value 10 and valueTwo variable has the value 20.
Now the sum function is on top of the stack and its instructions is about to run while the main function is waiting for this one to finish its instruction execution.
Within the body of sum function there’s only one statement to be executed and that is returning the result of valueOne + valueTwo expression to the caller function which is main via the return keyword.
The result is 30 and this value is returned to the main function and is assigned to the result variable.
At this moment the memory space assigned to the sum function is taken back and the function no-longer exists in the stack.
The next line of instructions in the main() function is to call the cout object to send the value assigned to the result variable and another message to the output stream.
The last line of instructions in the main() function is to call the return 0; statement which is equal to the end of the main function.
At this stage the main function reached to its end and the memory space allocated to this function in the stack will be released as well and of course this is equal to the end of our program.