5.1 Caching, Locality, and Mapping

Processors execute instructions much faster than they can access main memory. Multi-level caches narrow that speed gap; levels closer to a CPU core typically have less capacity and lower access latency. A program's access pattern determines whether the hierarchy actually helps.

A single-cycle data path depicts instruction memory and data memory as fixed-delay blocks. Real processors deal with layered storage systems. This lesson first explores locality, cache lines, set-associative mapping, and write policies; multi-core sharing is covered in cache coherence and false sharing.

The Processor Doesn't Treat "Memory" as a Single Thing

The ALU can compute an address quickly, but the data may not return immediately. Registers, L1 and L2 caches, the last-level cache, DRAM, and persistent storage differ in capacity, latency, bandwidth, and cost. An ordinary load of address X may hit a cache or reach DRAM. Instructions name register operands directly; registers are not another cache searched by a load. SSD data normally reaches memory through I/O or page-fault handling, rather than a CPU automatically continuing its cache lookup on disk.

A typical, though not rigid, layering structure is:

Registers
  ↓
Per-core L1 instruction / data cache
  ↓
Per-core or shared secondary cache
  ↓
Shared last-level cache
  ↓
DRAM
  ↓
SSD / Other Persistent Storage

The closer a storage layer is to the execution unit, the smaller its capacity, the lower its access latency, and the higher its per-unit cost. The exact number of layers, sizes, associativity, inclusion relationships, and latencies vary significantly by processor model; product specifications should not be treated as universal rules.

An outer cache does not necessarily contain every block held by its inner caches. Inclusive designs maintain that inclusion; exclusive designs avoid duplication across the relevant levels, while non-inclusive/non-exclusive designs guarantee neither relationship. Replacement policies may also consider cache coherence directories and service quality. Before applying software optimizations, it's essential to confirm the target platform.

Caches Bet on Locality

Caches predict future accesses based on recent ones:

• Temporal locality: Data recently accessed is likely to be accessed again soon;
• Spatial locality: Data near recently accessed addresses is likely to be accessed soon.

A counter variable in a loop often stays in a register and doesn’t repeatedly access L1 cache, so it’s not a good example to simply prove temporal locality. A better case is repeatedly querying a table that fits into cache, or performing multiple rounds of computation on a small working set.

C stores a two-dimensional array by rows. These function fragments require C17 support for variable-length array parameters, positive rows and columns, a valid complete matrix, and every partial sum in either traversal to fit int64_t. Large matrices produce different row-wise and column-wise address sequences:

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

static int64_t sum_row_major(size_t rows, size_t columns,
                             const int matrix[rows][columns]) {
    int64_t sum = 0;
    for (size_t row = 0; row < rows; row++) {
        for (size_t column = 0; column < columns; column++) {
            sum += matrix[row][column];
        }
    }
    return sum;
}

static int64_t sum_column_major(size_t rows, size_t columns,
                                const int matrix[rows][columns]) {
    int64_t sum = 0;
    for (size_t column = 0; column < columns; column++) {
        for (size_t row = 0; row < rows; row++) {
            sum += matrix[row][column];
        }
    }
    return sum;
}

Row-major access generally better exploits the fact that adjacent elements are already loaded into a cache line and is more easily recognized by hardware prefetchers. However, the performance difference isn’t a fixed “10x”: it depends on matrix size, the stride formed by column count, cache and TLB capacity, compiler vectorization, and hardware prefetching. When the matrix is small and entirely fits in cache, the two approaches may actually be nearly equivalent.

Locality is a property of the access pattern, not a decision based on the name of a data structure. Arrays are typically contiguous, while linked list nodes may be scattered; compact linked lists allocated via arena may outperform arrays filled with large cold fields. Before choosing a layout, examine the actual hot fields and how they are accessed.

Cache Lines Define Transfer and Coherence Granularity

Caches typically do not transfer data one byte at a time, but rather in fixed-size blocks known as cache lines. Many modern x86-64 and AArch64 processors use a 64-byte line size, but this is not a language-level guarantee across all architectures. Code that depends on line size should obtain the value through target documentation, system query interfaces, or deployment configuration, never hardcode 64 as a universal constant.

Assuming a line size of 64 bytes, when a miss occurs during the access to 0x1001, the cache might load a range aligned to that boundary:

0x1000 ... 0x103F

A subsequent access to 0x103F might then hit the same line, while 0x1040 would fall into the next line. The use of "might" is important here, as the line could be evicted, invalidated, or replaced due to other access patterns or special cache policies.

When objects span across cache lines, a single logical access may require two separate line lookups. Alignment can control the starting position, but it does not automatically ensure that object size, array stride, or field grouping aligns with expectations. In C, it's also essential to distinguish between alignment permitted by the language and alignment supported by the hardware cache geometry.

How Addresses Locate Candidate Locations

In a simple physically addressed cache with modulo indexing, split the address into:

| tag       | set index | line offset |

If the line size is B bytes and the cache has S sets, the following calculations apply:

