CPU Architecture Primer

Three structures do the work: a register file of sixteen named 64-bit slots on x86-64 (thirty-one on ARM64), an ALU, and a program counter.

One add rax, rbx visits all of them in order. Press play and watch the instruction move from structure to structure, with the registers it reads lit underneath:

Notice that the register file is touched twice — once for the operands, once for the sum — and nothing outside the core is touched at all. Reading a register is part of executing the instruction, not a separate event with a latency of its own.

Not every instruction is an add. The ladder below is what a Skylake core pays for each kind, in cycles, and the slider walks the one being charged for:

The spread is the whole story of this page. A register add is 1 cycle — 0.33 ns at 3 GHz — and a load that misses every cache is 250, or 83 ns. A factor of 250 sits between the two rungs, and no clock frequency closes it.

Sixteen registers is not many. Raise the values that have to be live at once and watch the ones with nowhere to sit drop into the row below:

At twenty-four live values, eight spill, and each spilled value costs a store and a load per iteration — sixteen memory operations the source code never mentions. This is the real reason aggressive inlining pays.

So why not build a machine with more registers? A register name has to be spelled out in the instruction, and on ARM64 every bit given to the three register fields is a bit taken from the opcode:

At the five bits ARM64 chose, thirty-two registers cost fifteen of the thirty-two and leave seventeen — 131,072 operations, which is plenty. Push the fields to eight bits and you get 256 registers and 256 operations, which is not an instruction set.

One number survives into everyday conversation: the clock. The tempting arithmetic is that 3 GHz retires 3 billion instructions. Raise the loads that miss to DRAM and watch the two bars separate:

Eight misses per thousand instructions triples CPI to 3.00 and drops throughput to 1.00 billion a second, a third of the number on the box. It is wrong the other way too: the next three sections are how a core retires more than one per cycle.

Cut the loop into stages — fetch, decode, execute, memory, writeback — and give each its own hardware. One instruction at a time uses one stage per cycle and leaves four idle.

The slider is the interval between starts. Drag it from five to one and watch the total collapse while each instruction still takes five cycles to reach writeback:

Five instructions take twenty-five cycles one at a time and nine when they overlap — 2.8× with no extra hardware and no faster clock. Nothing got shorter; the machine stopped leaving stages empty. Latency is unchanged at five, and throughput is what moved.

Step through one cycle at a time, watch the diagonal fill, and see the first retirement arrive at cycle five:

Because the run costs five cycles of fill plus one per instruction after that, n instructions cost n + 4 rather than 5n. That is an amortisation argument, not an average: no single instruction beats five cycles, but the run approaches one retirement per cycle as n grows.

It holds only while every stage has something to hand on. The second instruction below needs a register the first has not written. Switch forwarding off and step through the dead cycles:

Without it the consumer waits for the producer's writeback — two dead cycles, given a register file that writes in the first half of a cycle and reads in the second. Forwarding wires the ALU output back to its input and the run drops from ten cycles to eight.

One hazard survives it. A load's value is not known until the end of the memory stage, so the instruction right behind it still stalls. Drag the consumer away from the load and watch the bubble go:

One slot apart costs a bubble; two slots apart costs nothing. That is the whole reason compilers hoist loads — the scheduler is buying a slot, not being clever about caches. Any independent instruction will do, which is also why unrolling helps.

A five-stage pipeline is a 1990s machine. Modern cores run fifteen to twenty stages, because a shorter stage clocks faster. Drag the depth and watch the clock against the flush:

The trade is not the one people quote. Five stages to twenty nearly triples the clock, 1.19 to 3.51 GHz, and the flush grows from four cycles to nineteen — but those cycles are shorter, so in time it only goes 3.36 ns to 5.42 ns. Cycles is the wrong unit for a flush.

Not forever. Pentium 4's Prescott ran 31 stages at 3.8 GHz, and the extra latch delay gave back much of what depth bought: past twenty-five, the clock curve flattens while the flush climbs.

So it does not: the front end guesses and keeps fetching. Push the branch deeper into the pipeline before it resolves, and count what was fetched behind it:

Everything on the wrong path is deleted and the real target starts from fetch. The later the resolve, the more is thrown away — §02's depth trade from the other end. On a real core the refill is 17 cycles.

About one instruction in five is a branch, so the arithmetic is unforgiving. Raise the share that comes back wrong and watch how much of the core stops belonging to your program:

At the 2% real code manages, CPI is 1.07 and 6.4% of cycles are thrown away. At a coin-flip 50% the same core runs at CPI 2.70 and spends 63% of its cycles on work it will discard. Accuracy is the difference between two machines.

The mechanism is a counter per branch. One bit says “do what happened last time”; two bits must be wrong twice to change their mind. Step through the outcomes and watch the misses under each:

On an eight-iteration loop the one-bit predictor gets eight of thirty-two wrong and the two-bit six: the extra bit absorbs the single exit without forgetting the loop. On the alternating pattern two bits is wrong sixteen times — it oscillates in the middle and never predicts taken at all. On unpredictable data it is 21 of 32, marginally worse than one bit.

That last case is the famous one. Sort the values that clear the threshold towards the back and watch the wrong guesses disappear:

Shuffled, the loop mispredicts fifteen times in thirty-two iterations and costs 383 cycles; ordered, twice and 162. A 2.4× speed-up on identical data and identical code — the reason std::sort before a hot filter pays for itself.

Then the level-two question: how much sorting? Past sixteen, the mispredict count stops moving while the bars keep rearranging — sixteen is where every value below 128 sits in front of every value above it, and the predictor sees only the outcome sequence. A partition is enough, and it is O(n).

Direction is half the problem. An indirect call needs a target, and the buffer that remembers targets holds the last one. Add targets to the call site and watch the hit rate fall:

