What and Where are Stack and Heap?

Physical Level

    First of all, you should understand that Stack and Heap does not have a physical representation - it is a memory abstraction, so there is not physical difference between them, they are both in RAM. I will not explain how RAM works in this article. Those abstraction are created by OS and are helping us to develop some good software and not to think about where each variable and functions is going in RAM and keep tracking it there.
Some history here: First computers were able to run just one program(a process), that used all the memory it needed(starting from physical address 64k - max for this example).

     multiprogramming was born, ih which multiple processes were ready to run at a given time and OS would switch between them in order to maximize CPU use. Soon people began demanding more of machine and the era of time sharing(minimizing response time) was born in order to serve more users who used different terminals to access same machine.
Computers were expensive and it was useless to buy them for performing just one operation. Thus
   One way to implement time sharing would be to run one process for a short while, giving it full access to all memory, then stop it, save all of its state to some kind of disk (including all of physical memory), load some other process’s state, run it for a while, and thus implement some kind of crude sharing of the machine. Unfortunately, this approach has a big problem: it is way too slow, particularly as memory grows. While saving and restoring register-level state is relatively fast, saving the entire contents of memory to disk is brutally non-performant. Thus, what we’d rather do is leave processes in memory while switching between them, allowing the OS to implement time sharing efficiently.

But this method has its own problems like protection, each process can access same memory. So process A could change some variables process B depends on. So  the address space was created as new abstraction level. Each process has its own address space which is divided in different segments and looks basically like this:

For example program's code(instructions) have to live somewhere in memory and thus they are in address space so are stack and heap which we will discuss.

                                               Stack

    Stack is a collection of items where addition and the removal of items always takes place at the "top"(stack also has "base" - opposite of "top"). You can imagine stack as tower from "Tower of Hanoi" problem.

   When you add an item it always goes on top of the tower and if you want to remove item "2" for example you should also remove item "1" in order to clear the top. This principle is called "LIFO"(Last In First Out), so you will always have older items near the base, while newer near the top.
Example: when you use mobile app or browser and press back button - it will take you on the previous page, because as you navigate from page to page, those pages are placed on a stack with current page always on the top and the first page you looked on the base. When you click on the back button you will remove your current page(on the top) from the stack and the previous would become current.
  Each program gets a stack which is always allocated when it "starts" and can grow and shrink within constraints limited by OS. Stack is thread safe, because each thread has its own stack(but shares same heap)
  Every time you call a function: the stack pointer increments to the next physical memory address, creates new block/reserves space for its variables etc and copies it to that address. New block will have all local variables, function parameters, object references and return values.
  When you return from the function the block is removed from the top of the stack, memory released, the objects, variables etc used by this function are not accessible anymore and stack pointer decrements to the previous available item. The name of those procedures are "Push"(storing something on stack) and "Pop"(retrieving+deleting something from stack).
Stack is stores only primitive data types and addresses pointing to objects stored on Heap(object references). And all variables created on Stack are local and exists only while function executes, this concepts is called "variable scope"(local and global variables).

You will get a StackOverflowException thrown when you program had used up all the available space on the stack and almost certainly the symptom of the endless recursive calls, when function starts calling itself and allocate memory on stack for its local variables each time till you are out of memory on Stack.


                                                Heap
   Heap memory is a Dynamic memory(its size changes as program run) used to store arrays, global variables(with global scope/accessible from any function) and any created class instances(objects) at runtime in Java which are referred by the reference variables from Stack memory. It also becomes a space for String pool which is used to store the String values in Java (every String values has a unique address inside the pool).

   Talking about the size of memory, Heap memory has bigger size than Stack memory and unlike the Stack, the Heap does not have size restrictions on variable size apart from the physical limitations of your computer) also unlike Stack(allocated at compile time), Heap is allocated at runtime. When the heap memory is out of space, you will get OutOfMemoryError: Java Heap Space exception thrown. When object reference is not longer available on Stack - Java Garbage Collector will deallocate space reserved by that object on Heap. Heap memory is slower than Stack, because it has to use pointer to access the allocated regions on the Heap.

                                               Summary

                          Heap                                                       Stack         

   Stack

1. Stack is limited in size by Operating System.
2. Stack is fast.
3. Stack is used only for storing small data types(variables, object references).
4. Variables and References on Stack have Local Scope and are accessible only within their Stack memory block.

    Heap

1. Heap has no size limits, apart from physical RAM limitations.
2. Heap is not as fast as Stack.
3. Heap stores all instances of the class(objects).
4. Variables and References on Heap have Global Scope and are accessible throughout the program.

How does it work:

           Every time you create an instance of a class, some memory gets allocated on Heap to store that object and return a reference pointer to the start of that block of memory. This reference pointer comes in the form of a unique number represented in hexadecimal format, and as an integer it is stored on the Stack, so when we need to access that object on Heap, we find its reference on Stack which points to objects location on Heap, which is then accessed by that reference.

Example:

What is happening behind the wall(the scheme is showed below):

1. When JVM find main() method, the Stack frame will be created. After we create an instance of class Example, which means, that memory will be allocated on Heap to store the object and its address will be stored on Stack in form of a pointer.
2. When method fun1() is called, one more Stack frame will be created. local_var1 and its value will be stored on it, as it is local primitive variable. 
3. Method fun2() is called. New Stack frame created and as with main() method memory allocation for object o will happen on Heap and pointer will be returned and saved on Stack.
4. Method fun3() is called. Parameter obj is saved on Stack as it is pointer to an object on Heap, local_var2 and its value is saved on Stack as well. Memory allocation for string will happen on the Heap in String Pool in Java.

     5. After all GC will be invoked and memory will be released.

Author:   Maxim Malisciuc(Maksym Malishchuk)

email: developerint97@gmail.com