block_number = address / B
set_index    = block_number mod S
tag          = block_number / S
offset       = address mod B

Division here takes the integer quotient. Power-of-two B and S give fixed bit fields. Real CPUs may use virtual indexing, physical tags, or hashes for cache slices/sets; this modulo model does not prove address conflicts on arbitrary hardware.

For example, consider a 32 KiB cache with 64-byte lines and an 8-way set association:

line count = 32768 / 64 = 512
set count  = 512 / 8 = 64
offset     = 6 bits
index      = 6 bits

Blocks differing by 64 sets × 64 bytes = 4096 bytes will map to the same set. A set contains only eight ways; if the working set repeatedly accesses nine lines mapped to the same set, replacement policies may lead to severe conflict. The value 4096 is specific to this example configuration.

The tag is used to verify whether the block stored in any candidate way matches the target block. A valid bit distinguishes a usable copy from an empty or invalidated slot. In a write-back cache, an additional dirty bit is required to track write-back state.

Direct Mapping, Set-Associative, and Fully Associative

Organization	Candidate locations per block	Advantages	Disadvantages
Direct mapping	One way in a single set	Simple lookup	Prone to conflicts
N-way set-associative	N ways within a specified set	Balances conflict and lookup cost	Requires parallel comparison of multiple tags
Fully associative	Any line in the cache	No set conflicts	Lookup and replacement cost increases with capacity

Fully associative reduces conflict misses but does not eliminate compulsory misses or capacity misses. Some small TLBs or victim caches can be fully associative, but it's incorrect to generalize that all TLBs are fully associative.

In an N-way cache, a victim must be selected within a set. True LRU becomes increasingly complex as the number of ways grows. Hardware typically employs pseudo-LRU, random selection, RRIP, or adaptive strategies instead. Relying solely on “least recently used” is insufficient to accurately predict cache replacement behavior in modern CPUs.

Four Types of Misses to Help Identify Causes

Ignoring prefetching and coherence invalidations, the classic 3C model includes:

• compulsory/cold miss: the first access to a block;
• capacity miss: the working set exceeds the cache's available capacity;
• conflict miss: limited associativity causes multiple active blocks to compete for the same set.

In multicore systems, coherence misses also occur: when another agent writes to a shared block, the local copy in this core becomes invalid. Prefetching can also alter observed behavior; prefetched lines may be brought in early, or they may contaminate the cache and consume bandwidth.

The value of classification lies in guiding solution selection. More capacity does not directly solve pure coherence bouncing, and more ways do not eliminate the first fill. Prefetching may perform that fill early enough for the first demand access to hit.

A Runnable Set-Associative Simulator

This Python model uses exact LRU with integer geometry and nonnegative integer byte addresses. Each access checks one line containing that address; it does not model accesses spanning lines, prefetching, writebacks, or coherence. It is not a cycle-accurate model of a particular CPU.

from collections import OrderedDict

class SetAssociativeCache:
    def __init__(self, size_bytes: int, line_bytes: int, ways: int):
        if any(not isinstance(v, int) or isinstance(v, bool)
               for v in (size_bytes, line_bytes, ways)):
            raise TypeError("cache geometry must use integers")
        if min(size_bytes, line_bytes, ways) <= 0:
            raise ValueError("cache geometry must be positive")
        denominator = line_bytes * ways
        if size_bytes % denominator != 0:
            raise ValueError("size must contain a whole number of sets")

        self.line_bytes = line_bytes
        self.sets = size_bytes // denominator
        self.ways = ways
        self.contents = [OrderedDict() for _ in range(self.sets)]

    def access(self, address: int) -> bool:
        if not isinstance(address, int) or isinstance(address, bool):
            raise TypeError("address must be an integer")
        if address < 0:
            raise ValueError("address must be non-negative")

        block = address // self.line_bytes
        set_index = block % self.sets
        tag = block // self.sets
        entries = self.contents[set_index]

        hit = tag in entries
        if hit:
            entries.move_to_end(tag)
        else:
            if len(entries) == self.ways:
                entries.popitem(last=False)
            entries[tag] = None
        return hit

cache = SetAssociativeCache(32 * 1024, 64, 8)
same_set = [index * 4096 for index in range(9)]

assert not cache.access(same_set[0])
assert cache.access(same_set[0])

for address in same_set[1:]:
    assert not cache.access(address)

assert not cache.access(same_set[0])  # The ninth same-set block evicted the oldest entry.

This conclusion relies on the model's exact LRU implementation. With a real hardware pseudo-LRU, the specific victim choice might differ, but the principle that "exceeding the number of ways creates pressure within the same set" still holds.

Write Propagation and Allocation Are Separate Choices

When a CPU store hits in cache, common update policies are:

• write-through: update the cache simultaneously and propagate the write to the next level;
• write-back: update only the current cache line and mark it as dirty, propagating the change only when the line is replaced or coherence requires propagation.