One target is free. Four, in an order the predictor cannot learn, are right one call in four and cost 12.8 extra cycles each time — more than the body of a small virtual method. That is monomorphic, polymorphic and megamorphic, and why hot dispatch gets specialised.

Real predictors index the counter by recent branch outcomes as well. Pick a repeating pattern, then add bits of global history until the bar drops to zero:

A period-six pattern is invisible with four bits — ten of sixty wrong — and perfectly predictable with five. The threshold depends on the pattern, not its length, which is why TAGE keeps several history lengths at once. It is also what Spectre trains.

The first half is more hardware: several execution ports and a front end wide enough to feed them. The second half is finding instructions that do not depend on each other.

Widen the issue and watch independent work finish sooner while the chained version refuses to move:

Twelve independent operations go from fifteen cycles to six at four-wide, then stop improving — the core has four ports and a fifth slot has nowhere to send anything. The chain takes forty-eight cycles at every width: width cannot help a queue of one.

That is the shape of almost every disappointing optimisation. A reduction into one accumulator is a chain a million links long. Add accumulators and watch each chain shorten until the throughput floor stops them:

One accumulator is 4.00 million cycles, 1.33 ms at 3 GHz; four is 1.00 million and 0.33 ms — exactly 4×, same instruction count. Past eight, each chain is shorter than the two-per-cycle limit and the floor binds: the ninth accumulator and the twelfth buy nothing.

A second kind of dependency is not real: two instructions that both write rax collide over a name, not a value. Turn renaming on and watch the wait that was never necessary vanish:

Without it, mov rax, 7 cannot issue until cycle 20 — it is waiting for a divide whose result it overwrites — and its dependants finish at 23. Renaming gives it a fresh physical register, so it issues at cycle 0 and its dependants are done by cycle 3.

Which raises the obvious worry, and the answer is the machine's central promise: the architectural state after instruction N retires is exactly what a machine running one instruction at a time would have produced. Watch execution finish out of order while commit stays in it:

Because commit is in order, nothing becomes visible early: the last three finish by cycle 3 and still retire after the divide, at 22, 23 and 24. That is what the reorder buffer buys — and it is also why an exception can be delivered at exactly the right instruction.

Its size decides how far ahead the core can look for independent work, and looking ahead is how it overlaps cache misses. Widen the window over a loop that misses DRAM every eighth instruction and watch the misses it holds at once multiply:

Eight entries hold one miss at a time, so each costs the full 250 cycles; eighty hold ten, at 25 each. Then it stops — ten fill buffers, so the eleventh miss waits however large the window is. Skylake's ROB is 224 and Golden Cove's 512; neither binds here.

Which answers “why is pointer chasing slow?”. A linked list gives the core one miss at a time by construction, so even a 512-entry machine sits at the left end of that slider: 250 cycles a node.

Memory has one more trap, invisible in the source. A load can be answered out of the store buffer only if the store fully contains it. Slide the load across the store and find the positions where forwarding fails:

Inside the store the load costs 5 cycles; straddling its edge the hardware gives up, drains to L1 and replays — 18 cycles for the same C statement, and it fails silently.

It is not free even when it works. Between fetching a branch and resolving it, a four-wide front end keeps pouring instructions into the machine on the strength of a guess. Step through the seventeen cycles of the shadow and watch the work built on that guess pile up before it becomes work that gets discarded:

Sixty-eight µops at four-wide, 102 at six-wide — all decoded, renamed, scheduled, often executed, then deleted. Widening the machine makes a mispredict dearer, which is why width and predictor accuracy are designed together.

Architecturally the deletion is complete: no register, no memory location, no flag survives. That was the whole argument for speculation being safe — and where it has a hole, because caches were never architectural state.

Below is the Spectre v1 gadget. The bounds check has been trained taken; speculation reads past the end of the array and uses the byte it should never have seen as an index. Choose that byte, then step to the end:

Watch the last step. Every register is restored, the load never officially happened, and the program behaves as if the check had failed — but one line of the probe array is still cached, and which line depends on the secret. Nobody wrote a rollback for the cache.

Reading it back out is a timing measurement, and timing measurements under load are noisy. Turn the noise up until the line the attacker names stops being the line speculation touched, then average more repetitions until it works again:

At noise 0.80 a single measurement names line 9 and the attack is simply wrong. Averaging sixteen repetitions divides the noise by four and line 11 comes back clean. That is why proof-of-concept code loops thousands of times, and why capping high-resolution timers was the first browser mitigation shipped.

The real mitigations are structural, and they cost. Kernel page-table isolation gives user mode a page table with no kernel mappings, so every system call now switches address spaces. Raise the syscall rate and watch what the switch costs:

Two hundred thousand system calls a second costs 6.0% of a core with PCID, because the tagged TLB survives the switch — and 20.0% without it, because every switch then flushes the TLB.

Retpolines and IBRS add their own bills, and new side channels keep arriving. For anyone running untrusted code on shared hardware: the boundary you drew is architectural, and the machine underneath it is not.

double s = 0;                  // 4.00 M
for (i = 0; i < n; i++) s += a[i];

double s0=0, s1=0, s2=0, s3=0; // 1.00 M
for (i = 0; i + 3 < n; i += 4) {
  s0 += a[i];    s1 += a[i+1];
  s2 += a[i+2];  s3 += a[i+3];
}
s = (s0 + s1) + (s2 + s3);

• A megamorphic call in a hot loop. 12.8 cycles a call.
• A data-dependent branch over unsorted input. Partition upstream once.
• One accumulator in a reduction. 4× the latency, and it fails silently.
• A linked structure in a hot path. One miss in flight where an array holds ten.
• A load overlapping the store before it. 5 cycles becomes 18.