Memory Layout: Stack, Heap, and Cache Lines

Two programs can perform the same arithmetic and differ by an order of magnitude in runtime. The faster one may not use a cleverer algorithm. It may simply walk contiguous memory while the slower one follows pointers, faults in pages, and makes several CPU cores fight over the same cache line.

“Stack versus heap” is therefore only the entrance to memory layout. A useful model connects source-level lifetimes, an allocator’s blocks, a process’s virtual pages, physical memory, and the cache hierarchy. Each layer has different rules. Confusing them leads to claims such as “stack memory is always in cache” or “a heap allocation is one operating-system allocation.” Neither is generally true.

Virtual memory is the map, not the territory #

Each process normally sees a private virtual address space. An address used by a load instruction is translated through page tables to a physical frame, or to no resident frame yet. The operating system maps executable code, shared libraries, files, anonymous memory, stacks, and allocator arenas into this space. Pages are commonly 4 KiB, but large pages and other page sizes exist.

The translation lookaside buffer, or TLB, caches recent virtual-to-physical translations. A cache hit for data can still require a TLB lookup; a TLB miss can trigger a hardware page-table walk. If no physical page is resident, a page fault enters the kernel. A minor fault may only establish a mapping or provide a zeroed page. A major fault may wait for storage and is vastly more expensive.

This picture is conventional, not a language contract. Address-space layout randomization moves regions; allocators can use many noncontiguous mappings; stacks can have guard pages; and an operating system may overcommit virtual memory. Consequently, virtual size is not resident set size, and neither directly equals the bytes an application considers “live.”

Spatial placement also has a security role. Guard pages catch some stack overflows, non-executable mappings make injected data harder to run, and randomization makes addresses less predictable. These defenses reduce risk but do not make an out-of-bounds access defined or safe.

Stack frames and heap allocations express different lifetimes #

A thread stack supports call discipline. Conceptually, a call pushes a frame containing a return address, saved registers, spill slots, and some local values; return discards that frame in constant time. Real optimized code is less literal: a function may be inlined, a local may live only in a register, and compilers may omit frame pointers or reuse stack slots. Recursion and large local arrays can exhaust the finite stack.

Heap storage supports values whose size or lifetime does not fit lexical call nesting. malloc does not usually ask the kernel for every object. A user-space allocator obtains larger regions, divides them into size classes or runs, and tracks free blocks. Small allocations may come from thread-local caches; large ones may receive dedicated mappings. Allocation can be fast, but metadata, synchronization, fragmentation, and poor locality are still real costs.

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

static long sum_copy(const int *values, size_t count) {
    long total = 0;                 /* Usually a register or stack slot. */
    for (size_t i = 0; i < count; ++i) {
        total += values[i];
    }
    return total;
}

int main(void) {
    const size_t count = 1024;
    int *values = malloc(count * sizeof *values);
    if (values == NULL) return EXIT_FAILURE;

    for (size_t i = 0; i < count; ++i) values[i] = (int)i;
    printf("%ld\n", sum_copy(values, count));
    free(values);
    return EXIT_SUCCESS;
}

Here the pointer variable values has automatic lifetime in main, while the array has allocated lifetime until free. That does not mean the pointer is physically “on the stack”: optimization may keep it in a register. Nor does it mean the array’s pages are resident immediately. Many systems commit physical pages only when code first touches them.

Alignment and padding shape every object #

Processors and application binary interfaces impose alignment requirements. A uint64_t often prefers an address divisible by 8, while a byte has alignment 1. A compiler inserts padding before fields and at the end of a structure so each field is suitably aligned and every element of an array has a valid starting address.

For current offset offset and required alignment A, the bytes inserted before a field are:

padding = (A - (offset % A)) % A
aligned_size = round_up(raw_size, maximum_field_alignment)

For power-of-two A, low-level code often rounds an integer address with (x + A - 1) & ~(A - 1), after checking overflow. That expression is not a substitute for an allocator that promises the required alignment.

Inspect layout rather than guessing it:

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

struct Event {
    uint8_t kind;
    uint64_t timestamp;
    uint8_t active;
};

int main(void) {
    printf("size=%zu align=%zu offsets=%zu,%zu,%zu\n",
           sizeof(struct Event), _Alignof(struct Event),
           offsetof(struct Event, kind),
           offsetof(struct Event, timestamp),
           offsetof(struct Event, active));
}

On a common 64-bit ABI this layout occupies 24 bytes, but the C standard does not guarantee that result. Reordering the two byte fields together often reduces it to 16 bytes on that ABI. Reordering can therefore save memory across millions of elements, but it changes the binary layout. That matters for foreign-function interfaces, persisted records, network protocols, and code that assumes field offsets.

Packed structures remove some padding but can create misaligned loads, slower access, or faults on stricter architectures. They also do not define byte order. Serialize fields explicitly, specify endianness, and treat raw structure dumps as an ABI-dependent format. Rust’s default representation likewise leaves layout choices to the compiler; use #[repr(C)] for a C-compatible field order and #[repr(transparent)] for an appropriate one-field wrapper, then still verify the external contract.

Cache lines reward locality and expose false sharing #

CPUs transfer memory through caches in fixed-size cache lines, commonly 64 bytes on current desktop and server processors but not universally. Reading one byte generally brings its surrounding line into a nearby cache. Hardware prefetchers recognize regular streams, so scanning a contiguous array can approach memory bandwidth while chasing a linked structure stalls on dependent misses.

Two compact estimates help frame an investigation:

working_set_bytes = element_count * bytes_per_element
minimum_lines_touched = ceil(bytes_scanned / cache_line_bytes)

