Caches Deep Dive: Associativity & Coherence

The CPU never fetches a single byte from main memory. Instead, it always fetches a contiguous aligned block called a cache line (also called a cache block). On virtually every x86, x86-64, ARM, and RISC-V processor you will encounter today, a cache line is 64 bytes — eight 64-bit words, all at once.

Why 64 bytes? Two reasons. First, DRAM burst mode: DRAM controllers are optimized to stream contiguous data much faster than random single-byte accesses, so fetching 64 bytes costs only marginally more than fetching 8. Second, spatial locality: if your code reads array[0], it is very likely to soon read array[1] through array[7] — prefetching the whole line turns those future accesses into cache hits for free.

The implication is fundamental: the unit of cache pollution is 64 bytes. If you have a hot struct field and a cold field packed together, every access to the hot field loads the cold field into the cache too, wasting precious cache capacity. The kernel uses __cacheline_aligned to force a struct — or a critical field — to start on a 64-byte boundary, preventing two logically independent objects from sharing a line.

You can query the line size on Linux:

cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size

The output will almost certainly be 64.

A concrete C example showing the effect: iterating over a struct array in field order versus strided order can produce 4-8x throughput differences purely due to cache line utilization.

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

// Each element is exactly 64 bytes = one cache line
typedef struct {
    uint64_t hot;          // frequently accessed field
    uint64_t padding[7];   // cold data — occupies rest of line
} __attribute__((aligned(64))) CacheFriendly;

// Check line size at runtime (Linux)
void print_line_size(void) {
    FILE *f = fopen(
        "/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size",
        "r");
    if (!f) { perror("open"); return; }
    int sz;
    fscanf(f, "%d", &sz);
    fclose(f);
    printf("L1 cache line size: %d bytes\n", sz);
}

A cache holds far less data than main memory, so the hardware needs a fast rule: given a main-memory address, which cache slot(s) can hold it?

Address decomposition is the key. For a cache with S sets, E lines per set (ways), and B-byte lines:

• The block offset (low log2(B) bits) selects a byte within the cache line. For 64-byte lines, this is bits [5:0].
• The set index (next log2(S) bits) selects which set to look in.
• The tag (remaining high bits) is stored alongside the data to identify which memory block occupies a given slot.

Direct-mapped (E=1): Every memory address maps to exactly one cache set, and that set holds exactly one line. Lookup is O(1) and requires only one tag comparison. The fatal flaw: two hot addresses that map to the same set (they differ only in the tag bits, sharing the same set index) will thrash — each access evicts the other. Classic example: two arrays whose sizes are multiples of the cache size, accessed alternately.

Set-associative (E=2,4,8...): Each set holds E lines (E "ways"). A given address can live in any of the E slots within its set. The hardware compares all E tags in parallel (E comparators, one per way). 4-way or 8-way set-associative is the dominant design for L1 and L2 caches. It dramatically reduces conflict misses at modest hardware cost.

Fully associative: A given address can go anywhere in the cache. Requires comparing all tags simultaneously — expensive for large caches, practical only for small TLBs and victim caches.

Example: a 32 KiB, 8-way set-associative, 64-byte-line L1D cache (common on x86):

• Lines per set E = 8
• Total lines = 32768 / 64 = 512
• Sets S = 512 / 8 = 64
• Set index = log2(64) = 6 bits → bits [11:6]
• Block offset = log2(64) = 6 bits → bits [5:0]
• Tag = bits [63:12] (for a 64-bit address)

When the CPU issues a load, it extracts the set index, reads all 8 tag+valid pairs in that set in parallel, checks for a match — all in ~4 cycles.

// Visualise address decomposition for a 32KiB 8-way 64B-line cache
#include <stdio.h>
#include <stdint.h>

#define LINE_BITS  6   // log2(64)
#define SET_BITS   6   // log2(64 sets)
#define TAG_SHIFT  (LINE_BITS + SET_BITS)

