From malloc to Cache Lines
An allocation call returns a pointer, but between that call and a cache line being filled sit an allocator, a virtual address space, a page fault, a physical frame chosen by the kernel and finally the hardware that transfers the line. Each layer shapes where your data lands, which is why allocation pattern becomes cache behaviour.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The path from a call to a cache line
The allocator maintains free lists and size classes over regions it has obtained from the operating system. A request is satisfied from an existing region if one fits, which is fast and involves no kernel interaction at all; otherwise it asks the OS for more address space. Crucially, this means most allocations never touch the kernel, and the addresses returned are determined by the allocator's bookkeeping — its size classes, its free-list ordering, its per-thread caches.
Obtaining address space is not the same as obtaining memory. A fresh mapping is typically not backed by physical frames; the first *access* to a page triggers a fault, and the kernel then allocates a physical frame and installs the mapping (The Page-Table Walk: Dependent Loads All the Way Down, and the OS side in page-faults). This is first touch, and it is the moment that decides which physical memory — and on a multi-socket machine, which NUMA node — your data lives in.
Only then does the hardware story begin. The physical address determines which cache sets the data maps to (Tag, Index and Offset: How an Address Finds Its Line), the line size determines how much arrives with it (Memory Moves in Lines, Not Variables), and the allocator's adjacency decisions determine whether the next object you touch shares that line or is somewhere else entirely.
Why allocation pattern becomes cache behaviour
Consider building a linked list of a million nodes by allocating each node individually. In a freshly-started program the allocator may hand back near-contiguous addresses and the traversal will be far better than the data structure deserves. In a long-running program with a fragmented heap, the same code produces nodes scattered across the address space, and traversal becomes the pointer-chasing worst case (Pointer Chasing: The Address You Do Not Have Yet). The source is identical; the performance is not, and the difference is allocation history.
This is the strongest practical argument for arena or pool allocation in hot paths. Allocating a block once and carving objects from it guarantees adjacency, eliminates per-object allocator overhead, and makes bulk deallocation a single operation. The costs are real: you give up individual free, you must manage lifetime as a group, and you can waste memory if the arena is oversized. It is a hot-path technique, not a default.
The same reasoning explains why std::vector-style contiguous containers routinely outperform node-based ones for iteration even when the node-based structure has better asymptotic behaviour for the operation being measured (Both Are O(n). One Is Far Slower.) — and why a language that boxes every element gives you an array of pointers rather than an array of values, silently converting a contiguous traversal into a pointer chase.
1for i in 0..n:2 node = allocate(sizeof(Node)) // wherever the free list points3 node.value = data[i]4 append(list, node)5 6// Adjacency: none guaranteed7// Traversal: a dependent miss per node8// Gets worse as the process ages and the heap fragments1arena = allocate(n * sizeof(Node)) // one call2for i in 0..n:3 node = &arena[i] // guaranteed adjacent4 node.value = data[i]5 append(list, node)6 7// Adjacency: guaranteed by construction8// Traversal: prefetchable, several nodes per line9// Free: one operation for the whole arenaSame structure, same logic, same asymptotic behaviour. The arena version guarantees the adjacency that the per-node version can only hope for, so the traversal gets spatial locality and prefetching instead of a dependent miss per node. The trade is that individual nodes can no longer be freed independently.
First touch, NUMA and the thread that allocates
On a multi-socket machine the first-touch rule has a consequence that surprises people regularly: memory is placed near the thread that first writes to it, not the thread that allocates it. A common pattern — a single initialisation thread allocating and zeroing a large array, then worker threads spread across sockets processing it — places the entire array on one node. Every worker on the other socket then pays remote access cost for the whole run (NUMA: Not All Memory Is Equally Far).
The fix follows directly from the mechanism: have each worker thread first-touch the region it will later process, so the pages land on its own node. This is a small change with a large effect on large multi-socket machines, and it is invisible in the source unless you know the rule exists.
The related trap is that the same address space can behave differently at different times. A page that has been swapped or migrated may be backed by a different frame than it was; a program that measured well immediately after a fresh allocation may measure differently once the heap has aged. This is one more reason performance conclusions from a short, freshly-started benchmark process do not necessarily transfer to a long-running service (Every Way a CPU Microbenchmark Lies).
- Allocation returns address space — physical memory is committed later, on first touch.
- First touch decides placement — including which NUMA node, which is why the initialising thread matters.
- Adjacency comes from the allocator — and degrades as the heap fragments over a process's lifetime.
- Arenas buy guaranteed adjacency — at the cost of individual free and group lifetime management.
- Benchmarks on fresh heaps flatter you — a long-running process allocates from a very different landscape.
Key points
- Allocation returns virtual address space; physical frames are committed on first touch, which is a separate and later event.
- First touch decides physical placement, including NUMA node — so the thread that writes first, not the one that allocates, determines locality.
- The allocator's bookkeeping determines adjacency, and adjacency degrades as a long-running heap fragments.
- Arena and pool allocation buy guaranteed adjacency and cheap bulk free, at the cost of individual deallocation.
- Identical source can perform very differently depending on allocation history, which is why fresh-process benchmarks mislead.
Struct Layout & Padding
Change an input and watch which number moves — and which one refuses to.
Each field must sit at an address that is a multiple of its size, so the compiler inserts padding to get there. Twenty-four bytes to hold fourteen bytes of data, and in an array of a million records that is ten megabytes of nothing.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Request → allocator: a size class and free list produce an address, usually with no kernel involvement at all.
- 2Address → virtual page: the address falls in a mapped region that may not yet be backed by physical memory.
- 3First access → page fault: the hardware faults, and the kernel allocates a physical frame and installs the mapping.
- 4Frame → NUMA node: on a multi-socket machine the frame is normally taken from the node of the faulting thread (NUMA: Not All Memory Is Equally Far).
- 5Physical address → cache set: the address determines which set the line maps to, and the line brings in its neighbours (Tag, Index and Offset: How an Address Finds Its Line, Memory Moves in Lines, Not Variables).
- • "malloc gives me memory" — it gives address space; memory arrives on first touch, which may be much later and elsewhere.
- • "The allocator is fast, so allocation is cheap" — the direct cost is usually small; the layout it produces is the expensive part.
- • "The array is contiguous because I allocated it in a loop" — consecutive allocations are not guaranteed adjacent, especially on an aged heap.
- • "NUMA placement follows the allocating thread" — it follows the first thread to touch the page, which is often a different one.
Consequences, controls and cost
- • A structure built early in a process can traverse far better than the identical structure built later on a fragmented heap.
- • Single-threaded initialisation of a shared array places it on one NUMA node, penalising every worker elsewhere for the program's lifetime.
- • Allocation-heavy code pays not only allocator time but the cache effects of the layout it produces.
- • Benchmarks run in short-lived processes systematically overstate the locality a long-running service will have.
- • Allocate hot data structures in one block — arena, pool or a reserved contiguous container — so adjacency is guaranteed rather than hoped for.
- • First-touch from the thread that will process the data on multi-socket machines, so pages land on the right node.
- • Reserve capacity up front for growable containers to avoid repeated reallocation and the fragmentation it causes.
- • Reduce allocation count in hot paths; each one costs allocator work and dilutes locality.
- • Benchmark in a process whose heap resembles production, not a freshly-started one.
- • Compare cache miss rates for the same traversal built with per-object allocation versus an arena.
- • Check NUMA locality counters, or measure remote-access ratios, to confirm pages landed on the expected node.
- • Watch resident set against allocated size to see how much address space has actually been touched.
- • Run the benchmark in a long-lived process with a realistically aged heap and compare against the fresh-process result.
- • Arena allocation forfeits individual free, so lifetimes must be managed as a group and misuse leaks the whole arena.
- • Reserving capacity up front trades memory footprint for locality and fewer reallocations.
- • First-touch discipline complicates initialisation code and couples it to the threading model.
- • Custom allocators add complexity, are easy to get subtly wrong, and must be justified by measurement.
Scope
§224 — what these claims are specific to.
- PLATFORM-SPECIFICDemand paging and first-touch NUMA placement are common operating-system policies rather than hardware guarantees; the specific behaviour, and whether interleaving or migration is enabled, depends on the OS and its configuration.
- GENERALThe layered path — allocator chooses an address, kernel chooses a frame, hardware transfers a line — holds on any system with virtual memory and a general-purpose allocator.
- SIMPLIFIEDReal allocators are considerably more elaborate than size classes and free lists, with per-thread caches, multiple arenas and size-dependent strategies that change the adjacency outcome.
Misconceptions
Apply it
Where the rest of this lives
A runtime with a moving collector changes object addresses during execution, and a language that boxes elements turns an "array of objects" into an array of pointers — both of which override the layout reasoning here in ways the source does not show.