The second is only a lower bound. Strides, alignment, associativity conflicts, page boundaries, and writes can increase traffic. Temporal locality means reusing data before eviction; spatial locality means using neighboring bytes already fetched. Blocking a matrix algorithm into cache-sized tiles improves both without changing its asymptotic complexity.

Multicore coherence adds another concern. Cores generally maintain coherence at cache-line granularity. If two threads update different counters that share one line, ownership repeatedly moves between cores even though the variables are logically independent. This is false sharing.

use std::sync::atomic::{AtomicU64, Ordering};

// Assumes 64-byte separation is appropriate for the deployment target.
#[repr(align(64))]
struct PaddedCounter {
    value: AtomicU64,
}

fn increment(counter: &PaddedCounter) {
    counter.value.fetch_add(1, Ordering::Relaxed);
}

Padding hot per-thread counters can help, but it increases footprint and may waste cache capacity. Relaxed is correct here only when the counter needs atomicity without publishing other memory; stronger synchronization semantics require stronger ordering or locks. Benchmark the actual target, and prefer sharded local counters with occasional aggregation when exact immediate totals are unnecessary.

AoS, SoA, and TypedArrays make access patterns concrete #

An array of structures (AoS) keeps all fields for one entity together. A structure of arrays (SoA) keeps one field across all entities together. AoS works well when each operation consumes most fields of one object. SoA is often better for vectorized loops that read only a subset of fields.

Rust makes the distinction visible without exposing unsafe pointers:

#[repr(C)]
struct Particle {
    x: f32,
    y: f32,
    z: f32,
    mass: f32,
}

struct Particles {
    x: Vec<f32>,
    y: Vec<f32>,
    z: Vec<f32>,
    mass: Vec<f32>,
}

fn advance_x(particles: &mut Particles, velocity_x: &[f32], dt: f32) {
    assert_eq!(particles.x.len(), velocity_x.len());
    for (x, velocity) in particles.x.iter_mut().zip(velocity_x) {
        *x += *velocity * dt;
    }
}

The SoA loop loads only x and velocity_x; y, z, and mass do not occupy cache lines for this operation. That advantage disappears if the next operation immediately needs every field for one particle. Layout should follow dominant queries, not fashion.

JavaScript objects do not promise a C-like byte layout. Engines use shapes, tagged values, pointer compression, and representations that can change after optimization or deoptimization. TypedArray is the tool for explicit dense numeric storage:

const count = 100_000;
const storage = new ArrayBuffer(
  count * 3 * Float32Array.BYTES_PER_ELEMENT,
);
const all = new Float32Array(storage);
const x = all.subarray(0, count);
const y = all.subarray(count, count * 2);
const z = all.subarray(count * 2, count * 3);

for (let index = 0; index < count; index += 1) {
  x[index] += 0.25;
}

const header = new DataView(new ArrayBuffer(8));
header.setUint32(0, count, true); // Explicit little-endian encoding.

The views share one ArrayBuffer; subarray does not copy. Bounds are checked by the JavaScript runtime, but application-level indices still need validation, and a detached or shared buffer has additional rules. Use DataView when a binary format needs explicit endianness or unaligned fields. Use Atomics for synchronization on a SharedArrayBuffer; ordinary concurrent reads and writes are not a substitute for a synchronization protocol.

Garbage collection, profiling, and safety belong in the model #

A garbage-collected runtime changes reclamation, not the cost of layout. Young-generation collectors exploit the observation that many objects die quickly. Bump allocation can be extremely cheap, and copying live objects can compact them. However, a storm of temporary wrappers raises allocation and tracing work; long-lived graphs increase old-generation pressure; references retained by caches keep entire subgraphs alive; and pointers from old objects to young objects require write barriers and remembered sets.

Object pooling is not automatically an improvement. A pool can keep memory live, increase old-generation occupancy, preserve stale state, and defeat a collector already optimized for short-lived objects. Pool only after profiles identify allocation or pause cost, and bound the pool.

Measurements should connect symptoms to a layer:

Start with a representative workload and a release build. On Linux, perf stat can compare cycles, instructions, cache misses, and page faults; perf record plus a flame graph identifies hot call paths. Heap profilers and runtime snapshots show allocation sites and retention paths. Browser performance and memory panels expose GC activity and ArrayBuffer use. Tools such as Valgrind or sanitizers find invalid C accesses, though instrumentation changes timing. Always record CPU model, compiler flags, runtime version, input, and confidence intervals before declaring a layout win.

Finally, performance does not outrank memory safety. C pointer arithmetic outside an object, use-after-free, data races, and reads of uninitialized storage are undefined behavior. Rust’s borrow checker prevents many such errors in safe code, but unsafe, FFI, atomics, and custom allocators restore proof obligations. Typed arrays prevent arbitrary pointer dereferences, not denial-of-service-sized allocations or logical races. Keep ownership explicit, validate arithmetic for overflow, test boundary sizes, and use sanitizers or interpreters designed to catch violations.

Takeaways #

• Virtual addresses are translated in pages; virtual size, resident memory, allocator capacity, and live object size are different measurements.
• Stack frames match nested call lifetimes, while heap allocators manage flexible lifetimes through arenas, size classes, and mappings.
• Alignment and padding are observable ABI properties. Inspect them, and serialize data explicitly instead of dumping structures.
• Cache performance follows temporal and spatial access patterns. Contiguous scans help; pointer chasing and false sharing hurt.
• Choose AoS, SoA, or a hybrid from the fields each hot loop actually consumes. Typed arrays provide explicit numeric storage in JavaScript.
• Garbage collection does not erase allocation, retention, locality, or synchronization costs.
• Profile representative release workloads before changing layout, and never trade away defined behavior or synchronization correctness for a benchmark.