Interview Cake
When a program is running, variables are generally stored on the call stack or the process heap. Knowing where your variables are stored helps you understand your programs and track down subtle bugs.
In C
In C, you can explicitly control whether a variable should be stored on the stack or on the heap. Say we've got this function, which creates an array and fills it with random values:
When generateRandom gets called, space to hold i and randomValues gets allocated in its frame on the call stack.
generateRandom returns a pointer to the randomValues array, so that the caller can access the random values.
When generateRandom returns, its stack frame is de-allocated, freeing up the memory that held i and randomValues.
Whoops! The caller is left with a pointer to nowhere!
What happens when the caller tries to access the returned array? A few things might happen—the program might crash, it might read a value that makes sense, or it might read some random other data that's been written where the array used to be. This can cause security vulnerabilities!
Where can a programmer get memory that sticks around past the end of a function call? Enter the process heap, also sometimes just called "the heap."
Confusingly, "the heap" is not a heap data structure. If your interviewer starts talking about heaps and you're not sure which one they mean, just ask!
The heap is a region of memory that, like the stack, stores variables in a running program. Unlike the stack, memory in the heap isn't tied to a specific function. That means one function can allocate memory on the heap, and other functions can safely use that memory until it's no longer needed.
To fix our C function from before, we can use malloc when we create randomValues. malloc, short for "memory allocate," allocates space for a variable on the heap.
Now, when generateRandom gets called, memory for randomValues gets allocated on the heap, and our stack frame just stores a pointer to it. The memory for i is still on the stack.
When generateRandom returns randomValues, it's returning a pointer to the heap block that holds the array.
So, even after the stack frame for generateRandom gets de-allocated, that pointer is still valid and safe to read from.
It'll stay valid until its explicitly freed later on with a call to free:
In Java
In Java, items can either be placed on the stack or the heap:
Java's garbage collector automatically frees heap allocations when they're no longer needed.
If you can control whether something is allocated on the stack or the heap, how should you decide where to put it?
- If a variable needs to exist beyond the current function, it must go on the heap. Remember, variables on the stack disappear once the function returns!
- If a variable takes up a lot of space, it should go on the heap. A program's call stack isn't infinite, and humongous stack frames can quickly use up all the stack space, causing a "stack overflow!" The heap is designed to hold big objects and can expand as needed if space gets tight.
- If a variable's size is unknown (like user input, network packet data, or file data), it should usually go on the heap. While compilers can handle these variables on the stack, the resulting code is usually larger and slower than heap-based versions. In fact, the Linux kernel got rid of all variable-length stack-backed arrays in late 2018.
This stack-vs-heap distinction helps us understand what's happening in in-place vs. out-of-place methods.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
