Breaking Down the Call Stack
Stack Background
If you are familiar with the tech industry you may have heard of Stack Overflow, the website, or Full-Stack Academy, the coding bootcamp. When I first began, these names sounded sweet, but I had no clue what they were referring to. Then, I actually started to code… bring on the overflow errors. A stack overflow is exactly what it sounds like. When the stack does not contain enough space to have new items pushed into it, then it has reached an overflow state. But WHAT THE HELL is a stack?
The reason that “the Call Stack” can be a vague concept is because in computer science, a stack is an abstract data type. A stack serves as a collection of elements that can “push” or “pop” elements on and off the stack. As can be seen in the image below, the name “stack” comes from the analogy of stacking physical items on top of each other. While putting items on and taking them off is easy, getting items deeper in the stack require taking multiple other items off first. A stack is either empty or it consists of a “top” and the rest, which is the stack.
A few simple applications that a stack is good for are the reversal of a string or clicking the “undo” button in your text editor. For example, think about how you would find your way through a maze. Once you reached a dead end, you would backtrack to the previous point of choice. Similarly, at each point of a stack all possible choices are stored and backtracking would simply mean popping the next choice from the stack. This small background on stack data structures will help us in understanding how “the Call Stack” or “Execution Stack” works.
The Call Stack
When referring to the Call Stack, engineers are speaking about the stack data structure that stores information about the active subroutines of a computer program. A subroutine is a sequence of program instructions that perform a specific task, packaged as a unit and can be used in programs wherever the task should be performed. I would think of a subroutine as a method or a function.
The main purpose of the Call Stack is to keep track of the point to which each active subroutine should return control when it finishes executing.
Maintenance of the Call Stack is incredibly important to keep your application running smoothly, but the details of it are often hidden in high-level programming languages with strong abstraction from the details of the computer. “In high-level programming languages, the specifics of the Call Stack are usually hidden from the programmer. They are given access only to a set of functions, and not the memory on the stack itself. This is an example of abstraction. Most assembly languages, on the other hand, require programmers to be involved with manipulating the stack. The actual details of the stack in a programming language depend upon the compiler, operating system, and the available instruction set.”
“Since the Call Stack is organized as a stack, the caller pushes the return address onto the stack, and the called subroutine, when it finishes, pulls or pops the return address off the Call Stack and transfers control to that address. If a called subroutine calls on yet another subroutine, it will push another return address onto the Call Stack, and so on, with the information stacking up and unstacking as the program dictates.” The Call Stack only has so much space in it and as the pushing consumes allocated space within the Call Stack, a stack overflow can occur causing the program to crash.
The Call Stack is important because each task can have it’s own separate stack. This means that each function called can be active simultaneously for different tasks doing different things. Another advantage is that a Call Stack supports recursive calls automatically.
The structure of a stack can also be confusing. However, each function call of a stack is kept in it’s own state of the stack called a “stack frame.” This remains in the stack until it has been terminated by a return value at which point it is popped off. This concept may seem difficult to picture (although pictured above), but let’s say we had a function named DrawSquare that called a helper function within it named DrawLine. The first thing that will happen is the function named DrawSquare will be pushed onto the stack as it is run. Remembering that an element on the stack is not popped off or terminated until a return value is called, DrawLine gets called and pushed onto the stack on top of DrawSquare. Now, we have two stack frames on our Call Stack like we can see above. Depending on how many times DrawLine gets called and how each function is written, we may have more stack frames (assuming we are drawing a square, DrawLine will get called 4 times, so there could be 5 stack frames). As each line gets drawn, the return value of DrawLine will pop each DrawLine stack frame off of the stack until it bubbles down to the DrawSquare stack frame. Once DrawSquare hits it’s return value it will be popped off and we will have an empty stack once again.
What would happen if the DrawLine function was running a complex transformation algorithm that is running in the browser though?
“While the Call Stack has functions to execute, the browser can’t do anything else — it’s being blocked. This means that the browser can’t render, it can’t run any other code, it’s just stuck. And here comes the problem — your app is stuck.” Given too much to process in the Call Stack, your browser may be unresponsive for a long period of time and eventually the browser will error out on behalf of your program.
If you were building this program in JavaScript, here is a case where we can clearly see how the Call Stack is abstracted. Since JS is an asynchronous language, later doesn’t necessarily happen strictly and immediately after now. This means that your program will still run while the Call Stack is executing the complex algorithm and will re-render your page when it is executed.