What Happens in Memory: guided lesson

the story

Call stack & heap

Every tool here exists because something was too slow or broke without it. Here is what.

1960 · Edsger W. Dijkstra

Early programs gave each subroutine one fixed block of working memory. A subroutine could not be called again before it finished, because the new call would overwrite the old one's data. In "Recursive Programming" (1960), written for ALGOL 60 compilers, Dijkstra kept each call's data on a stack instead: push a fresh area on every call, drop it on return. The JVM works the same way today: every thread has a stack of frames, and objects live on a shared heap.

the problem it solved

Let methods call each other, and themselves, without overwriting each other's local variables, and free that memory the instant a call returns.

why it matters: without it

Without a frame per call, no method could call itself, so no tree DFS and no backtracking. Without a heap, nothing could outlive the method that made it: no linked lists, no HashMaps.

sources: E. W. Dijkstra, "Recursive Programming", Numerische Mathematik 2 (1960) ↗ · JVM Specification (Java SE 17), §2.5 Run-Time Data Areas and §2.6 Frames ↗ · The java command (JDK 17): -Xss default thread stack size ↗

also in this chapter: References & pass-by-value · Fixed-width integers & overflow · Garbage collection

the idea

The idea in 30 seconds

Every method call gets a frame on the call stack for its parameters and local variables. The frame disappears when the method returns.

Every object you create with new, every array included, lives on the heap. A variable of object type holds only a reference: an arrow to it.

Java always copies the value into a parameter. For an object, that value is the arrow, so a method can change the object but never the caller's variable.

picture this

Desktop shortcuts in Windows: the shortcut (a reference in your frame) is tiny and points at a real folder (the object on the heap). Copy the shortcut and both copies open the same folder, so a file added through one shows up in the other. Deleting a shortcut never deletes the folder.

watch it

Call stack and heap, frame by frame

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Call stack and heap, frame by frame

Boxes on the left are frames and their variables, spheres on the right are heap objects, arrows are references. Watch the array outlive the method that made it.

loading simulation…

javajava.util.*

1static int[] makeArray(int n) {2    int[] arr = new int[n];                  // the array object lives on the heap3    for (int i = 0; i < n; i++) {4        arr[i] = (i + 1) * 10;5    }6    return arr;                              // hands back the reference, not a copy7}8 9static int sum(int[] a) {10    int total = 0;                           // a primitive: stored inside sum's frame11    for (int x : a) {12        total += x;13    }14    return total;                            // sum's frame is thrown away after this15}16 17static int run(int n) {18    int[] data = makeArray(n);19    int[] alias = data;                      // copies the arrow, not the array20    alias[0] = 99;                           // so data[0] is 99 now too21    return sum(data);22}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

watch it

Pass-by-value: swap fails, arr[i] = … works

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Pass-by-value: swap fails, arr[i] = … works

swap gets copies of two numbers. swapInArray gets a copy of an arrow to the caller's array. reassign repoints only its own arrow.

loading simulation…

javajava.util.*

1static void swap(int a, int b) {             // a and b are COPIES of the caller's ints2    int t = a;3    a = b;4    b = t;                                   // only the copies are swapped5}6 7static void swapInArray(int[] arr, int i, int j) {   // arr is a copy of the REFERENCE8    int t = arr[i];9    arr[i] = arr[j];10    arr[j] = t;                              // writes into the caller's array object11}12 13static void reassign(int[] arr) {14    arr = new int[] {0, 0};                  // points the local copy at a NEW array15    arr[0] = -1;                             // the caller never sees this array16}17 18static String demo(int x, int y) {19    swap(x, y);20    int[] nums = {x, y};21    swapInArray(nums, 0, 1);22    reassign(nums);23    return x + " " + y + " " + Arrays.toString(nums);24}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

key idea 1 of 8