void decode(uint64_t addr) {
    uint64_t offset = addr & ((1 << LINE_BITS) - 1);
    uint64_t set    = (addr >> LINE_BITS) & ((1 << SET_BITS) - 1);
    uint64_t tag    = addr >> TAG_SHIFT;
    printf("addr=0x%016lx  tag=0x%lx  set=%2lu  offset=%2lu\n",
           addr, tag, set, offset);
}

int main(void) {
    decode(0x0000000000000000UL);
    decode(0x0000000000001000UL);  // same set, different tag
    decode(0x0000000000000040UL);  // next cache line, same set
    decode(0x0000000000000FFFul);  // last byte of set 63
    return 0;
}

When a cache miss occurs in a set that is already full, the hardware must evict one existing line to make room. The eviction policy determines which line is sacrificed.

Least Recently Used (LRU): Evict the line accessed longest ago. Optimal for typical temporal-locality workloads. Tracking true LRU requires log2(E!) state bits per set — expensive for E=8 or more. True LRU is used in some small caches (e.g., TLBs) but rarely in large data caches.

Pseudo-LRU (PLRU or Tree-PLRU): A binary-tree approximation. For E=8 ways, a 7-bit binary tree tracks "recently used" direction at each node. Only 7 bits vs. 56 for true LRU. The error rate is very low in practice. Most modern x86 L1/L2 caches use some form of PLRU.

Random replacement: Pick a victim at random. Surprisingly competitive with LRU for large caches and avoids the pathological thrashing that LRU can exhibit with access patterns that cycle through (N+1) distinct lines in a cache of N lines ("LRU thrashing"). ARM Cortex-A cores commonly use pseudo-random replacement in L2.

Not Recently Used (NRU) / Clock: A single "recently used" bit per line. When evicting, scan for a line with the bit clear; if none, clear all bits and retry. The hardware equivalent of the OS clock page replacement algorithm.

Belady's Optimal (OPT): Evict the line whose next use is furthest in the future. Unimplementable in hardware (requires knowing the future) but useful as a theoretical upper bound in cache simulation. If your measured miss rate is within 10% of OPT, your replacement policy is good.

For kernel developers, the replacement policy is mostly opaque — you cannot control it directly. But understanding it explains why benchmark results can vary depending on access patterns and why "warming up" a cache matters in microbenchmarks.

When the CPU writes to a cached address, the hardware must decide what to do with main memory.

Write-through: Every store immediately propagates to main memory (or the next cache level). The cache and memory are always consistent. Simple, but every store pays the full memory latency. Write-combining buffers can batch consecutive stores to the same cache line, but write-through is rarely used for L1D in modern CPUs because it wastes bus bandwidth.

Write-back (WB): Stores go only to the cache. The line is marked dirty with a special bit. The dirty line is written back to memory only when it is evicted. This is the dominant policy for L1/L2/L3 on all modern CPUs. It can reduce memory bus traffic by 5-10x because multiple stores to the same cache line coalesce into a single writeback.

The tradeoff: with write-back, a cache line can hold data not yet reflected in memory. This requires the write-allocate policy: on a write miss, fetch the whole line from memory into the cache, then modify it in place (so you can track the dirty bit). Without write-allocate, you would have to write a partial line back without a full copy — messy.

Write-no-allocate (streaming stores): A special case for write-only data. The CPU issues a "non-temporal store" that bypasses the cache entirely and goes straight to memory (or a write-combining buffer). Used in memset, GPU framebuffer writes, and kernel memory initialization (clear_page). In x86 this is movnti/movntps; in ARM it is cache-bypassing store instructions.

Kernel relevance: the arch/x86/lib/clear_page_*.S and copy_page routines switch between streaming stores and cached stores depending on the size — a direct expression of these trade-offs.

A write miss with write-back+write-allocate:

1. CPU stores to address A (miss)
2. Cache fetches line containing A from memory
3. CPU modifies the word in the cache line
4. Line is marked dirty
5. Eventually, the line is evicted — hardware writes the dirty line back to memory

// Demonstrate non-temporal (streaming) stores vs. regular stores
// Compile: gcc -O2 -msse4.1 -o wt_demo wt_demo.c
#include <string.h>
#include <stdint.h>
#include <immintrin.h>

