Workspace

Stack, heap, pointers and alignment

3 day streakD

Stack, heap, pointers and alignment

Where values live decides how fast you can reach them and how long they survive. Learn the two regions, and why struct field order changes its size.

BasicsLesson 3 of 613 min

A running program has two main places for data. The stack holds function frames: local variables, arguments and the return address. It grows and shrinks with calls, so allocation is just moving a pointer, and memory is freed the instant a function returns. The heap holds data whose size or lifetime is not known in advance. It needs an allocator, and in managed languages a garbage collector.

Figure 3.1

Frames on the stack, objects on the heap

Stack and heapThe stack holds three frames: main, runTurn and parseToolResult. Locals in runTurn and parseToolResult point to a messages array and a result object on the heap. Below, a struct with fields char, int32 and char uses 12 bytes with padding, while the reordered struct uses 8.Stack · grows downHeap · managed by the allocator or GCmain()argvrunTurn()turn = 7messages ●parseToolResult()raw ●result ●← topmessages: Array(42)[ptr, ptr, ptr, …]raw: string2.1 MB of tool outputresult: objectsurvives the returnField order changes sizek···ttttd···char · int32 · char = 12 bytesttttkd··int32 · char · char = 8 bytesk = kind (char) · t = tokens (int32) · d = done (char) · dot = padding byte
Each call pushes a frame. Locals that hold objects are pointers into the heap. When parseToolResult returns, its frame is gone, but the heap object it built stays alive as long as something still points to it.

Pointers are addresses

A pointer is a number: the address of another value. Following one is called dereferencing. Every dereference may jump to a distant part of memory. A linked list, a tree or a JavaScript object graph is a chain of these jumps, which is why they can be much slower to walk than an array of the same size. The next lessons explain the cost.

In JavaScript, Python and Java, almost every object is a heap allocation reached through a pointer. An array of numbers in V8 may be stored unboxed and contiguous, while an array of objects is an array of pointers to objects scattered around the heap.

Alignment and padding

CPUs read memory fastest when a value of size n sits at an address divisible by n. Compilers insert padding to make that true. Field order therefore changes the size of a struct.

padding.cC
#include <stdio.h>
#include <stdint.h>

struct Wasteful { char kind; int32_t tokens; char done; };   // 1 + 3 pad + 4 + 1 + 3 pad
struct Compact  { int32_t tokens; char kind; char done; };   // 4 + 1 + 1 + 2 pad

int main(void) {
  printf("%zu %zu\n", sizeof(struct Wasteful), sizeof(struct Compact)); // 12 8
}

A million of these is 12 MB versus 8 MB, and 50% more cache lines to read.

Where you will meet it

Stack overflow

Deep recursion on a large tree, or a recursive JSON walker on hostile input, can exhaust a thread's stack. Production parsers use explicit stacks on the heap.

Columnar data

Arrow and Parquet store each field in its own contiguous array. Scanning one column then touches only the bytes it needs (Module 7).

Game engines

Entity-component systems keep components in packed arrays rather than object graphs, purely for cache behaviour.

Check yourself

Answer out loud before you open each one.

What happens to a local variable's stack memory when its function returns?

The frame is popped. The memory is reused by the next call, so pointers to it become dangling.

Why might struct { char a; int b; char c; } take 12 bytes?

b must start at a multiple of 4, so 3 padding bytes follow a. The struct's size rounds up to a multiple of 4, adding 3 more after c.

Why is an array of objects slower to scan than an array of numbers?

Each element is a pointer to a separate heap object, so every access may land on a different, uncached part of memory.

Try it

In Node, compare process.memoryUsage().heapUsed after creating 1,000,000 { a: i, b: i } objects against one Float64Array of 2,000,000 values. Explain the gap.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap