Cache lines, locality and pointer chasing

The core never reads a single byte from main memory. It reads the 64-byte line that contains the byte and copies the whole line into its caches. Every later access to any byte in that line is served from the cache, which is many times faster than going back to memory.

Three levels of cache are usual on server parts: a small L1 per core, a larger L2 per core, and a large L3 shared by the cores on a chip. Each level is bigger and slower than the one before it, and main memory is slower again by a wide margin. Module 5 goes through the hierarchy in detail. For reading code, one rule carries most of the weight: the cost of a load depends on where the line is when you ask for it.

Our Quote is 24 bytes: four for the instrument, four for the sequence number, eight for the price, four for the quantity, one for the side, and three bytes of padding so that the next quote's price stays 8-byte aligned. Laid end to end in a vector, the lines fall like this:

A 64-byte line holds two and two-thirds quotes. Walking the vector, roughly one iteration in three or so triggers a fetch, and the others are served by a line already brought in. Some quotes straddle two lines, which is harmless when you are reading every quote in order, since the second line is needed next anyway.

Spatial locality is using data that sits next to data you have just used. Contiguous arrays have it; a structure whose fields you read together has it if those fields are close together.

Temporal locality is using the same data again soon. A small lookup table that every iteration consults stays in L1 as long as nothing evicts it.

Code that has both runs from cache almost all the time. Hot-path code is usually written to have both on purpose: the data an event needs is packed together and stays resident between events.

The worst access pattern is one where the address of the next load is the result of the current one:

struct Node { Quote q; Node* next; };

std::int64_t total_qty(const Node* n) {
    std::int64_t t = 0;
    while (n) { t += n->q.qty; n = n->next; }   // next address comes from this load
    return t;
}

A modern core can have many loads in flight at once and keeps working on independent instructions while it waits. Here there is nothing independent to do: the loop cannot know where node k + 1 is until node k arrives. If every node misses the cache, the loop runs at the speed of memory latency, one round trip per node.

The array version is not just faster because each line serves several elements. Its loads do not depend on each other, so even the misses overlap.

Linked lists are the obvious case. Less obvious ones show up all the time in interview code:

• std::map and std::set: every step down the tree is a dependent load.
• std::unordered_map: with the standard library's node-based design, a lookup goes to the bucket array and then to a node that can be anywhere.
• A std::vector<std::unique_ptr<Order>>: the vector is contiguous, but the orders are not.
• Virtual dispatch: object, then vtable, then code, three dependent loads before the function starts.

The fix is the same in every case: put the data the hot path reads in contiguous storage, and replace pointers with indices into that storage where you can.