Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 40 ยท Systems and Performance

Performance: Pipelines, Caches and Branches

Why the same instructions can run at very different speeds: pipelines, latency vs throughput, branch misprediction and cache lines, with runnable simulators.

Count the instructions in two programs and you will often find the same number, yet one runs five times faster. Instruction count is a poor predictor of speed, because a modern CPU does not execute instructions one after another like our toy CPU does. It overlaps them, guesses which way branches will go, and keeps copies of recently used memory close by. If you can read assembly but know nothing about these three tricks, you will misjudge almost every piece of code you look at.

This lesson explains the tricks and then lets you watch them in small simulators. The simulators are models, not real silicon: the numbers they print are exact for the model and only illustrative for a real core. At the end we discuss why a compiler usually beats hand-written assembly and how to measure honestly, because that is where most performance work goes wrong.

Pipelining: many instructions in flight

An instruction needs several steps: fetch it, decode it, read its operands, execute, and write the result back. If the CPU finished all five steps for one instruction before starting the next, four of the five hardware units would sit idle at any moment. A pipeline keeps them all busy: while instruction 1 executes, instruction 2 is being decoded and instruction 3 is being fetched.

flowchart LR
  F["Fetch"] --> D["Decode"] --> E["Execute"] --> M["Memory"] --> W["Write back"]

A classic five-stage pipeline: each stage works on a different instruction in the same cycle.

Real cores go much further. They are superscalar (several instructions start per cycle) and out of order (an instruction whose inputs are ready may run before an earlier one that is still waiting). From the outside the program behaves as if it ran in order; inside, the CPU is finding independent work.

Latency versus throughput

Two numbers describe every instruction:

  • Latency: how many cycles pass between starting the instruction and its result being usable.
  • Throughput: how many such instructions the core can start per cycle when nothing is in the way.

An integer multiply on a typical recent core has a latency of about 3 cycles but can start one new multiply every cycle. So eight multiplies can cost anywhere from about 10 cycles to about 24, depending on one thing only: whether each one needs the result of the previous one. A chain of dependent instructions can only go as fast as the latency; independent instructions go as fast as the throughput.

The simulator below schedules a list of three-operand instructions on a one-instruction-per-cycle machine with a 3-cycle multiply. An instruction starts when the previous one has started and its inputs are ready.

JS Latency versus throughput

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The dependent chain takes 24 cycles and the independent version 10, for the same eight instructions. The last line is the practical lesson: if you must accumulate a sum or product in a loop, splitting it over several accumulators (and combining at the end) breaks the long dependency chain. Compilers do this for you only when it does not change the result, which for floating-point numbers is almost never, because rounding makes addition non-associative. That is why -O3 alone often leaves a floating-point reduction slow, and -ffast-math (which allows the change) speeds it up.

Branches and the cost of a wrong guess

A pipeline is a problem for a conditional jump. The CPU must fetch the instructions after the jl now, but the flags that decide the jump may not be known for several more cycles. So it predicts the direction, runs ahead speculatively, and checks later. A correct guess costs nothing. A misprediction throws away all the speculative work and restarts from the right place, which on current desktop cores costs very roughly 15 to 20 cycles, enough time to run dozens of instructions.

Predictors are simple counters at heart. The classic one is a 2-bit saturating counter per branch: states 0 and 1 predict "not taken", states 2 and 3 predict "taken", and each outcome nudges the counter one step. Two wrong guesses in a row are needed to flip the prediction, so a loop branch that is taken 999 times and falls through once costs one mispredict, not two. Better predictors also remember the last few outcomes of the branch (its history) and keep a separate counter for each pattern.

The simulator compares three predictors on 10,000 executions of the branch if (x >= 128) for three kinds of input.

JS Branch predictors on three kinds of data

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Read the table row by row. On random data every predictor is stuck near 50 percent: nothing can predict a coin flip. On sorted data the branch goes one way for 5,000 elements and then the other, so the counter and the history predictor almost never miss. The alternating pattern is the surprise: the plain 2-bit counter is wrong every time (it always lags one step behind), while the history predictor learns the pattern after a few rounds. This is exactly why a loop over sorted data can run several times faster than the same loop over shuffled data, a famous effect you can reproduce in C.

The fix, when data is unpredictable and the work in the branch is tiny, is to remove the branch: a conditional move (cmov on x86, csel on ARM64), or arithmetic that turns the comparison into a 0 or 1 mask. The lesson How if, switch and Ternaries Compile showed that layout; the trade is that a cmov always computes both values and has a data dependency, so it loses when the branch would have been well predicted.

Caches and cache lines

A multiply takes a few cycles, but fetching one value from main memory takes hundreds. CPUs hide that gap with a hierarchy of small, fast caches: L1 (tens of kilobytes, a few cycles away), L2, and L3 (megabytes, shared). Memory moves between levels in fixed blocks called cache lines, 64 bytes on current x86-64 and most ARM64 cores. Touch one byte and the CPU loads the whole 64-byte line around it.

flowchart LR
  R["Registers<br/>0 cycles"] --> L1["L1 cache<br/>about 4 cycles"] --> L2["L2 cache<br/>about 12 cycles"] --> L3["L3 cache<br/>about 40 cycles"] --> RAM["Main memory<br/>about 200+ cycles"]

Each level is bigger and slower than the one before it; the cycle counts are rough, order-of-magnitude figures.