#define N (1 << 24)   // 16 million bytes
static char buf[N] __attribute__((aligned(64)));

// Regular write-back store (goes through cache)
void fill_cached(char *dst, int len) {
    memset(dst, 0xAB, len);   // will cache the data
}

// Non-temporal store — bypasses cache (streaming)
void fill_streaming(char *dst, int len) {
    __m128i val = _mm_set1_epi8(0xAB);
    for (int i = 0; i < len; i += 16)
        _mm_stream_si128((__m128i*)(dst + i), val);
    _mm_sfence();   // ensure visibility
}

int main(void) {
    fill_streaming(buf, N);   // faster when buf >> LLC size
    return 0;
}

Every cache miss belongs to exactly one of three categories, a taxonomy first formalized by Mark Hill in 1987. Understanding which type of miss dominates is the first step in fixing a cache performance problem.

Compulsory (Cold) Misses: The first time a cache line is ever accessed, it must be fetched from memory regardless of cache size or associativity. These misses are unavoidable unless you prefetch. In a streaming algorithm that reads every byte of a large array exactly once, 100% of misses are compulsory. Hardware and software prefetching (__builtin_prefetch in GCC, PREFETCHNTA in x86 asm) directly target these.

Capacity Misses: Occur because the cache is too small to hold all the data the working set needs. If you increase the cache to infinity, these misses disappear. Detected by running the same workload on a fully-associative cache of varying sizes and measuring when the miss rate flattens. A workload with a 10 MiB hot working set on a CPU with 4 MiB L3 will have heavy capacity misses.

Conflict Misses: Occur because multiple addresses compete for the same cache set, even when there is plenty of total capacity. These are the treacherous ones — they can be eliminated by increasing associativity or by padding/aligning data. A classic example: a loop accessing A[0], B[0], A[0], B[0] where A and B map to the same set in a direct-mapped cache will miss every single access despite the working set fitting easily in the cache. Increasing to 2-way set-associative would eliminate all misses.

A fourth category sometimes added: Coherence (Communication) Misses — caused by another core invalidating a line via the cache coherence protocol. These are the "fourth C" in multiprocessor systems and are discussed in the MESI section below.

To measure miss types on Linux:

perf stat -e L1-dcache-load-misses,L1-dcache-loads ./your_program

For detailed breakdown, valgrind --tool=cachegrind simulates a specific cache configuration and annotates misses per source line.

// Trigger conflict misses in a direct-mapped cache
// Two arrays whose size is a power of 2 and a multiple of L1 size
// will map to the SAME sets, thrashing a direct-mapped cache.
#include <stdint.h>
#include <stdio.h>

#define L1_SIZE  (32 * 1024)   // 32 KiB
#define N        (L1_SIZE / sizeof(uint64_t))

static uint64_t A[N];  // A[i] and B[i] map to the same set!
static uint64_t B[N];  // They are L1_SIZE bytes apart

void conflict_demo(void) {
    uint64_t sum = 0;
    for (int i = 0; i < N; i++) {
        sum += A[i];   // load A[i] -> evicts B[i] from cache
        sum += B[i];   // load B[i] -> evicts A[i] from cache
    }
    (void)sum;
}
// Fix: pad A or B by one cache line to shift its set index

Modern CPUs have multiple levels of cache, each trading size for speed. The hierarchy is a fundamental architectural feature, not an implementation detail.

L1 Cache (Split I$ and D$): Typically 32-64 KiB per core, 4-way or 8-way set-associative, 4-cycle latency. Split into separate instruction cache (L1I) and data cache (L1D) to allow simultaneous instruction fetch and data access without port conflicts. Every core has its own private L1.

L2 Cache (Unified): Typically 256 KiB – 1 MiB per core, 8-way or 16-way, 12-20 cycle latency. Unified (holds both instructions and data). Still private to each core on most modern designs (Intel, AMD Zen). Acts as a victim cache for L1 — lines evicted from L1 often land in L2.

