Cache Lines, Locality, and Pointer Chasing

In the vector scan, update i + 1 sits beside update i. That helps because the processor fetches a block of nearby bytes when either update is missing from the cache. The block is a cache line.

The cache line

On most current x86-64 processors, a cache line is 64 bytes wide. A load can request one byte or eight bytes, but a cache miss brings in the line containing that address.

Suppose the loop loads one byte at address 0x1000. The line runs from 0x1000 through 0x103F, so the cache receives all 64 bytes. Later loads can use any byte in that range while the line remains cached.

The CPU will get everything from 0x1000 to 0x103F, not just the data at address 0x1000.

If the next load reads 0x1004, it uses the line brought in by the first load, assuming the cache has not evicted it. The processor avoids another miss for that access. The exact latency depends on which cache level holds the line and on the processor, so measurements should supply the numbers for a particular machine.

Accessing nearby bytes close together in time gives the program spatial locality. A cache line then contains useful data for several loads instead of serving only the load that caused the miss.

You can see the same behavior in a row-major 2D array. With outer i and inner j, arr[i][j] advances through adjacent elements in one row. Several accesses can use the same cache line. If the inner loop changes i instead, arr[i][j] jumps between rows. A large row stride can send consecutive accesses to different lines. The widget traces both address sequences and shows which line each access uses.

How MarketUpdate fits in a cache line

The same calculation applies to the MarketUpdate from the running example.

Copy
struct MarketUpdate {
    std::uint64_t sequence;   // 8 bytes
    char         symbol[8];   // 8 bytes
    std::int64_t price;       // 8 bytes
    std::int32_t qty;         // 4 bytes
    // typically 32 bytes after padding on the target ABI
};

With this layout, sizeof(MarketUpdate) is typically 32 bytes on a 64-bit target. Over a long vector scan, each 64-byte line contains two updates' worth of storage. The exact pairing depends on where the vector buffer begins, and an update can cross a line boundary when the buffer lacks 64-byte alignment. Contiguous storage still lets one fetched line serve fields from neighboring updates.

A std::list<MarketUpdate> gives the processor a different address sequence. The iterator reads the current node, loads its next pointer, and follows that pointer to another allocation. Separately allocated nodes can land in unrelated cache lines, and each node also stores link fields beside the update. This is the pointer chasing from the previous article. Here we can see its cache cost: the processor must load the current node before it knows which address to request next.

With the illustrated 32-byte layout and alignment, one 64-byte line contains two complete updates.

Designing for locality

When you read a hot path, ask how many bytes one iteration uses and where the next iteration will read. The answer tells you how much of each fetched line contributes useful data.

Bytes already present in a cached line avoid another miss. A new line requires another lookup through the cache hierarchy, and a dependent pointer can delay that lookup because the processor must learn the address first. Following the addresses in order exposes which case the loop creates.

Designing for locality means arranging data around its access pattern. A loop that reads every field of each update often works well with a vector of compact structs. If another loop reads only price across many updates, a dense price array may place more useful values in each line. Grouping frequently read fields can help for the same reason. The right layout follows the fields and traversal order used by the hot path.

The vector packs two illustrated updates into one line. A list traversal follows each node's pointer to find the next address.

In interviews

• "Why can std::vector traversal outperform std::list traversal?" → "The vector gives the processor adjacent element addresses, so one cache line can serve several loads and hardware can prefetch the sequence. A list must load each node's link before it knows the next address."
• "What's pointer chasing?" → "The loop reads a pointer from the current object and then uses that value as the address of the next load. A cache miss on the current object delays the next request."
• "Is a std::vector of pointers cache-friendly?" → "The pointers are contiguous. The pointed-to objects can still be scattered, so each dereference may lead to another cache line."
• "How would you lay out data for a hot loop that reads only two fields?" → "I would inspect the access pattern and try to place those fields in fewer cache lines, either by grouping hot fields or storing them in separate dense arrays. Then I would measure the resulting loop."

The next article moves to the next checklist question: can the loop body ask the allocator for memory?