Architecture: caches, branch prediction and SIMD

Modern processors are fast at arithmetic and slow at waiting for memory, and nearly every performance question at a low-latency firm reduces to that asymmetry. Writing fast code means arranging data so the processor is never waiting and never guessing wrong.

Level	Latency	Size
Register	0 cycles	A few hundred bytes
L1	~4 cycles, ~1 ns	32–48 KB per core
L2	~12 cycles, ~4 ns	0.5–2 MB per core
L3	~40 cycles, ~15 ns	Tens of MB, shared
Main memory	~200–300 cycles, ~80–100 ns	Gigabytes

Table 1.1 · The memory hierarchy. A cache miss to main memory costs roughly as much as a hundred arithmetic operations. That ratio, more than any instruction count, is what determines the speed of real code.

Figure 1.2 · The memory hierarchy, in nanoseconds. Typical figures on a modern server core. A hundred to one between L1 and DRAM is why layout beats instruction count: a loop over a contiguous array and a loop over the same data behind pointers execute the same operations and differ by two orders of magnitude.

Proposition 1.3

The cache line is the unit

Memory moves in 64-byte lines, not in bytes. Reading one integer pulls in its fifteen neighbours, so a sequential walk pays one miss per sixteen elements and a random walk pays one per element — a sixteenfold difference in memory traffic from the access pattern alone.

Holds when

Sequential access is also prefetched: the hardware notices the pattern and fetches ahead.
Struct-of-arrays beats array-of-structs when you touch one field at a time, because the unused fields no longer occupy the line.
False sharing is the pathological case: two threads writing different variables on one line invalidate each other’s copies.

Why a mispredicted branch costs so much. A modern pipeline has fifteen to twenty stages, and it does not wait to discover which way a branch goes — it predicts and speculates ahead. When the prediction is right the branch is effectively free. When it is wrong, everything speculatively executed is discarded and the pipeline refills from scratch, costing roughly the pipeline depth. Predictable branches are therefore nearly free and unpredictable ones cost fifteen to twenty cycles, which is why a data-dependent branch on random input can be slower than doing the work unconditionally.

Example 1.4

A loop sums the elements of an array that exceed a threshold. Why is it much faster on sorted data?

Show the worked solutionHide the worked solution

Worked solution

Formula $\text{cost} \approx n \times \left(\text{work} + P(\text{mispredict}) \times 15\right)$
Substitute $\text{sorted: the branch goes one way then the other, so it predicts}$
Solve $\text{random: } P(\text{mispredict}) \approx 0.5 \Rightarrow \approx 7.5 \text{ cycles wasted per element}$
$\text{sorted: } P \approx 0 \Rightarrow \text{effectively free}$
Answer $\text{several times faster, with identical instructions}$

Sanity check. Nothing about the arithmetic changed — the same comparisons and additions run in the same order. The entire difference is that the predictor can learn a sorted pattern and cannot learn a random one, which is why this is the canonical demonstration that the processor, not the algorithm, decides.

Architecture: caches, branch prediction and SIMD

After this lesson you should be able to

The cache line is the unit

The rest of this lesson is in Premium