L3 Cache (Last Level Cache, LLC): Typically 8-64 MiB, shared across all cores on a die, 30-50 cycle latency, often 16-way or higher associativity. The LLC is the last line of defense before a request goes to DRAM (200+ cycles). On NUMA systems, an LLC miss may go to a remote NUMA node's DRAM, adding another 100+ cycles.

Inclusion/Exclusion policies:

• Strictly inclusive LLC: Every line in L1 or L2 is also in LLC. Simplifies coherence (to snoop for a line, check only LLC). Wastes LLC capacity. Used historically by Intel.
• Non-inclusive (NINE): LLC holds only lines that have been evicted from lower levels. More efficient use of LLC capacity. AMD Zen uses NINE L3.
• Exclusive: A line exists at exactly one level. Maximizes total effective cache capacity (L1 + L2 + L3 never duplicate). Used in some embedded and AMD older designs.

The kernel's CONFIG_L1_CACHE_SHIFT and CONFIG_X86_L1_CACHE_SHIFT expose these parameters, and arch/x86/include/asm/cache.h defines L1_CACHE_BYTES which is used throughout the kernel to align critical structures.

On Linux you can inspect the full hierarchy:

ls /sys/devices/system/cpu/cpu0/cache/
# index0=L1D, index1=L1I, index2=L2, index3=L3
cat /sys/devices/system/cpu/cpu0/cache/index3/size

When multiple CPU cores each have their own private caches and all share the same main memory, a terrifying problem arises: Core 0 reads X (value 5) into its L1 cache. Core 1 also reads X (value 5) into its L1 cache. Core 0 writes X = 7 in its cache. Core 1 still sees 5. Which value is correct? Without a coherence protocol, both are "correct" according to each core's private view, which is a recipe for subtle, non-reproducible bugs.

The MESI protocol solves this with four line states:

• M (Modified): This core has the only valid copy, and it has been written (dirty). Main memory is stale. No other core has this line. The owning core must write the line back to memory (or forward it directly) before any other core can use it.
• E (Exclusive): This core has the only copy, and it is clean (matches memory). No other core has it. Can be promoted to M on a write without any bus transaction — silent upgrade.
• S (Shared): Multiple cores may have read-only copies of this line. The line matches memory. Any core that wants to write must first invalidate all other copies (broadcast an "invalidation" message), transitioning its own copy to M.
• I (Invalid): This line is not present in this cache, or has been invalidated. Any access generates a miss.

The protocol is enforced by the cache coherence interconnect (a snooping bus on older designs; a directory-based system on modern many-core CPUs). Every cache monitors ("snoops") bus transactions for addresses it holds.

Typical MESI transitions:

• Cold read: I → E (if only requester wants it) or I → S (if another core already has it)
• Another core reads your E line: E → S (and their copy arrives as S)
• Write to a shared line: broadcast "invalidation"; other cores I their copies; your S → M
• Another core reads your M line: you write back to memory or forward; M → S

This protocol guarantees sequential consistency per cache line — all cores agree on the sequence of values for any given address. It is the hardware foundation on which std::atomic and Linux's memory barriers are built.

AMD's protocol extends MESI to MOESI (adding Owned state, allowing dirty sharing without writeback). ARM uses a variant called MOESI or MEI depending on the microarchitecture. The fundamental mechanism is the same.

// Demonstrate MESI transitions via perf (Linux)
// On a 2-core machine, this causes S->I->M transitions on the shared line

// Thread 0: repeatedly reads shared_var (holds it in S state)
// Thread 1: repeatedly writes shared_var (forces S->I on thread 0, M on thread 1)

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

static volatile uint64_t shared_var = 0;

void *reader(void *arg) {
    uint64_t sum = 0;
    for (int i = 0; i < 1000000; i++)
        sum += shared_var;   // S-state hit, unless writer invalidated
    printf("sum=%lu\n", sum);
    return NULL;
}

void *writer(void *arg) {
    for (int i = 0; i < 1000000; i++)
        shared_var = i;   // S->I on reader's cache, M on writer's
    return NULL;
}

