Computer memory model

Every method call pushes a stack frame holding its parameters, local variables, a link to the caller and the return address. Primitives live directly in the frame; for objects the frame holds only the reference. When the method returns, its frame disappears and the memory is reused immediately.

Frames are cheap to create, but each one counts toward the depth limit of the thread's stack.

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case
3    return n * factorial(n - 1);       // recursive case
4}

Objects and arrays are allocated on the heap, shared by all threads, and live until the garbage collector finds them unreachable. Allocation is fast (a pointer bump in the young generation), but heap objects need headers, references to reach them and the collector's attention.

Locals that point to heap objects are references; the object may outlive the method if another reference keeps it.

1int x = 5;                    // primitive: stored in the stack frame
2int[] a = new int[1000];      // reference in the frame, 1000 ints on the heap
3List<Integer> xs = new ArrayList<>();   // reference + ArrayList object + backing Object[]

The call stack is the chain of active frames, from main to the method running now. Recursion adds one frame per call, and the stack unwinds as calls return. A StackOverflowError means the chain exceeded the stack's size, usually because of a missing base case or a recursion deeper than about 10⁴ to 10⁵ frames.

Stack traces print this chain, innermost call first.

1static int depth(int n) { return depth(n + 1); }   // no base case
2// depth(0) -> StackOverflowError after roughly 10,000-20,000 frames with the default stack

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case
3    return n * factorial(n - 1);       // recursive case
4}

A reference is a small value (4 bytes with compressed object pointers) that identifies an object. Assigning a reference copies the address, not the object, which is why aliasing happens and why a List<Integer> costs a reference plus an Integer object per element.

Step through the alias, clone and deep-copy cases to see where references are shared.

1int[] a = { 10, 20, 30, 40 };               // options 0 and 1 use this 1D array
2int[] b = a;                                // option 0: copies the reference only
3int[] b = a.clone();                        // option 1: copies the elements
4int[][] a2 = { { 10, 20 }, { 30, 40 } };    // options 2 and 3 use this 2D array
5int[][] b2 = a2.clone();                    // option 2: new outer array, SAME row objects
6int[][] b2 = Arrays.stream(a2).map(int[]::clone).toArray(int[][]::new);   // option 3: rows copied too
7b[idx] = v;                                 // (b2[0][idx] = v for options 2 and 3)
8System.out.println(Arrays.toString(a));     // does a see the change?

Every object starts with a header: a mark word (identity hash, lock and GC bits) and a class pointer, 12 bytes on a 64-bit HotSpot JVM with compressed class pointers. Arrays add a 4-byte length for a 16-byte header. Object sizes are rounded up to a multiple of 8 bytes, so tiny objects have large overhead.

That is why an int[] of one million ints takes about 4 MB while a List<Integer> of the same values takes about 20 MB.

The garbage collector reclaims heap objects that are no longer reachable from any live reference. Most objects die young, so the heap is split into young and old generations: minor collections clean the young generation quickly, and rarer major collections handle the old one. Collectors (G1, ZGC, Parallel) trade pause time against throughput.

For algorithm code the practical rule is to avoid allocating in hot loops. See the Java architecture chapter for the collectors in detail.

Memory is read in blocks. Accessing data close in memory (spatial locality) or reusing recently used data (temporal locality) is fast, because it is already in the cache. Walking a 2D array row by row reads consecutive addresses; walking column by column jumps a whole row each step.

The simulator below uses 4-int lines and a small LRU cache so you can count hits and misses for row-major versus column-major order.

1int sumRowMajor(int[][] m) {                  // inner loop walks along a row
2    int sum = 0;
3    for (int r = 0; r < m.length; r++)
4        for (int c = 0; c < m[0].length; c++) sum += m[r][c];
5    return sum;
6}
7int sumColumnMajor(int[][] m) {               // inner loop jumps down a column
8    int sum = 0;
9    for (int c = 0; c < m[0].length; c++)
10        for (int r = 0; r < m.length; r++) sum += m[r][c];
11    return sum;
12}

CPUs have small, fast caches between the cores and main memory: typically L1 (tens of KB, about 1 ns), L2 (hundreds of KB to a few MB, a few ns), and a shared L3 (many MB, ten-odd ns), against about 100 ns for main memory. A miss at every level costs roughly a hundred times a hit in L1.

Exact sizes and latencies vary by processor, but the ratios are what matter for algorithm design.

Data moves between memory and cache in cache lines, typically 64 bytes: 16 ints or 8 longs. Reading a[0] loads a[0..15] together, so the next 15 reads are free hits. A linked list node is a separate object, so each hop may load a new line.

Structure data so values used together sit next to each other; arrays of primitives are the most cache-friendly layout Java offers.

1int n = 4096; int[][] m = new int[n][n]; long s = 0;
2for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) s += m[r][c];   // row order: sequential access
3for (int c = 0; c < n; c++) for (int r = 0; r < n; r++) s += m[r][c];   // column order: a new line each step

1int sumRowMajor(int[][] m) {                  // inner loop walks along a row
2    int sum = 0;
3    for (int r = 0; r < m.length; r++)
4        for (int c = 0; c < m[0].length; c++) sum += m[r][c];
5    return sum;
6}
7int sumColumnMajor(int[][] m) {               // inner loop jumps down a column
8    int sum = 0;
9    for (int c = 0; c < m[0].length; c++)
10        for (int r = 0; r < m.length; r++) sum += m[r][c];
11    return sum;
12}