The Stack and the Heap

A running Java program keeps its data in more than one place in memory. Two of those places matter for understanding how a program behaves: the stack and the heap. They differ in what they hold, how long that data lives, and who cleans it up. This post explains both, mostly in terms of Java, with some comparison to C and C++ where it helps.

What lives where in Java

In Java, the standard conceptual rule of thumb is short:

• A method call's local variables and parameters are stored in its stack frame.
• Objects — anything you create with new — conceptually live on the heap.

These two facts interact for reference types. Suppose we have a small class:

public class Employee {
    private int id;
    // constructor, getter, etc.
}

Now consider this line:

Employee e = new Employee(1);

This involves two separate pieces of memory. The object — the actual Employee, with its id field — is created on the heap. The variable e is a local variable, so its reference value is stored in the stack frame, and that reference points to the object on the heap.

A primitive local variable is different. With int count = 5;, the local-variable slot for count holds its value, 5, directly in the stack frame. There is no separate object anywhere.

        Stack                                Heap
   ┌─────────────────┐              ┌──────────────────────┐
   │ e   ■───────────┼────────────▶ │ Employee             │
   │                 │              │   id = 1             │
   │ count = 5       │              │                      │
   └─────────────────┘              └──────────────────────┘

The stack

The stack holds the data for method calls. Each time a method is called, Java sets aside a block of memory called a frame for that call. The frame holds the method's local-variable slots, its parameters, and some bookkeeping.

The frames are arranged as a stack in the data-structure sense: last in, first out. When method A calls method B, a frame for B is pushed on top of A's frame. When B returns, its frame is popped off, and control goes back to A. If B had called C, C's frame would sit on top of B's and would be popped first.

This has one important consequence: the storage for a method call is automatic and tied to that call. The frame comes into existence when the method is called, and it is gone the moment the method returns and its frame is popped. A local variable may be in scope for only part of the method, but in any case you do not free it; its stack storage goes away on its own when the call ends.

The stack is cheap to use. Allocating a frame is essentially moving a pointer, and popping it is moving the pointer back. But the stack has limits: the size of each frame is known in advance, and the total stack space is limited.

Recursion and the call stack

Recursion is the clearest way to see the call stack at work. A recursive method calls itself, and each call gets its own frame, with its own copy of the parameters and local variables.

Take a method that computes a factorial for positive inputs:

static int factorial(int n) {
    if (n == 1) return 1;          // base case
    return n * factorial(n - 1);
}

When you call factorial(3), the calls do not all run at once. Each one calls the next and waits for it to return:

• factorial(3) is called. A frame is pushed with n = 3. To finish, it needs the result of factorial(2).
• factorial(2) is called. A frame is pushed on top, with n = 2. It needs factorial(1).
• factorial(1) is called. A frame is pushed on top, with n = 1. This is the base case: it returns 1, and its frame is popped.
• factorial(2) resumes, computes 2 * 1 = 2, returns 2, and its frame is popped.
• factorial(3) resumes, computes 3 * 2 = 6, returns 6, and its frame is popped.

At the deepest point, all three frames are on the stack at the same time:

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ factorial(1)  n=1  return 1  (n == 1)       ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌─────────────────────────────────────────────┐
        │ factorial(2)  n=2  waiting for factorial(1) │
        ├─────────────────────────────────────────────┤
        │ factorial(3)  n=3  waiting for factorial(2) │
        └─────────────────────────────────────────────┘

Each frame has its own n, which is why the calls do not interfere with one another. The frames build up until the base case is reached, then unwind in reverse order as each call returns.

This also explains stack overflow. If a recursive method has no base case, or never reaches it, the frames keep getting pushed and none are ever popped. Eventually the stack space runs out, and the program fails with a StackOverflowError.

The heap

The heap holds objects, and it is not tied to method calls. Conceptually, when you write new, the object is created on the heap, and it stays there until it becomes unreachable and the garbage collector reclaims it, regardless of which method created it.

This is the key difference from the stack. An object created inside a method does not disappear when the method returns. It can outlive the call, as long as it remains reachable:

static Employee createEmployee() {
    Employee local = new Employee(1);  // object on the heap; local reference in the stack frame
    return local;                      // return the reference
}

Employee e = createEmployee();         // e refers to the same heap object

When createEmployee returns, its frame is popped off the stack, and the local variable local is gone. But the Employee object on the heap is still reachable, because the reference was returned and is now held by e in the caller. The object outlived the method that created it.

The heap is more flexible than the stack. Objects can have different sizes, their lifetimes can extend beyond the method call that created them, and they can be referred to from many places at once. The cost of that flexibility is that the heap needs separate management to reclaim objects that are no longer reachable — the cleanup that the stack gets for free by popping frames.

Why two regions

A reasonable question is why a program needs both. The stack's automatic lifetime is cheap and safe, but it only works for data whose storage can disappear when the call returns. Two situations do not fit that pattern:

• The data must outlive the method that created it. The createEmployee example returns an object that has to exist after the method returns. A stack frame cannot hold it, because the frame is gone once the method returns.
• The data needs to be shared or to vary in size. Objects can be referred to from several reachable places at once and can have sizes chosen at runtime; tying them to a single frame would not work.

For data that fits the call pattern — ordinary local-variable values and parameters — the stack is ideal, because cleanup is automatic and free. For object data with independent lifetime, the program uses the heap.

C and C++

The stack and the heap are not specific to Java. C and C++ have the same two regions, with the same basic roles: local variables go on the stack, and dynamically allocated memory goes on the heap. There are two differences worth noting.

First, C and C++ let you choose where an object goes. A local struct or object declared in the normal way lives on the stack and is destroyed automatically when it goes out of scope. An object you allocate with malloc (in C) or new (in C++) lives on the heap. In Java you do not make this choice in source code: objects are treated as heap objects in the standard model, and local variables and parameters hold primitive values or references in stack frames.

Second, the heap has to be reclaimed somehow. In C you do it by hand with free. In C++ you usually tie it to scope with destructors and smart pointers. In Java, a garbage collector reclaims heap objects that are no longer reachable. In all three languages, the stack reclaims itself automatically by popping frames.

A caveat

"Objects on the heap, local-variable values in stack frames" is the standard model for reasoning about a Java program, and it is the right model for understanding lifetimes and behavior. But it describes the conceptual runtime model, not a word-for-word rule about how every JVM must represent every value internally. The JVM is allowed to optimize. For example, with a technique called escape analysis, it may avoid a heap allocation, or represent an object as separate pieces, if it can prove the object never escapes the method that created it.

The short version

• The stack holds method-call frames, including local-variable slots and method parameters. Frames are pushed when a method is called and popped when it returns, so stack storage is cleaned up automatically when the call ends. The stack is fast but limited in size.
• The heap holds objects created with new in the standard Java model. Objects live independently of method calls and can outlive the method that created them, for as long as they remain reachable. The heap is flexible but needs separate cleanup.
• A reference-typed local variable has its reference value stored in the stack frame, and that reference points to an object on the heap.
• C and C++ have the same two regions. The main differences are that they let you choose the stack or the heap for an object in source code, and that they reclaim the heap by hand or by scope rather than with a garbage collector.