Thread: Understanding Call Stacks

There are different ways for memory to be allocated for a program to use:

There's the stack and the heap. The stack behaves like a stack data structure:

Whenever something gets "allocated" on the stack, it's pushed onto the stack. Whenever something gets "unallocated" on the stack, it's popped off.

This structure very efficiently handles scopes in a natural manner:

void func1(int a, int b)
{
    for(int i = 0; i < b; ++i)
    {
        func2(i, a);
    }
}
 
void func2(int c, int d)
{
}

Now let's look at the stack:

func1 scope:
    int a
    int b
    int i
func2 scope:
    int c
    int d

When func1 gets called, a, b, i get pushed onto the stack. func2 calls func2, and c,d get pushed onto the stack. A function only has access to variables which are newer than the marker of where it was called. After func2 returns to func1, c and d are popped off so func1 can never access c or d.

This type of allocation maps very nicely to an "ideal" shared memory model where your computer has a single large array of memory. To pop all of the variables of a scope off the stack, the program just needs to move where the tail of the stack is, so you could clean up an entire scope with one very fast operation. All the program needs to do is at the beginning allocate some fixed array of memory which can fit the entire stack the program could use (one for each thread).

Items allocated on the heap work differently. Here, a chunk of arbitrary memory is allocated somewhere in memory. The program needs to know where this chunk of memory is allocated, so the address of this block is stored in a heap structure. Now multiple variables could refer to the same chunk of memory, so the heap object no longer has any ties to scope, and it must be manually deleted. This is more expensive than stack operations (though you probably won't notice/care about the difference unless you look very carefully).

Java takes this one step further by reasoning that variables do have scope, and when all variables stop referring to a certain block of memory it should be automatically un-allocated. This is what Garbage Collectors do (there are other ways to solve this problem, too). However, garbage collection has some non-zero overhead because it must search for what chunks of memory no longer have any references to them.

In Java, primitives are allocated on the stack, and objects are allocated on the heap. This is not a strict requirement of how stacks and heaps work, and indeed other languages like C++ or C# do not have this requirement.

In both cases, I was careful to avoid any mention of RAM. Why? Because it doesn't have to be RAM. Performance will suffer greatly if the memory can't be treated more or less as RAM, which is why nearly all modern computers use some variant of RAM, along with some caching scheme but that's beyond the scope of this discussion.