int main(void) {
    pthread_t r, w;
    pthread_create(&r, NULL, reader, NULL);
    pthread_create(&w, NULL, writer, NULL);
    pthread_join(r, NULL);
    pthread_join(w, NULL);
    // Run with: perf stat -e cache-misses,cache-references ./mesi_demo
    return 0;
}

False sharing is one of the most pernicious performance problems in concurrent systems code. It happens when two threads access different variables that happen to reside in the same cache line. The variables are logically independent — no actual data sharing occurs — but the cache coherence protocol treats the cache line as the unit of ownership, not the individual variable.

Here is the scenario: Core 0 writes counter_A and Core 1 writes counter_B. If counter_A and counter_B sit in the same 64-byte cache line, every write by Core 0 invalidates Core 1's copy of the line (MESI S/E → I), and every write by Core 1 invalidates Core 0's copy. Each write causes a coherence miss, a bus transaction, and a line to bounce back and forth between cores. On a heavily loaded system, this can reduce throughput by 10-100x.

Diagnosis: perf c2c (cache-to-cache) is the canonical tool. It identifies cache lines with high "hitm" (hit-to-modified) counts — precisely the signature of false sharing.

perf c2c record ./your_program
perf c2c report

The fix is straightforward: pad each variable to occupy its own cache line. In C, use __attribute__((aligned(64))) or the kernel macro ____cacheline_aligned_in_smp. In C++11 and later, use alignas(std::hardware_destructive_interference_size) (typically 64).

Real kernel examples:

• struct rw_semaphore in include/linux/rwsem.h pads its owner field
• Per-CPU variables (DEFINE_PER_CPU) naturally avoid false sharing by keeping each core's copy in a separate memory region
• Linux's struct zone in the memory allocator carefully aligns hot and cold fields to prevent false sharing between allocation and reclamation paths

True sharing vs. false sharing: Do not conflate them. True sharing is when two threads legitimately access the same data and must synchronize. False sharing is when they access different data that happens to be co-located. True sharing requires algorithmic solutions (locks, atomics); false sharing requires only padding/alignment.

// False sharing demo: two counters in the same cache line
// Compile: gcc -O2 -pthread -o false_sharing false_sharing.c
// Time: ./false_sharing  (try both PADDED=0 and PADDED=1)

#include <pthread.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>

#define ITERS 100000000UL
#define PADDED 0   // change to 1 to fix false sharing

typedef struct {
    uint64_t counter;
#if PADDED
    char pad[56];  // pad to 64 bytes — one full cache line
#endif
} Counter;

static Counter counters[2];   // [0] and [1] share a line when !PADDED

void *increment(void *arg) {
    int idx = (int)(intptr_t)arg;
    for (uint64_t i = 0; i < ITERS; i++)
        counters[idx].counter++;
    return NULL;
}

int main(void) {
    pthread_t t0, t1;
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    pthread_create(&t0, NULL, increment, (void*)0);
    pthread_create(&t1, NULL, increment, (void*)1);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);
    clock_gettime(CLOCK_MONOTONIC, &end);
    double ms = (end.tv_sec - start.tv_sec)*1e3
              + (end.tv_nsec - start.tv_nsec)/1e6;
    printf("Time: %.1f ms  (PADDED=%d)\n", ms, PADDED);
    return 0;
}

The hardware prefetcher is a circuit inside the CPU that watches your memory access patterns and speculatively fetches cache lines before they are needed, hiding the latency. It primarily targets stride prefetching (you access A, A+64, A+128 ... so it fetches A+192 before you ask) and stream detection (long sequential reads, like memcpy).

The hardware prefetcher works well for predictable patterns but fails for:

• Pointer chasing (node = node->next): each address depends on fetching the previous one
• Irregular / random access (hash tables, red-black trees)
• Access strides larger than a few cache lines

For these cases, software prefetching lets you issue an explicit hint to load a cache line into cache N iterations before you need it:

__builtin_prefetch(addr, rw, locality);
// rw: 0=read, 1=write
// locality: 0=non-temporal (use once), 3=keep in all cache levels