Two habits follow. Spatial locality: use the neighbours of what you just touched, because they arrived for free in the same line. Temporal locality: reuse a value soon, before it is evicted. An array walked in order has perfect spatial locality: with 4-byte integers, one miss brings in 16 elements. The same array walked with a large stride uses one element per line and throws the other 15 away.

The next simulator models a 32 KB, 8-way, 64-byte-line L1 cache with least-recently-used replacement and sums a square matrix of 4-byte integers stored row after row, first along the rows and then down the columns. It counts only hits and misses; it does not model time.

JS Row-major or column-major? A cache simulator

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Row by row, every 16th access misses (6.3 percent, from the first touch of each line). Column by column with 512 columns, every access misses: the stride is 2,048 bytes, so consecutive accesses land in only two of the 64 sets and keep evicting each other, even though the cache is mostly empty. This is a conflict miss, and power-of-two strides are its classic cause.

The 500-column case is the instructive exception. One pass down a column touches 500 different lines, which still fit in the 512 lines of this cache, so the next 15 columns find their lines already loaded and the column walk is almost as cheap as the row walk. At 1,000 columns a single column pass needs 1,000 lines, the cache cannot hold them, and every access misses again. So locality has a working set threshold: the same code is fast until the data you revisit outgrows the cache. Real cores add prefetchers that detect strides, which softens these numbers, but the lesson holds: walk memory in the order it is laid out.

Why the compiler usually beats hand-written assembly

Everything above (scheduling for latency, unrolling into several accumulators, choosing cmov or a branch, aligning loops, vectorizing) is bookkeeping that depends on the exact CPU model, and it changes with each generation. A compiler knows the target's instruction timings and applies these transforms mechanically to every loop in a million lines. A person writing assembly by hand has to get the same details right once, for one CPU, and keep them right after every edit.

So the practical rules are:

  1. Write clear C (or Rust, or C++) first, with good data layout. Most speedups come from fewer cache misses and a better algorithm, which assembly does not change.
  2. Compile with -O2 (or -O3) and read the result with the habits from Reading Real Assembly from a C Compiler.
  3. Use intrinsics or the compiler's vectorization when you need SIMD (see Floating Point and SIMD).
  4. Hand-write assembly only for what the language cannot express: a special instruction, a few lines in a startup routine, a hot kernel in a crypto or codec library after profiling proved it.

Measuring correctly

Performance claims need evidence, and a micro-benchmark is easy to get wrong. A short checklist:

  • Run it many times and report the median or minimum, not one run; the first run pays for cold caches and page faults.
  • Prevent the compiler from deleting your test. If the result is never used, -O2 removes the whole loop and you "measure" zero. Print the result or store it through a volatile or an opaque sink.
  • Use real inputs. A branch that is perfectly predictable on your test data may be random in production.
  • Watch the machine. Frequency scaling, turbo boost, other processes and thermal limits all move the numbers; pin the process to a core and keep the load steady.
  • Read hardware counters when you can. On Linux, perf stat -e cycles,instructions,branch-misses,cache-misses ./prog tells you whether you are bound by branches, by memory, or by plain instruction count, instead of guessing.

The simulators in this lesson cannot tell you how fast your code is. They only show why two programs with the same instruction count differ, which is the first step to knowing which counter to read.

Timing JavaScript with Date.now() in a browser tab is a poor benchmark for all of these effects: the engine compiles and optimizes the code while it runs, timers are deliberately coarse, and other tabs compete for the CPU. That is why the demos above count events (cycles in a model, mispredictions, cache misses) rather than milliseconds.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Eight multiplies each need the result of the previous one. Compared with eight independent multiplies, they run...

    A dependent chain advances at the instruction's latency per step, while independent instructions can start every cycle (throughput). In the simulation: 24 cycles against 10.
  2. 2. Why is a loop with an if often much faster over sorted data than over shuffled data?

    On sorted data the branch goes one way for a long stretch and then the other, so predictors almost never miss. On random data about half the guesses are wrong, and each miss costs a pipeline flush.
  3. 3. What is a cache line?

    Memory moves in whole lines, so touching one byte also brings in its neighbours. That is why walking an array in order is cheap and striding across it is expensive.
  4. 4. Your micro-benchmark reports 0 nanoseconds per iteration at -O2. What is the most likely cause?

    If nothing observes the result, dead-code elimination removes the loop. Use the result (print it or store it through a volatile) so the work must happen.
  5. 5. When is hand-written assembly the right choice?

    Compilers know instruction timings and apply scheduling, unrolling and vectorization everywhere. Assembly pays off for special instructions, startup code and a few proven hot kernels.

Summary

  • Modern CPUs overlap many instructions (pipelining, superscalar and out-of-order execution), so instruction count alone does not predict speed.
  • Latency is the time until a result is usable; throughput is how often an instruction can start. Dependent chains are latency-bound, independent work is throughput-bound; extra accumulators break chains.
  • A branch is predicted and run speculatively; a misprediction costs very roughly 15 to 20 cycles. Predictable data (sorted, patterned) is cheap, random data is not; cmov or csel can remove unpredictable branches at the price of computing both sides.
  • Memory moves in 64-byte cache lines through L1, L2 and L3; use neighbours of what you touched (spatial locality) and reuse data soon (temporal locality). Large power-of-two strides cause conflict misses.
  • Compilers usually beat hand assembly; improve data layout and algorithms first, use intrinsics for SIMD, and keep assembly for what C cannot say.
  • Measure with repeated runs, real inputs, an observed result and hardware counters such as perf stat.

Next: see how the same low-level details become security holes, and how to defend, in Security: Buffer Overflows and Defenses.