100

Pointers and dynamic memory – stack vs heap


Memory, is one important and crucial resource
on our machine and it is always good to know the architecture of memory,
the way operating system manages memory and the way memory is
accesible to us as programmers. In this lesson we will discuss
the concept of dynamic memory and we will see how to work with dynamic
memory using C or C++. The memory that is assigned to a program
or application in a typical architecture can be divided into four
segments. One segment of the memory is assigned to store the instructions
that need to be executed. Another section stores all the static
or global variables, the variables that are not declared inside a function,
and that have the whole lifetime of an application, they are
accesible anywhere during the whole life cycle of the application as long
as the application is running. One section of the memory is used to store
all the information of function calls and all the local variables
and we have also talked about stack in our lesson on Call by Reference.
Local variables are declared inside a function and they live only till
the time the function is executing. The amount of memory set aside for these three
segements: the text segment, the global variable segment and the
stack, does not grow while the application is running. We will
come back to why we use this fourth segment- heap , in a while. Let us
first understand how these three segments of the memory are used when
a program executes. I have a simple C program here. We have a function
square that gives me the square of a number. We have another function
Square of Sum that is given two arguments x and y, and it returns
us the square of x plus y. And, in the main method, I am just calling
this function Square of Sum passing it two arguments a and b. Let us now
see what happens in the memory when this program executes. Let us
say this rectangle in green here is memoryreserved as stack and the rectangle
in orange is the memory reserved as Static or Global variable
section. When the program starts executing, first the main method is
invoked. When the main method is invoked, some amount of memory from
the stack is allocated for execution of main. And this total is a
global variable, so it should sit in the global section. The amount of memory
allocated in stack for execution of main can also be called the stack
frame for the method main. All the local varibales, arguments,
and the information where this function should return back to, all this information
is stored within this stack frame. The size of the stack frame for
a method is calculated when the program is compiling. Now, when main
calls Square of Sum method, let’s write shortcut SOS, for Square
of Sum, then a stack frame is allocated for the call to Square Of Sum,
all these local varibales x, y and z will sit in this particular stack frame.
Now, Sum of Square calls Square,lets again put a shortcut here for
square, so another stack frame for square and it will have its own local
variables. At any time during the execution of the program, the function at
the top of the stack is executing and rest are kind of paused, waiting
for the function above to return something and then it will resume execution.
I have drawn these play and pause button here, in case you do
not understand.Ok, so this total is a global variable , it’s here in
this section. Global variable because it is not declared inside a function.
We can access it anywhere, and then we go to this particular statement
where we call Square of Sum, and Square of Sum is calling Square and
so this is called our call stack. This program may not be the best way
to implement this logic. I have written this program this way so that
I can have some nested methods calling each other. Let’s say right
now we are at this particular statement, we are executing this statement.
So, at this stage the call stack will have these three methods. Now,
when this method finishes, we will return back to this particular statement.
As soon as Square function will return, it will be cleared from
the stack memory and now Square of Sum function will resume. Once again
when Square of Sum finished, the control will come to this particular
line total is equal to Square of Sum and main will resume again.
Now, main will call printf, so once again printf will go to the top of the
stack. Printf will finish and the control will come back again to main and now
main will finish. And, now main finishes, program will also finish.So,
In the end, our global variables will also get cleared. There was no need in
this program to keep this variable total as global. We should assign
a variable as global only if it is needed at multiple places in multiple functions
and it is needed for the whole lifetime of the program, otherwise
it is a waste of memory to keep a variable for the whole lifetime of
program execution. We had kept one global variable in this program just to
understand the concepts. Here, I must point out one more thing, when
our program starts, our operating system allocates some amount of
reserved space, let’s say OS allocates 1 MB of space as stack, but the
actual allocation of the stack frame and the actual allocation of the local
variables happens from the stack during runtime and if our call stack
grows beyond the reserved memory for the stack like for example, if
a method A calls B, B calls C and we go on calling and we exhaust the whole
space reserved for the stack, then this is called stack overflow
and in this case our program will crash. One common case of stack overflow is
when you write a bad recursion and your program goes infinitely
into recursion. So, as we can see, there are some limitaions of stack. The
memory set aside for stack does not grow during runtime. Application
cannot request more memory for stack. So, if it is 1 MB, then if the
allocation of variable and functions in stack exceeds 1 MB, our program will crash.
Further the allocation and deallocation of memory onto the stack happens
by a set rule. When a function is called, it is pushed onto the
stack, when it finishes, it is popped out of the stack or removed from the
stack. It is not possible to manipulate the scope of a variable if it is
on the stack. Another limitation is that if we need to declare a
large data type, like an array as local variable, then we need to know the size
of the array at compile time only. If we have a scenario like we have
to decide how large the array will be based on some parameter during
runtime then it is a problem with stack. For all these problems,
like allocaing large chunks of memory or keeping variable in the memory till
the time we want, we have heap. Unlike stack, application’s heap
is not fixed. It’s size can vary during the lifetime of the application and
there is no set rule for allocation or deallocation of the memory.
A programmer can totally control how much memory to use from the heap,
till what time to keep the data in the memory during the applications
lifetime and heap can grow as long as you do not run out of memory
on the system itself. That is a dangerous thing also and we need to be
really careful about using heap for this reason. We also sometimes call
heap, free pool of memory or free store of memory. We can get as much
as we want from the heap. How heap is implemented by the operating system,
language runtime or the compiler, is something which can vary,
which is a thing of computer architecture. But an abstracted way of looking
at the heap as a programmer is that this is one large free
pool of memory available to us that we can use flexibly as per our need.
Heap is also called dynamic memory and using the heap is referred to as
dynamic memory allocation. Let us now see how to use the heap in out
C or C++ program. I will clear this code in the left and I will draw one
more rectangular block here for heap. there is one more thing that I must
point out before moving forward. Heap is also one data structure and
if you do not know about this data structure Heap yet, you will learn
about it in your Data Structure course. But this nomenclature here
has nothing to do with heap data structure. The term heap is being
used only for the large free pool of memory. Heap data strcutre does not
come anywhere in this context. This term often confuses a lot of
people when they know about heap data structure. Stack is also one data
strcutre but the stack segment of the memory is actually an implementation
of the stack data structure but heap is not an implementation
of the heap data structure. To use dynamic memory in C, we need to know
about four functions malloc, calloc, realloc and free. To use dynamic
memory in C++, we need to know about two operators new and delete.
These four functions can also be used in C++, as C++ has backward compatibility.
It is only a superset of C. But C++ programmers use mostly
these two operators, new and delete. We will see some code examples
and try to understand how things happen when dynamic memory is used.
Let us first pick up some code examples in C. Let us write a C
program. I will clean up some of the stuff in the right. 1 MB for stack,
this was just an assumption. In reality, the size of the stack will be decided
by the operating system and the compiler. It is a thing of computer architecture.
Coming back to the code, if we declare a variable like this,
then this variable is a local variable. It goes on the stack. Memory for
this particular variable a’ will be allocated from the stack frame of the main
method. Let us say we want to store an integer on the heap. To reserve,
or get some space allocated on the heap, we need to call the
malloc function, something like this. The malloc function asks for how
much memory to allocate on the heap in bytes. When we say malloc and
pass as argument size of integer, then we are saying that “Hey, give
me a block of memory, which is 4 bytes. 4 bytes is the typical size of
the integer. So, one block of 4 bytes will be reserved or allocated on the
heap and malloc will return a pointer to starting address of this block.
And, malloc returns a void pointer. Let us say, the starting address
of this block of 4 bytes is 200, then malloc will return us address 200. Now,
we have a pointer to integer p, which is a local variable to main.
So, this will be allocated in the stack frame of the main method. We have
done a typecasting here, because malloc returns pointer to void, sorry,
void pointer and p is an integer pointer. Now, p stores the address
of this block of memory which is 200. So, we have got some block of memory
on the heap which we want to use to strore an integer. Right now,
we do not know what’s there in this particular block of memory. If we
want to fill in something here, we need to dereference this location using
the pointer p and then put in some value. In fact the only way to use memory
on heap is through reference. All the malloc function does it,
looks for some free space in the heap, books it or reserves it for you
and give back the pointer. And the only way you can access this particular
block by keeping a pointer variable which will be local to your function.
Now, let us write something like this. After writing 10 in this particular
block, i will go ahead and make one more call to malloc. When I make
one more call to malloc, one more block of 4 bytes is allocated on the
heap and let us say the address is 400 for this block. Now, the address that
is returned by the second call to malloc, we store this address in the
variable p. So, what happens is, that p is now pointing to the address
400. The next line writes address 20 to this address. We allocated one
more block and we modified the address in p to point to this
block. The previous block will still sit in the heap. This memory we are
still consuming, it will not be cleared off automatically. At any point in
our program , if we are done using some block of memory which is dynamically
allocated using malloc, we also need to clear it, because
it is unnecessary consumption of memory which is an important resource.
So, what we should have done here is that once we were done using
this particular block of memory at 200, we should have made a call
to the function free. Any memory which is allocated using malloc, is
cleared off by calling free. And to free, we pass the pointer to the starting
address of the memory block. So, now with this code this first block
of memory will first be cleared and then we will be pointing to anohter
memory address. It is the responsibility of the programmer to clear
anything on the heap if he has allocated it and does not need it any
further. So, you see, in terms of the scope of the variable, anything allocated
on the heap is not automatically deallocated when the function
completes like on the stack. And, it does not need to live for the whole
lifetime of the application like a global variable. We can control when
to free anything on the heap, when to deallocate anything on the heap. If
we wanted to store an array in the heap, like let’s say we wanted to store
an integer array into the heap, then all we do is make a call to the
malloc asking for one block of memory equal to the total size of the array
in bytes. So, if we want an integer array of 20 elements, then we will
make a call to malloc asking 20 X size of int which will be 4 number of
bytes. So, what will happen now, is that one bit of contigous block of
byte for 20 integers will be allocated on the heap and we will get the
starting address of the heap. So, we kind of get the base address of the
array. This p will point here, to the base address of this block. And then in
our code we can use this, 20 integers as P[0], P[1], P[2] and so on. As
we know, P[0] is same as saying value at address P, and P[1] is same
as saying value at address P+1. This is what it means. One more thing,
if malloc is not able to find any free block of memory, is not able to allocate
some memory on the heap, it returns null. So, for error handling,
we need to know this and we need to write our code appropriately.Malloc
and Free. The use of malloc and free is C style code. If we want to write
the same code, same logic in C++, there is not much difference. Instead
of using these two functions, malloc and free, we will use two
operators: New and Delete.And, we will write our code something
like this. So, instead of malloc, we are using the New operator here
and instead of using free, we are using delete here. If we want to allocate
an array, we use something like this where we put the size
in brackets here. And, if we want to free an array, we use this particular
operator delete and two brackets, sorry, one bracket. With C++, we
do not have to do all these typecastings, like malloc returns void and
we need to typecast it back to integer pointer. New and Delete operators
are type safe. What it means is, that they are used with a type and return
pointers to a particular type only. So, here p will get a pointer to integer
only. We will be talking about dynamic memory allocation and other
library function in more detail in the coming lessons. So, Thanks for
watching!