Write-through does not mean every instruction must synchronously wait for DRAM. Store buffers, write combining, and lower-level caches can absorb latency; multi-core systems still require coherence, and no core can bypass the protocol to directly access memory.

Write-back reduces redundant writes to lower levels, but dirty line replacement is more expensive and adds complexity in state management. In the event of a power failure, dirty cache lines cannot reliably be flushed to DRAM through a generic "mainboard capacitor promise"; standard DRAM is also volatile. Durability requires explicit guarantees from the storage system, flush/fence operations, controllers, and the underlying hardware platform.

When a write miss occurs, there's also an orthogonal choice:

• write allocate: allocate the line in this cache and obtain the data/write permission needed for the update; full-line overwrites may avoid fetching old data;
• no-write-allocate/write-around: allow the write to propagate downward without allocating the line into the current cache.

Write-back is often paired with write allocate, while write-through is typically paired with no-write-allocate, but this is not logically mandatory. Non-temporal stores represent a different class of hint or instruction semantics, potentially using write-combining paths to reduce cache pollution. They should not be simply labeled as "write-through" or "direct write to DRAM."

AMAT Converts Hit Rate to Cost

The average memory access time (AMAT) for a single-layer simplified model is:

AMAT = hit_time + miss_rate × miss_penalty

If the L1 hit time is 1 ns, the miss rate is 5%, and the average additional cost after an L1 miss is 12 ns:

AMAT = 1 + 0.05 × 12 = 1.6 ns

For multi-level hierarchies, the model can be recursively expanded:

AMAT_L1 = hit_L1 + miss_L1 × AMAT_L2_miss_path

Actual performance is also influenced by memory-level parallelism, out-of-order hiding of latency, bandwidth saturation, prefetch accuracy, and queue congestion. AMAT is a ballpark model for estimating memory access cost; it is not a complete equation for directly predicting program runtime.

Data Layout Should Be Considered Alongside Access Patterns

AoS (array of structures) bundles the fields of an object together, making it suitable when the entire object is frequently accessed. SoA (structure of arrays) arranges fields of the same type contiguously, which is better for scenarios involving selective field access, vectorization, or columnar compression.

struct Particle {
    float x, y, z;
    float vx, vy, vz;
    float mass;
    int type;
};

struct ParticlesSoA {
    float *x, *y, *z;
    float *vx, *vy, *vz;
    float *mass;
    int *type;
};

SoA is not universally faster; it introduces additional pointer overhead and allocation management. Accessing multiple fields simultaneously may require maintaining more streams. AoSoA (array of structures organized by SIMD/cache-friendly blocks) often serves as a balanced compromise. Begin by identifying the fields actually accessed in hot loops, then design the layout accordingly.

Matrix multiplication tiling follows the same principle: reuse subblocks of matrices A and B before they are replaced. The block size cannot be fixed at 32; element size, cache capacity, memory associativity, SIMD kernel design, and thread-level sharing all influence the optimal value.

How to Conduct a Trustworthy Cache Experiment

A “read the same address repeatedly” benchmark only measures compiler optimizations, load forwarding, or L1 hot data caching. It cannot reliably force a DRAM access by referencing a distant memory location. A trustworthy experiment must at least consider:

1. For latency beyond a cache level, exceed that level’s capacity and use dependent accesses to limit overlap; bandwidth tests instead need sufficient independent accesses, so the same dependency rule does not apply;
2. Warming up and repeating the test multiple times, reporting a distribution rather than a single value;
3. Preventing compiler elimination of work, while ensuring that timing overheads from loops do not dominate the results;
4. Fixing CPU affinity, recording frequency, NUMA node, and system load;
5. Distinguishing between latency and bandwidth;
6. Validating cache misses using the target platform's performance counters, rather than relying solely on wall-clock time.

perf event names and meanings vary with the CPU and kernel. First use perf list to check supported events, then explain multiplexing, permissions, and sampling errors.

Hands-on Analysis of Address Sequences

1. For a 32 KiB, 64-byte, 8-way cache, decompose the address 0x12345678 into its offset, set, and tag components.
2. Modify the Python model to compare miss counts for 1-way, 2-way, and 8-way configurations across the same trace.
3. Construct three types of traces (compulsory, capacity, and conflict) and explain why certain optimizations affect only one of these categories.
4. For a row-major versus column-major experiment, specify the working set size and stride, and predict cache and TLB behavior accordingly.
5. Provide a use case for each of AoS, SoA, and AoSoA that aligns with their access patterns.
6. Use a two-level AMAT model to evaluate the impact of parameter changes in L1, L2, and DRAM, then identify which forms of parallelism the model overlooks.

Multicore Allows the Same Line to Appear in Different Places

With a single-core cache, the system only needs to maintain data consistency within the cache hierarchy. When multiple cores each have their own private caches, the same physical line may exist in multiple copies. Writes to that line must then be coordinated among all owners. The next section, Cache Coherence and False Sharing, will distinguish between coherence, atomic operations, and language memory models.