On x86, this compiles to PREFETCHNTA (locality=0), PREFETCHT0/T1/T2 (L1/L2/L3). On ARM, PRFM PLDL1KEEP.

A classic use: linked list traversal. While processing node[i], prefetch node[i]->next->data several iterations ahead. This overlaps the DRAM latency with computation.

The Linux kernel uses software prefetching sparingly and carefully — prefetch() and prefetchw() macros are defined in include/linux/prefetch.h. They are used in critical paths like copy_from_user, scheduler runqueue walks, and the block I/O path.

Caution: Over-prefetching pollutes the cache with data you will not use, potentially causing more misses. Always measure before and after. The hardware prefetcher is often smarter than hand-written prefetch hints for regular patterns.

// Software prefetch for linked-list traversal
#include <stdlib.h>
#include <stdint.h>

typedef struct Node {
    struct Node *next;
    uint64_t data[7];   // 7*8 = 56 bytes + pointer = 64 bytes total
} Node;

uint64_t sum_list_prefetch(Node *head) {
    uint64_t sum = 0;
    Node *cur = head;
    while (cur) {
        // Prefetch the node AFTER next — hide pointer-chase latency
        if (cur->next && cur->next->next)
            __builtin_prefetch(cur->next->next, 0, 1);
        sum += cur->data[0];
        cur = cur->next;
    }
    return sum;
}

Understanding caches transforms how you design data structures. The guiding principle: arrange data so that a single cache line fetch gives you everything needed for one unit of work.

Array of Structs (AoS) vs. Struct of Arrays (SoA): If you have N objects each with fields {x, y, z, mass, color, name} but your hot loop only touches x and y, AoS wastes 75% of each cache line loading fields you never use. SoA keeps all x values together and all y values together, so the hot loop has 100% cache-line utilization. This is why SIMD/vectorized code almost always uses SoA layout.

Tree structures — the B-tree lesson: A binary search tree has terrible cache performance: each pointer chase to a child node is a separate cache miss (16-bit pointer with data = 24 bytes, but the next pointer is in a completely different cache line). A B-tree or B+-tree fits many keys in a single cache line (a node with 8 keys = 64 bytes = one cache line), reducing tree height and turning pointer chases into sequential comparisons within a line. This is why database indexes, the Linux kernel's interval tree (lib/interval_tree.c), and std::map replacements use cache-oblivious or cache-aware layouts.

Hot/cold field splitting: Place frequently accessed (hot) fields at the beginning of a struct, cold fields (error counts, debug info, rarely-accessed config) at the end or in a separately allocated "cold" struct. The kernel's struct task_struct uses this technique: the scheduler's hot fields (run state, priority, on-rq flag) are carefully placed so the scheduler's fast path fits in as few cache lines as possible.

Per-CPU data: Linux's DEFINE_PER_CPU(type, var) allocates one copy of var per CPU, each in the CPU's own memory region. This eliminates cache-line bouncing for CPU-local counters and state. this_cpu_inc(var) accesses only the current CPU's copy — always a cache hit, no coherence traffic.

These patterns are not just optimization tricks — they are idioms that appear throughout the kernel codebase and that reviewers will look for in performance-sensitive patches.

// AoS vs SoA: cache line utilization comparison
#include <stdint.h>
#include <stdlib.h>

#define N 1000000

// AoS: hot loop reads x,y but loads x,y,z,w,pad too (wasted bandwidth)
typedef struct { float x, y, z, w; char pad[48]; } ParticleAoS;
static ParticleAoS aos[N];

// SoA: hot loop reads only x[] and y[] — 100% utilization
typedef struct {
    float x[N], y[N], z[N], w[N];
} ParticleSoA;
static ParticleSoA soa;

float sum_xy_aos(void) {
    float s = 0;
    for (int i = 0; i < N; i++)
        s += aos[i].x + aos[i].y;   // each struct = 64B, only 8B used
    return s;
}

float sum_xy_soa(void) {
    float s = 0;
    for (int i = 0; i < N; i++)
        s += soa.x[i] + soa.y[i];   // 64B line = 16 floats, all used
    return s;
}