Glenn Chapman

100 Comments

  1. Wow thank you for saying something like heap isn't the same like datastructure heap I got quit confused by that XD

  2. very very thank you Sir……nobody has included this topic in such a simple technique C programming tutorial……

  3. 16:47, in the line
    P=new int;
    Where exactly are u telling, how many blocks must be allocated in heap.. Like, if i want 2 blocks of int data type each.. "new int" doesn't tell how many blocks to allocate..

  4. probably the best explanation of memory allocation I have heard, great work buddy way to go!

  5. How does free () function get to know how much bytes of memory to be cleared ? Since we can only pass as an argument to free is a pointer and we all know pointer holds the starting address of the assigned memory.

  6. will square function work this way you have called it in sqaureofsum()?

    As i can see that square takes one argument ie int and below we are passing the addition of the two variable to that function ??

    I don't know will it work or not bt please explain coz i have a doubt abt it.

  7. when you allocated 1 integer, you showed just 1 block of memory got allocated; however, when you allocated 20 integers, you showed 80 blocks of memory getting allocated. So what was wrong? Either the first allocation (that should've allocated 4 blocks of memory) or the second one (that should've allocated 20 blocks of memory) ?

  8. What does he mean when he says: Heap here is not an implementation of heap Data Structure ?

  9. what does it that stack-frame-size is calculated during compilation??

    int main()
    {
    int temp; cin>>temp ; // is it not that temp will get its value during run time??
    int arr[temp] ; // if the temp getting its value at runtime arr is declared to size temp at run time only??

    }
    plz repy ASAP !! i am totally confused. Thanks for the video .

  10. even after using free() function to delete allocated memory , pointer p still contains address of memory block , why?

  11. Great people who created this channel. Really thankful and I hope you continue with this project someday.

  12. I started computer science one year ago And I have never understood that, but by wacthing your video I got it in less than 20 min, You have a gift for teaching

  13. It is amazing…..your presentation was good enough to address the problem I had in 10 classroom sessions

  14. Awesome presentation. Which whiteboard software are you using for your presentation?

  15. I've never encountered an explanation of this subject that was so easy to understand as well as covering so much material. Thank you infinitely

  16. Stacks grown downward, and heaps grown upward, typically. So when you say a stack does not grow, you are wrong. I recommend reading OS 9th Edition, by Silberschatz.

  17. I am a Vietnamese student. Indians are very smart and friendly. You help me alot!

  18. Amazing explanation of memory management!! Thanks a lot!!!! Wonder, why we don't get to know this, like this in college!

  19. So, are globals a session in the stock or a special session of memory as hit and stack?

  20. Have been looking for this for ages! Thanks for a very concise and clear explanation!!!

  21. Wooow what a teaching…!…why doesn't this guy has 1M subscribers yet??…

  22. For some reason I either can't focus or understand when hearing indian videos, you guys should subtitle your videos instead of doing this all over youtube.

  23. Gonna be taking a course that involves a lot of this sort of material. The explanations are very much appreciated!

  24. int Squire(), int BillySquire() …great video, but damn that was funny

  25. so the stack grows from low to high addresses and the heap grows randomly because you used different start-addresses every time you allocated space on the heap?

  26. Wow. This cleared up so much confusion I didn't even know I had! I feel far more solid in my understanding of stack/heap/memory. Thank you!!!

  27. Thanks very simple and straight forward explanation of stack vs heap in memory. Keep up the good work.

  28. I'm in my 2nd year of computer engineering, finally someone tells me that "heap" is NOT the data structure. Thanks a lot

  29. A legend. So sorry that he isn't alive anymore, but his videos will stay on forever. I suppose he was a red coder on codeforces also? Correct me if I wrong.

  30. you have to add about array of pointers with example of command line argument

  31. I was more in love with python than C/C++ because I never understood the concept of pointer clearly but now I think I'm in love pointers. Thanks to this man! Love and respect from future…

  32. Always had to deal with stack and heap, and I was unclear of the difference. This explanation and examples were kick-ass. Loved it and it was the best delineation of the stack and heap that I have ever ran into. Thanks much!

  33. this could have been the best channel ever on youtube
    only if he woould have continued… sad he is not posting anything now

  34. why should we type-cast malloc to int, why cant we instead create a pointer of type void?

  35. What size of the heap memory? As I know heap is per application? How OS decide to allocate size for application correctly? Thanks

Leave a Reply

Your email address will not be published. Required fields are marked *