CPU Caches and Locality Visualized

Big O describes growth, but memory access patterns strongly affect how fast algorithms actually execute on real hardware. Two implementations can both perform a linear number of source-level operations while spending very different amounts of time waiting for data.

The visualizer uses a tiny cache with four abstract cells per line and least-recently-used eviction. It is intentionally not a model of a particular processor. Real CPUs have several cache levels, set mapping, prefetchers, coherence protocols, and replacement policies that are architecture-specific. The simplified model isolates one durable idea: nearby and recently used data is often cheaper to access.

The memory hierarchy

Storage close to the processor is generally smaller and faster; storage farther away is generally larger and slower. A conceptual hierarchy is:

registers
  -> L1 cache
    -> L2 cache
      -> shared or last-level cache (often called L3)
        -> main memory (RAM)
          -> persistent storage

This is a direction of tradeoff, not a universal physical diagram. Some processors have different level counts, private and shared arrangements, specialized caches, or non-uniform memory access. Persistent storage is not simply “the next CPU cache.” Each layer has its own management rules.

The hierarchy exists because one technology cannot simultaneously provide register-like speed, enormous capacity, low cost, and persistence. Hardware and software cooperate to keep likely-needed data closer to execution.

Cache lines move blocks

A CPU cache generally transfers memory in aligned blocks called cache lines, not as isolated source-language variables. A 64-byte line is common on modern general-purpose processors, but it is not guaranteed. This tutorial uses four cells per line so every transfer is visible.

If address 0 misses, the teaching cache loads cells 0 through 3. Accesses to 1, 2, and 3 can then hit even though the program did not explicitly request them during the first access. Loading the surrounding block is valuable when programs exhibit spatial locality.

A cache hit finds the requested data in the cache. A cache miss requires obtaining its line from a lower level before execution can use it. The exact cost varies by cache level, contention, processor, and workload, so a universal latency table would mislead. What matters is that misses introduce work invisible in a count of high-level loop iterations.

Spatial locality

Spatial locality means an access makes nearby addresses likely to be used soon. Sequential array traversal is the standard example:

array[0] -> array[1] -> array[2] -> array[3]

When those elements occupy contiguous memory, one line fill may serve several accesses. After address 0 loads the block containing 0–3, the next three reads can hit. Address 4 crosses into another line and misses once, then nearby accesses benefit again.

This is why a loop's order can matter even when it reads the same number of values. A large stride can touch one element from each line, receiving little immediate benefit from the rest of every transferred block.

Temporal locality

Temporal locality means recently accessed data is likely to be accessed again:

read x
perform nearby work
read x again soon

If x's line remains in cache, the later read can hit. “Soon” is workload-dependent: other accesses may evict the line before it is reused. The relevant concept is a working set, the data actively needed during a phase of computation.

Finite capacity matters. The visualizer holds three lines. When a fourth distinct line arrives, it evicts the least recently used line in this teaching policy. Returning to that evicted address misses even though it was accessed earlier. Real replacement decisions are more complex and do not universally implement exact LRU.

Sequential and scattered traces

For line size four, the sequential trace begins:

access 0 -> miss, load [0, 1, 2, 3]
access 1 -> hit
access 2 -> hit
access 3 -> hit
access 4 -> miss, load [4, 5, 6, 7]

The scattered pattern deliberately jumps among lines. It may still hit occasionally—address 3 can reuse the line loaded by address 0—but it creates more line fills and can exceed capacity sooner. The counters in the visualizer come directly from the trace; no hit rate is estimated.

Stride controls show that locality changes gradually. Stride 1 consumes each loaded line. Stride 2 uses fewer cells from it. Stride 4 touches the first cell of each successive line. Stride 8 skips an entire line at a time and revisits only after other lines have pressured the cache.

Why arrays often perform well

Compact arrays commonly store elements contiguously or in compact buffers, letting one cache line contain several useful values. Index calculation is predictable, and processors may prefetch obvious sequential patterns.

A linked list can also require O(n) work to traverse n nodes, yet each node may live in a separate allocation. Following a pointer reveals the next address only after the current node is loaded, and the next node may be far away. That pointer chasing can reduce spatial locality and limit parallel memory access. Node metadata and allocator layout add further overhead.

This is a tendency, not a universal verdict. Some runtimes compact objects, some linked structures use pools or arrays internally, arrays can contain references to scattered objects, and workloads may need constant-time splicing or stable references more than traversal speed. Data representation and runtime behavior determine the actual pattern.

The arrays and linked structures tutorial explains the operation-level tradeoff. Cache locality adds the hardware-level cost model.

Matrix traversal and layout

In C or C++, a conventional row-major two-dimensional array places each row's elements next to one another. Iterating columns inside rows follows memory order:

for (std::size_t row = 0; row < rows; ++row) {
  for (std::size_t col = 0; col < cols; ++col) {
    total += matrix[row][col];
  }
}

Swapping the loops can jump by a full row between accesses. Both versions visit rows times columns elements and are O(rows × cols), but the row-major traversal typically uses each fetched line more effectively. Compilers, matrix dimensions, cache geometry, vectorization, and prefetching still influence the measurement.

JavaScript nested arrays are arrays of references, not guaranteed contiguous C-style matrices. A typed array with explicit indexing provides a closer raw-buffer example. Any locality claim must state its data-layout assumption.

Big O and constant factors meet hardware

Big O notation answers how work grows with input size. It intentionally ignores constants and lower-order terms. Cache behavior helps explain where some of those constants come from.

Two O(n) algorithms can differ because one performs compact sequential reads while another follows pointers, allocates temporary objects, executes unpredictable branches, or crosses runtime boundaries. Two O(n log n) sorts can differ because one moves contiguous blocks while another has less favorable access patterns. Even the same algorithm can behave differently for two representations of the same logical data.

This does not make complexity optional. A cache-friendly quadratic algorithm eventually loses to an appropriate linear or n log n algorithm as input grows. Nor does an asymptotically better design guarantee victory at the small input sizes that actually occur. Complexity identifies scaling risk; systems effects and measurement determine present cost.

More effects invisible to Big O

Memory locality is only one constant-factor influence:

• allocations add bookkeeping and can trigger garbage collection in managed runtimes;
• branch prediction affects control-flow throughput;
• vector instructions may process several values together;
• compiler and runtime optimizations can remove, combine, or specialize work;
• synchronization and false sharing can make cores contend over cache-coherence traffic;
• virtual-memory translation and TLB behavior add another cache of mappings.

Each deserves its own model. Combining all of them into one “hardware makes it faster” explanation prevents useful reasoning.

Measure instead of guessing

Start with complexity to reject designs whose growth cannot meet the expected scale. Profile the real application to locate where time is spent. Benchmark a focused change with representative data and enough control to make comparisons meaningful.

Warm and cold cache states can produce different results. Managed runtimes may compile hot code after several executions. Optimizing compilers can remove benchmark work whose result is unused. Background activity, data shape, allocation history, and input distribution all matter. A benchmark is evidence about a specified environment, not a permanent property of an algorithm.

Use the visualizer to form a hypothesis: sequential access should produce fewer misses in this model than the scattered trace. Then read the actual counters. That habit—explicit model, measurable prediction, real observation—is more valuable than memorizing that arrays are “fast.”