Caches: why neighbors are fast

The speed gap

A modern processor core completes several instructions every nanosecond. Fetching a value from main memory (DRAM) takes around 80 to 100 nanoseconds. If every load went to main memory, the processor would spend almost all of its time waiting.

Caches close that gap. They are small, fast memories built into the processor that keep copies of recently used data. Typical figures for a desktop or server chip:

The exact numbers change from chip to chip, but the shape doesn't: each level is roughly ten times bigger and several times slower than the one above, and main memory is about a hundred times slower than L1. Where your data happens to be decides how fast your code runs.

Memory moves in lines

Caches don't store individual bytes. They store cache lines: aligned blocks of 64 bytes on most x86 and ARM processors (Apple's M-series chips use 128). When you read one byte that isn't cached, which is called a miss, the processor fetches the entire line that contains it.

The trace above shows the consequence. An array of 4-byte integers fits 16 to a line. Reading a[0] misses and pays the full trip to memory, but the line that arrives also holds a[1] through a[15], so the next fifteen reads hit and cost about a nanosecond each. Sixty-four reads cost four misses.

This is spatial locality: when a program uses one address, it is likely to use nearby addresses soon. Contiguous data benefits automatically, because nearby addresses hold the next elements. The other kind is temporal locality: data used recently is likely to be used again soon, and is still in the cache when it is.

The prefetcher

Processors also watch the stream of misses. When they see a pattern, such as consecutive lines or lines a fixed distance apart, a hardware prefetcher starts fetching the lines it predicts will be needed before the program asks for them. In the trace, the line holding a[16] is already on its way by the time the loop reaches it.

Prefetchers handle forward and backward streams and fixed strides well. They can't predict random indexes, and they can't predict pointer chasing, because the next address is only known once the current node has arrived.

When locality breaks

Three access patterns undo the cache:

• Large strides. A matrix stored row by row, as C, NumPy and most languages do, has each row's elements side by side. Walking down a column jumps a whole row each step. For a 1,000 × 1,000 matrix of doubles that is 8,000 bytes per step, so every read touches a new line and uses 8 of its 64 bytes. Swapping the two loops so the inner one walks along a row often makes the code several times faster, with identical arithmetic.
• Random access. Reading a large array at random indexes, as in this lesson's opening question, turns almost every read into a miss. A processor can keep several independent misses in flight at once, which softens the blow, but each read still pays for a full line it barely uses.
• Pointer chasing. Walking a linked list, a tree or a graph whose nodes are scattered is the worst case. Each address comes from the previous load, so misses happen strictly one after another and the processor can't overlap them. Ten million nodes with a miss at each one is close to a full second of waiting.

When the working set is small enough to fit in the cache, as with the 256 bytes in the trace, all of this matters less: after the first pass, everything hits. Problems appear once the data outgrows the caches, which for most real programs is quickly.

What this means for data structures

Big-O counts steps, as the next module teaches, and treats every memory access as equal. On real hardware a cache hit and a miss differ by a factor of about a hundred, so two algorithms with the same Big-O can differ tenfold in practice. That is why:

• scanning an array is one of the fastest things a program can do, often faster than a cleverer structure for small inputs;
• hash tables with open addressing probe neighboring slots that share a cache line, as the hash tables module shows;
• B-trees, inside nearly every database, pack many keys into each node so that each node fetched from memory or disk answers more of the search;
• later modules lay data out on purpose, for example storing each field in its own array so that a loop reads only the bytes it needs.

Throughout this track, "behind the code" traces count these costs: how many lines a step touches, and whether its next address was predictable.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Caches: why neighbors are fast from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

total = 0
for i in range(64):
    total += a[i]

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.