The previous post treated memory as one long row of addresses, and measured how long reading from each level takes. This post shows that row of addresses is a deliberate illusion. The opening experiment:
volatile char *q = malloc((size_t)256 << 30); // 256 GiB
printf("%s\n", q ? "succeeded" : "failed"); // succeeded
On a machine with far less than 256 GiB of RAM, malloc still succeeds, and uses almost no extra RAM at all. To understand why, we need to look at how a program sees memory.
The route: a process's address space, the stack, the heap (and how much a Python list really costs), virtual memory and pages, the price of the first touch, address translation and the TLB, segfaults, then a few practical consequences.
Every number in this post was measured on a real machine, in C (clang) and Python 3.12, single-threaded. The operating system here is macOS; Linux and Windows do the same things with a few differences in the numbers, noted where they matter.
Every program its own world
Print the addresses of four things in a C program: a function, a global variable, a malloc'd block, and a local variable:
int global = 1;
int main(void) {
int local = 2;
int *heap = malloc(sizeof(int));
printf("code (main) %p\n", (void *)main);
printf("global variable %p\n", (void *)&global);
printf("heap (malloc) %p\n", (void *)heap);
printf("stack (local) %p\n", (void *)&local);
}
Run it twice:
run 1 run 2
code 0x104b684f8 0x1005584f8
global 0x104b70000 0x100560000
heap 0x105335c40 0x100aa1c40
stack 0x16b29678c 0x16f8a678c
Two things stand out. First, the regions sit in a familiar layout: code and globals low, the heap above them, the stack far above. Second, the addresses change on every run. The operating system deliberately shuffles where regions go on each run (ASLR, address space layout randomization), so an attacker can't predict where a function or some data will be.
And the most important thing can't be seen in the table: these are all virtual addresses. Two programs running at the same time can both use address 0x100560000, and each sees its own data there. Every process has its own address space; the chip and the operating system together translate virtual addresses into real addresses in RAM.
The stack: fast, self-cleaning, and limited
Every function call needs room for local variables and for the address to return to when the function finishes. That room is a frame on the stack: a region of memory the CPU keeps a register pointing to the top of. Calling a function moves the top down a little (the stack grows from high addresses to low), returning moves it back. Allocating and freeing on the stack is just adding to or subtracting from a register, so it's very fast, and automatic: local variables vanish when the function returns.
The price is that the stack has a fixed size, chosen when the thread is created:
| Stack size | |
|---|---|
The main thread (default limit, ulimit -s) |
8,176 KiB (~8 MiB) |
| A newly created thread (this OS's default) | 512 KiB |
On Linux, new threads usually get 8 MiB too (the post How Python runs concurrent code mentioned that figure). Recursion that goes too deep runs off the end of that region, a stack overflow, and the program is stopped. Python's default recursion limit of 1,000 levels (sys.getrecursionlimit()) is there partly to stop that before it happens to the interpreter's own stack.
The heap: outliving the function that made it
Anything that needs to outlive the function that created it, or whose size is only known at run time, lives on the heap: malloc asks for a block, free gives it back. The allocator has to find a free spot of the right size, remember which blocks are in use, and merge free space back together when blocks are returned; much slower than the stack, but flexible.
In Python, every object lives on the heap. Measuring a list of a million integers with tracemalloc, compared with the standard library's array holding the same numbers as raw 64-bit values:
import array, tracemalloc
tracemalloc.start()
a = [i + 1000 for i in range(1_000_000)]
print(tracemalloc.get_traced_memory()[0]) # bytes in use
| Total | Per number | |
|---|---|---|
A list of ints |
40.4 MB | 40.4 bytes |
array("q", ...) |
8.2 MB | 8.2 bytes |
Each list element costs 8 bytes for the pointer, plus 32 bytes for the integer object (28 real bytes, rounded up by the allocator). Almost 5 times a bare 64-bit number. The previous post showed the second price of storing things this way: the objects are scattered, and walking them out of order is 7.6 times slower.
Virtual memory: malloc is only a promise
The operating system divides memory into fixed-size pages. On this machine a page is 16 KiB; on most x86 machines and Linux it's 4 KiB. For each process, the operating system keeps a page table recording which real RAM page each virtual page maps to, or that it doesn't map to anything yet.
When a program mallocs a big block, the operating system only notes that the address range may be used. It hands out no RAM pages yet. Only when the program touches (reads or writes) a page for the first time does the CPU notice the page isn't in the table, pause the program and tell the operating system: a page fault. The operating system finds a free RAM page, clears it to zero, records it in the page table, then lets the program carry on as if nothing happened.
The experiment: ask for 512 MiB, then touch every page in turn, watching the real memory the process uses (resident) and the page fault count:
volatile char *p = malloc(512u << 20);
for (size_t i = 0; i < size; i += page) p[i] = 1; // first touch: the OS has to find a real page
| When | Real RAM used (peak) | Page faults |
|---|---|---|
| At the start | 1.3 MiB | 289 |
After malloc(512 MiB) |
1.3 MiB | 291 |
| After touching every page | 513.3 MiB | 33,059 |
| After 5 more passes | 513.3 MiB | 33,067 (no increase) |
After malloc(256 GiB) |
513.6 MiB | 33,077 |
| After touching 2 bytes of that 256 GiB | 513.6 MiB | 33,079 |
malloc(512 MiB)costs no extra RAM at all.- Touching every page adds exactly 512 MiB of RAM, and about 32,768 page faults, exactly the number of 16 KiB pages in 512 MiB.
- Later passes cause no more page faults: the pages are real now.
malloc(256 GiB)succeeds, and touching both ends of it costs just two page faults, two pages, 32 KiB of RAM.
The time per page:
| Per page | |
|---|---|
| First touch (with a page fault) | about 1.3–1.6 µs |
| Later touches | 7.5 ns |
The first touch is almost 200 times more expensive: each page fault is a trip into the operating system to find a free page, clear 16 KiB to zero, and update the page table. That's why a program that allocates a big block is often slow the first time it uses it, and why programs that need steady latency (databases, games) often "pre-touch" their memory at startup.
What if a program really touches more pages than there is RAM? The operating system has to reclaim pages from somewhere: compress rarely used pages (macOS does this first), write them to disk (swap), or, on Linux as a last resort, pick a process to kill outright (the OOM killer). malloc's promise is cheap; keeping it isn't.
Address translation and the TLB
On every memory read, the virtual address has to be translated into a real one. The page table is big, and organized in several levels (a table of tables), so looking up one address can take several reads of memory itself. If every data read dragged along several page-table reads, everything would be several times slower.
The answer is, once again, a cache: the TLB (translation lookaside buffer), a very small memory in the CPU holding recently used translations. On a TLB hit, translation is almost free. On a miss, the CPU has to walk the page table itself (a page walk), costing many extra cycles. The TLB only holds so many translations, so the more pages data is spread over, the more often it misses. That's part of the reason the latency in the previous post kept climbing inside the L2 range instead of staying flat: random reads over 16 MiB are spread across 1,024 different pages.
This is also why page size matters. 16 KiB pages mean each TLB entry covers 4 times as much memory as with 4 KiB pages. Systems that use a lot of memory (databases, virtual machines, model training) often also use huge pages (several MiB each) so the TLB covers even more.
Segfaults: touching where you're not allowed
The page table records not only which real page each virtual page maps to, but also permissions: whether the page may be read, written, or run as code. Code is usually readable and runnable but not writable; data is readable and writable but not runnable. Address 0 and the area around it map to no page at all.
When a program touches a page that isn't in the table (never allocated, or already freed and returned), or does something the page's permissions don't allow, the CPU also raises a page fault. But this time the operating system has nothing to "fix", so it stops the program: a segmentation fault. Reading through a NULL pointer is the most common case. The same mechanism keeps processes from reading each other's memory: a process can only touch pages in its own table.
Python almost never segfaults in ordinary code, because it never hands you a raw pointer: every access goes through an object and is checked. When a Python program does segfault, the culprit is almost always an extension written in C.
A few practical consequences
forkis cheap thanks to copy-on-write. Creating a child process doesn't copy all of memory: the two processes share the real pages, marked read-only, and only when one side writes to a page is that page copied. That's the foundation of servers that run many child processes.mmapa file: map the file into the address space, and its pages are only read from disk when touched. That's how large model-weight files (such as the safetensors format in part 2 of the LLM series) can "open" almost instantly: most of the reading is put off until it's actually needed.- Memory "used" is a fuzzy number. Virtual memory (promised), resident memory (backed by real pages), memory shared with other processes: monitoring tools show different numbers, and a process with "256 GiB" of virtual memory may be using only a few MiB.
- Compact data structures save twice.
arrayor NumPy instead of a list of integers saves 5 times the memory, and also means fewer pages, fewer TLB misses and fewer cache misses.
Summary
| Concept | What it really is |
|---|---|
| Address space | Each process has its own row of virtual addresses; ASLR shuffles them on every run |
| Stack | A frame per function call; allocation is one subtraction; ~8 MiB for the main thread, 512 KiB for new threads here |
| Heap | malloc/free; every Python object lives here; an int in a list costs ~40 bytes |
| Page | The unit of virtual memory: 16 KiB here, 4 KiB on most x86 |
malloc |
Only a promise: 512 MiB or 256 GiB costs no RAM until touched |
| Page fault | The first touch: ~1.3–1.6 µs per page, against 7.5 ns afterwards |
| TLB | A cache of address translations; a miss means walking the page table |
| Segfault | Touching a missing page, or without permission; the OS stops the program |
Who keeps the page tables, who handles page faults, who decides which process runs on which CPU core, and who talks to the GPU? The operating system. Next post: the kernel, system calls, scheduling, and why CPUs and GPUs are designed for two very different kinds of work.