Inside the Processor

A robot's camera hands its computer a picture the way a mosaic is built from tiles: as a grid of dots, each dot a pixel, stored as a number from 0 for black to 255 for white. A few lines of the robot's program walk through the numbers and add up the bright ones, every number of 128 or more, to judge how much of the scene is lit. The code is short, and it is correct.

Now the puzzle. In 2012 someone asked on a programming forum why that loop, run over a list of 32,768 such numbers 100,000 times, took 11.54 seconds, but only 1.93 seconds when they sorted the list first, before starting the stopwatch. The same numbers, the same additions, the same computer. Six times faster. This chapter finds out where the other ten seconds went, and the rest of the lesson opens up the machine that lost them.

The loop, twice

Here is the heart of the program from the question. It is written in C++, a close cousin of the language C. The first loop fills a list called data with 32,768 numbers: std::rand() % 256 means "a random whole number, keeping only the part from 0 to 255". The second pair of loops is the part that was timed. It walks the whole list 100,000 times, and for each number it checks the if and adds the number to sum when it is 128 or more.

c++// 32,768 numbers from 0 to 255, then read 100,000 times
const unsigned arraySize = 32768;
for (unsigned c = 0; c < arraySize; ++c)
    // like the brightness of 32,768 pixels
    data[c] = std::rand() % 256;

for (unsigned i = 0; i < 100000; ++i)       // the timed part
    for (unsigned c = 0; c < arraySize; ++c)
        if (data[c] >= 128)                 // the fork
            sum += data[c];

The sorted run added one line before the timer started: std::sort(data, data + arraySize);.

If you know Python better, here is the same idea in Python. The list is called numbers, and the if is the same test:

pythontotal = 0
for x in numbers:        # 32,768 numbers from 0 to 255
    if x >= 128:         # a bright one? This if is the fork.
        total += x

In Python the interpreter's own work per step is far larger, so the gap is smaller than in C, but it is still there: run the snippet above with both orders and time it yourself.

Look closely at what sorting did, and what it did not do. Sorting did not remove a single addition. Half the numbers are big in either order, and the loop adds exactly the same ones. Whatever made the sorted run faster, it was not less work.

What the computer really runs

To find the missing seconds we need three things from underneath the code. Picture a kitchen. The ingredients wait in a pantry. A cook follows a recipe one line at a time. Each line of the recipe is a small, plain action: take an egg, crack it, stir.

The list lives in the computer's large working store, where the numbers wait until the program needs them: its memory. That is the pantry.

The chip that carries out a program, one small step after another, is the processor. That is the cook. It cannot read Python or C. It only knows tiny steps, such as "load the next number from memory", "compare it with 128" or "add it to the total": instructions, the lines of the recipe. A program that translates your code into instructions, the way a translator turns a recipe from one language into another, is a compiler.

One more word. Many chips hold several complete processors, like several cooks in one kitchen, and each one is called a core. Our loop runs on one of them, and everything in this chapter happens inside that one core.

Our loop in six steps

Here is what the compiler makes of the loop, written as plain steps. Every number in the list goes round these six:

1. Load the next number from memory.
2. Compare it with 128.
3. If it is smaller, jump past step 4.
4. Add it to the total.
5. Step on to the next number.
6. If numbers are left, jump back to step 1.

Steps 3 and 6 are forks in the road: the processor either jumps somewhere else or carries straight on. An instruction like that, which either jumps to another place in the program or lets the processor carry straight on, is a branch, and every if in your code becomes one. Step 6 is the loop's own fork: it jumps back 32,767 times and falls through once, at the end of the list. Step 3 is the fork this chapter is about, because which way it goes depends on the number.

The clock

The processor takes its steps in time with an electrical signal that ticks at a steady rate, like a metronome: the clock. Each tick is one clock cycle, or just a tick. A step may take one tick, or several, or share a tick with other steps (Chapters 2 and 4 show how), but everything the processor does is counted in ticks.

The questioner did not say how fast their computer's clock ticked. The answer to the question re-ran the same test on a computer whose clock ticked 3.5 billion times a second, written 3.5 gigahertz, or GHz, so from here on we use its numbers. One tick lasts 1 ÷ 3,500,000,000 of a second. A billionth of a second is a nanosecond (ns), so one tick is under a third of a nanosecond: 0.286 ns.

Where time comes from

Now we can say exactly where a run's time comes from. Every second the clock ticks 3.5 billion times. So a run's time is the number of ticks it took, divided by 3.5 billion; or, the same thing, the number of ticks times the length of one tick.

The number of ticks is the number of instructions carried out, times the ticks each one took on average. How many instructions a run carries out, the number of steps in the recipe, is its instruction count. How many ticks each instruction takes, on average, is its cycles per instruction, or CPI: the minutes per recipe step, if you like.

Put together, a run's time is instructions × ticks per instruction × length of a tick. Hover over or tap each symbol:

time

How long the whole run takes, in seconds.

N

The instruction count: how many instructions the run carries out. Sorting did not change it.

C

The cycles per instruction (CPI): how many ticks each instruction takes, on average. This is what changed.

t

The length of one tick: 1 ÷ 3.5 GHz = 0.286 ns on the 2012 computer. It did not change.

Apply it to the puzzle. Sorting changed the order of the numbers, not the program: the same instructions ran, the same number of times. The computer was the same, so the tick was the same length. Two of the three factors are fixed, so the whole five-fold change sits in the middle one. The processor must have spent five times as many ticks on each number of the random list.

For our loop it is handier to count per number than per instruction: ticks per number = time × clock rate ÷ numbers read. The re-run read 32,768 × 100,000 = 3,276,800,000 numbers. In random order it took 11.777 seconds: 3.594 nanoseconds a number, which at 3.5 ticks a nanosecond is 12.58 ticks. Sorted, it took 2.352 seconds: 0.718 nanoseconds a number, 2.51 ticks. The worked example at the end of the chapter writes out every step.

random: 12.58 ticks a number · sorted: 2.51 ticks a number · 5.0 times

The guess

So where did ten extra ticks a number come from? The processor does not wait to find out which way your if goes. It guesses, and keeps working.

Here is why. Before the processor can know which way step 3 goes, it has to load the number and compare it, and that takes many ticks. Waiting at every fork would leave it standing idle most of the time. So it does not wait.

It guesses which way the fork will go and carries on down that road, like a walker who reaches a fork, picks the road that looks right, and keeps walking instead of standing still until someone brings a map. Guessing which way a branch will go before it is known, and carrying on down that road, is branch prediction.

When the guess is right, nothing is lost: the work done on the road is exactly the work that needed doing. When it is wrong, the processor throws away everything it did on the wrong road and goes back to the fork, like the walker turning round. A wrong guess is a misprediction, and the ticks it throws away are the mispredict penalty. Chapter 3 opens up how the guessing works; here we need only the fact that it happens.

Why sorting fixes it

The answer's own explanation is short. The numbers were spread evenly from 0 to 255. Sorted, the first half are all small: the processor skips, skips, skips. Then they are all big: add, add, add.

A processor that guesses "the same as last time" is wrong about twice in the whole list. In random order every number is a coin flip, big or small, and no guess can be right more than about half the time.

The price of one wrong guess

Now the arithmetic. The random run took 9.425 seconds longer. If about half of its 3,276,800,000 numbers were wrong guesses, that is 1,638,400,000 of them. 9.425 seconds shared among them is 5.75 nanoseconds each, and at 3.5 ticks a nanosecond that is 20.1 ticks thrown away per wrong guess.

Is 20 ticks believable? Measured directly on processors of that family, a wrong guess costs at least 17 ticks, so the answer adds up. It adds up the other way too: 2.51 + half of 20.1 = 12.56 ticks a number, and the measurement says 12.58. The sorted run's work, plus a wrong guess on every other number, is the whole random run.

Try it yourself. Set how often the chip guesses wrong and how much each wrong guess costs, and see which of the measured runs your two numbers land on.

Two numbers are enough. Half the guesses wrong at about 20 ticks each lands on the random run; no wrong guesses lands on the sorted run. Nothing else is needed to explain the gap: not slower memory, not a slower clock, not more additions.

The fix that needs no sorting

The same answer tried one more thing: it rewrote the loop without the if, adding either the number or zero with a small arithmetic trick (Chapter 3 shows it). Random order: 2.564 seconds. Sorted: 2.587. No fork, nothing to guess, and the order stopped mattering.

Compilers can do this rewrite by themselves, and many now do. That is why, if you run the 2012 loop on your own laptop today, you may see no difference at all. Chapter 2 shows the instructions a recent compiler really made from this loop.

The same test written in Java ran 10.93 and 5.64 seconds: about 2 times, not 5. The most likely reason is that a different compiler, Java's own, made different instructions, though the 2012 answer does not say so directly. The source code is not what runs. The instructions are.

A robot's code is full of forks like this one: is this pixel part of the marker, is the obstacle closer than a metre, has the whole message arrived. Where the data behind a fork is as unpredictable as camera noise, each fork can cost about 20 ticks, and nothing in the code looks slow.

worked exampleThe 2012 runs on a 3.5 GHz desktop processor
  numbers read   = 32,768 × 100,000            = 3,276,800,000
  random order    = 11.777 s ÷ 3,276,800,000
                     = 3.594 ns a number
  sorted          =  2.352 s ÷ 3,276,800,000
                     = 0.718 ns a number
  one tick        =  1 ÷ 3.5 GHz               = 0.286 ns
  ticks per number = 3.594 × 3.5 = 12.58  and  0.718 × 3.5 = 2.51
  random ÷ sorted = 11.777 ÷ 2.352              = 5.0 times

Where the extra 9.4 seconds went
  extra time      = 11.777 − 2.352              = 9.425 s
  per number      =  9.425 s ÷ 3,276,800,000    = 2.876 ns
  wrong guesses   =  half of 3,276,800,000       = 1,638,400,000
  per wrong guess = 9.425 s ÷ 1,638,400,000 = 5.75 ns
                     = 5.75 × 3.5 = 20.1 ticks
  check           = 2.51 + 0.5 × 20.1 = 12.56 ticks a number
                     (measured 12.58)

The other runs
  the question's own computer: 11.54 s ÷ 1.93 s
                     = 5.98, about 6 times
  the same loop in Java:       10.93 s ÷ 5.64 s
                     = 1.94, about 2 times
  without the if:  2.564 s random, 2.587 s sorted: no gap

Clock speed alone (illustrative, the failure story)
  3 GHz board, 1.5 ticks an instruction:
    1,000,000,000 × 1.5 ÷ 3,000,000,000 = 0.50 s
  2 GHz board, 0.8 ticks an instruction:
    1,000,000,000 × 0.8 ÷ 2,000,000,000 = 0.40 s
  the board with the slower clock wins by 0.50 ÷ 0.40 = 1.25 times

Faster clock, slower robot

What the team does. A team chooses between two boards, two small computers, for the robot's vision loop. One runs at 3 GHz, the other at 2 GHz. They pick the 3 GHz board without testing: "fifty percent more clock". The vision loop runs slower on it.

What you measure. Count the ticks and the instructions for the same loop on both boards (Chapter 3 shows the Linux tool that counts both). On the 3 GHz board the loop takes 1.5 ticks an instruction; on the 2 GHz board, 0.8 (illustrative numbers). For a billion instructions that is 0.50 seconds against 0.40: the slower clock wins by 1.25 times.

What you change. Compare processors by running your own loop and reading its ticks per instruction, never by the clock alone. The clock is one factor of three.

Every part of that story has machinery behind it: a clock that can only tick so fast, a line of stages that keeps several instructions moving, a guesser, and rules about who on the chip may do what. Here is the road, in order:

1. How the chip keeps time: why its clock can tick only so fast, and the assembly line that lets it tick faster.
2. The assembly line and its waits: our loop stepped through five stages, and the one wait no wire removes.
3. Guessing the fork: how the processor guesses, what a wrong guess costs, and how to take the fork away.
4. Doing later work early: how a big core runs ahead, and the chain it can never skip.
5. Many numbers per instruction: one instruction for many numbers, and what still limits the whole program.
6. Many cores, shared cores: several cores, two threads sharing one, and big cores beside little ones.
7. Who may do what: the chip's own rules about which software may touch what, and why even the software in charge of the whole computer is not at the top.
8. What a crossing costs: the price of asking that software for help, and how much of your program it touches.
9. Field Guide: the checklist, the numbers and where each came from.

Your laptop's box says 3.5 GHz: three and a half billion ticks a second. Why not 35 billion? Nothing in the chip is lazy. The limit is a race that happens inside the chip on every single tick, and the clock can only tick as fast as the slowest runner in that race. This chapter watches the race, then shows the trick every modern processor uses to shorten it.

Switches, bits and gates

Start at the very bottom. A light switch has two positions, on and off. Inside the chip are billions of tiny electrical switches, each either on or off: transistors. On or off is all a computer knows.

A single 0 or 1, one switch's position, is a bit, and a number is a row of bits. The number 200, for example, is the row 11001000: 128 + 64 + 8.

A handful of switches wired together can compute one simple rule on bits, such as "1 only if both inputs are 1": that is a gate. Wire thousands of gates together and you get circuits that add, compare and choose. Engineers call such a network of gates logic. An adder is logic: feed it two numbers as rows of bits, and their sum comes out the other side as another row of bits.

Logic takes time

Change an adder's inputs and the answer does not appear at once. The change ripples through the gates like a line of dominoes falling, each gate waiting for the one before it, and for a moment the output flickers through wrong values before it settles. The time an answer takes to ripple through and stop changing is its propagation delay.

These delays are tiny. They are counted in trillionths of a second: picoseconds (ps), each a thousandth of a nanosecond. In this chapter's example the arithmetic part of the processor takes 200 ps, an illustrative value in the style of the classic textbook. That is fast, but it is not zero, and this whole chapter turns on it not being zero.

Registers: a photograph per tick

So how does the chip keep a clean answer from one step to the next, when the logic in between is a flickering blur? It photographs it. A register is a row of storage cells that holds a number and takes a new value only on the tick: at the tick it captures whatever is at its input, and it holds that value steady until the next tick, whatever the logic in front of it does in between. Think of a camera that takes exactly one photograph on every tick of the metronome, and shows that photograph until the next tick.

The gap between two beats of the metronome, the time from one tick to the next, is the clock period. At 3.5 GHz it is 286 ps; at 1 GHz, 1,000 ps. Choosing the clock period is choosing how long every race inside the chip is allowed to take.

The race, rule one

Picture two registers, A and B, with some logic between them. At a tick, register A takes its photograph. Its new value appears at its output a moment later, like a camera's shutter lag: the register's clock-to-output delay, t_pcq. Then the value ripples through the logic to register B, taking the propagation delay, t_pd, of the slowest path between them. And it must arrive, and hold still, a moment before the next tick at B, the way you hold still for a photograph: that moment is B's setup time, t_setup.

So the clock period must cover all three: the time for A to show its value, plus the time for the answer to ripple through, plus the time B needs it to hold still. Add one small term for the tick itself. It reaches different registers at slightly different moments, which engineers call skew, and a tick that reaches B early eats into the margin, the spare time left over once t_pcq, t_pd and t_setup are subtracted from the clock period.

T_c

The clock period: the time from one tick to the next.

t_pcq

The register's clock-to-output delay: how long after the tick its new value appears.

t_pd

The propagation delay of the slowest path of logic to the next register.

t_setup

The setup time: how long the answer must hold still before the next tick.

t_skew

Skew: how much later the tick may reach one register than another.

The slowest runner decides when the whistle can blow. Every pair of registers on the chip runs its own race, and the slowest path between any two registers sets the clock for the whole chip: it is the critical path. Make every other path faster and the clock cannot move; shorten the critical path and it can.

Rule two: too fast is also a problem

The photograph has a second condition. The input must stay still for a moment after the tick too, the way you must not move until the flash is over: the hold time, t_hold. The danger here is the fastest path, not the slowest. If a new value can race through a very short path and arrive while register B is still taking its photograph, the photograph is spoiled.

So there is a second rule. The soonest a new value can start to leave A, plus the delay of the fastest path from A to B, must be longer than B's hold time, plus any skew:

t_ccq

The soonest a register's output can start to change after the tick.

t_cd

The delay of the fastest path of logic.

t_hold

The hold time: how long the input must stay still after the tick.

t_skew

Skew: how much later the tick may reach one register than another.

no T_c in the hold rule: a slower clock cannot fix it

Look at what is missing from this rule: the clock period. Slowing the clock cannot fix a hold problem; only adding delay to the too-fast path can. Here is one with illustrative numbers: a short path that starts changing 20 ps after the tick and takes 10 ps to cross, 30 ps in all, against a hold time of 25 ps plus 10 ps of skew, 35 ps. It fails at every clock speed, because nothing in that sum is the clock. Adding 10 ps of delay to the path makes it 40 ps, more than 35, and fixes it.

Five jobs for every instruction

Now the instructions themselves. First, the words memory needs. Memory is counted in bytes of 8 bits, and every byte has a number, its address, like a house number on a long street. A 32-bit number takes 4 bytes, a word. Copying a number from memory into a register is a load, like fetching an ingredient from the pantry; putting a number from a register back into memory is a store.

Making a sandwich takes five jobs: take the order, work out what it needs and gather it, do the cutting, fetch anything missing from the pantry, and hand it over. Every instruction goes through the same five jobs, and engineers shorten them to IF, ID, EX, MEM and WB:

1. Fetch the instruction from memory.
2. Decode it, working out what it asks and reading the registers it names.
3. Execute it: the arithmetic (for a load, working out the address).
4. Memory: load or store a number if the instruction asks.
5. Write back its result into a register.

A load uses all five: it fetches its instruction, reads the register holding the address, adds to work out the address, reads the number from memory, and writes it into a register. An add skips the memory job, because it has nothing to fetch from the pantry.

One tick per instruction

The simplest processor does all five jobs of an instruction inside one tick, like one person making the whole sandwich from order to hand-over: a single-cycle processor. Between its two registers, one at the start of the tick and one at the end, sits all five jobs' worth of logic, so its tick must fit the slowest instruction's whole journey.

Put numbers on it, using the classic textbook's teaching values (illustrative, not any real chip): fetch 200 ps, decode 100, execute 200, memory 200, write back 100. That is 800 ps of logic, plus 30 ps for a register to show its value and 20 ps of setup: 850 ps a tick, 1.18 GHz. Every instruction gets the whole 850 ps, even an add that never uses the memory job.

What the instructions are

The full list of instructions a processor understands is its instruction set, like a language's vocabulary. A good one to learn from is RISC-V, an open instruction set anyone may build a processor for. Its simplest version, RV32I, has 40 instructions, each 32 bits long, and every one of them goes through the same five jobs. Forty is few enough to write a processor for in an afternoon, which is what the lab at the end of this chapter does.

The assembly line

Now picture a sandwich counter with five people in a row. One takes the order, one works out what it needs and gathers it, one does the cutting, one fetches anything missing from the pantry, one hands it over. Every few seconds each passes their sandwich to the next. Five sandwiches are in progress at once, and one comes off the end at every step.

Put a register between each pair of jobs and the processor becomes the same counter: a pipeline, with five stages and a pipeline register between each pair. Each stage works on a different instruction, and at every tick each pipeline register photographs its stage's answer and hands it to the next stage. Now the logic between two registers is only one stage, so the tick only has to fit the slowest stage: 200 + 30 + 20 = 250 ps, 4.0 GHz.

one tick per instruction: 30 + 800 + 20 = 850 ps · five stages: 30 + 200 + 20 = 250 ps

Try both below. Start with one tick per instruction at 850 ps and shorten the tick until something breaks. Then switch to five stages and do it again.

Latency and throughput

The line did not make any instruction faster. One instruction now takes five ticks of 250 ps from start to finish: 1,250 ps, longer than the 850 ps of the single-cycle processor. How long one instruction takes from start to finish, one sandwich's time from order to hand-over, is its latency. The line made latency worse, by 1.47 times.

What it improved is throughput: how many instructions finish each second, the sandwiches served per hour. Once the line is full, one instruction finishes every tick. A thousand instructions take (1,000 + 4) × 250 ps = 251 ns, against 1,000 × 850 ps = 850 ns: 3.39 times sooner. The 4 extra ticks are the time it takes to fill the line at the start, before the first instruction reaches the end.

Why 3.39 and not 5? The stages are not equal: the 100 ps stages idle half of every tick, waiting for the 200 ps ones. And every stage pays the registers' 50 ps. Five equal stages of 160 ps with free registers would give exactly five times: 800 ÷ 160 = 5. Here is the whole budget in a few lines of Python, with its real output:

python# timing.py: how fast can the clock tick?
# (illustrative delays, in picoseconds)
stages = {
    "fetch": 200, "decode": 100, "execute": 200,
    "memory": 200, "write back": 100,
}
# a register's own times: show the new value,
# hold still before the tick
t_pcq, t_setup = 30, 20

# a whole instruction between two registers
one_tick = t_pcq + sum(stages.values()) + t_setup
# only the slowest stage between two registers
five_stage = t_pcq + max(stages.values()) + t_setup

print(f"one tick per instruction: {one_tick} ps a tick, "
      f"{1000 / one_tick:.2f} GHz")
print(f"five-stage line:          {five_stage} ps a tick, "
      f"{1000 / five_stage:.2f} GHz")
n = 1000
print(f"{n} instructions: {n * one_tick / 1000:.0f} ns against "
      f"{(n + 4) * five_stage / 1000:.0f} ns")
print(f"one instruction, start to finish: {one_tick} ps against "
      f"{5 * five_stage} ps")

outputone tick per instruction: 850 ps a tick, 1.18 GHz
five-stage line:          250 ps a tick, 4.00 GHz
1000 instructions: 850 ns against 251 ns
one instruction, start to finish: 850 ps against 1250 ps

Deeper lines

Chips cut instructions into more and more stages to shorten the tick. Even the Cortex-M85, a small processor design made for the cheap one-chip computers inside gadgets, uses seven stages for ordinary instructions, and the big processors in laptops use more. One careful measurer notes that on Intel's Core 2 a wrong guess costs about 15 ticks, "corresponding to the length of the pipeline". A deeper line ticks faster, and throws away more work on every wrong guess. That trade is Chapter 3.

worked exampleIllustrative delays (the classic textbook teaching
  values, not any real chip)
  logic: fetch 200 + decode 100 + execute 200 + memory 200
    + write back 100                           = 800 ps
  each register: 30 ps to show its new value
    + 20 ps setup                              = 50 ps

One tick per instruction
  tick   ≥ 30 + 800 + 20                      = 850 ps
  clock  = 1 ÷ 850 ps                         = 1.18 GHz
    1.18 billion instructions a second

Five stages
  tick   ≥ 30 + 200 + 20                 = 250 ps   (the slowest stage)
  clock  = 1 ÷ 250 ps                         = 4.0 GHz
    one instruction finishes every tick
  1,000 instructions: (1,000 + 4) × 250 ps    = 251,000 ps
    = 251 ns, against 1,000 × 850 = 850 ns: 3.39 times sooner
  one instruction alone: 5 × 250 ps           = 1,250 ps
    against 850 ps: 1.47 times longer
  why not 5 times: 850 ÷ 250 = 3.4; five equal 160 ps stages
    with free registers: 800 ÷ 160 = 5.0

Pushing the clock too far (setup)
  a 240 ps tick on the five-stage line: the 200 ps stages need
    250 ps, so answers arrive late: wrong results

Hold (illustrative)
  shortest path: 20 ps + 10 ps = 30 ps must be more than hold
    25 ps + skew 10 ps = 35 ps: fails at every clock speed
  add 10 ps of delay to that path: 40 ps > 35 ps: fixed

Faster, then wrong

What happens. A builder raises the clock of a robot's board to squeeze more frames a second out of its vision loop: overclocking, running a chip's clock faster than it was sold to run. It works for an hour. Then one multiplication comes out wrong, and the arm twitches.

What you measure. Run a calculation whose right answer you know, billions of times, at each clock setting, and count the wrong answers. They appear only above a certain speed, and only now and then: the slowest paths, with the unluckiest inputs, no longer settle before the tick.

What you change. Back the clock down to where every path settles with room to spare. And know the one timing fault a slower clock cannot fix: a path so fast that it changes a register's input while it is still taking its photograph. That fails at every speed, and only a change to the chip's design, adding delay to that path, fixes it.

The lab below is Chapter 1's single-cycle processor written in Python: it fetches one instruction per tick, decodes it and does what it says. You write the parts that touch memory and the fork, and it sorts a list of numbers from 0 to 255.

Back at the sandwich counter, an order comes in: toast the bread, then melt cheese on the toast. The cheese person is next in line after the toaster, and when the cheese person's turn comes, the toast is not ready. They stand and wait, and an empty tray moves down the counter behind them.

Our loop has exactly this problem. Chapter 1's line finishes one instruction every tick, and our loop has six instructions for each number, so a number should take six ticks. Step it through the line and count: a number that gets added takes twelve.

The loop as the processor sees it

Here are the six steps from Chapter 0, written as RISC-V instructions. Instructions written as short words, one per line, so a person can read them, like a recipe in shorthand, are assembly language. Each line is one instruction; the words after the # are comments for people.

risc-v assemblyloop: lw   t0, 0(a0)    # load the number at the address in a0 into t0
      slti t1, t0, 128     # t1 = 1 if the number is below 128, else 0
      bnez t1, skip        # if t1 is not 0, jump to skip (do not add)
      add  a1, a1, t0      # total = total + number
skip: addi a0, a0, 4    # step a0 on to the next number, 4 bytes along
      # if a0 has not reached the end (a2), jump back to loop
      bne  a0, a2, loop

Read it line by line, like labelled trays on the counter: t0, t1, a0, a1 and a2 are the names of five of the processor's registers. a0 holds the address of the next number, a1 the running total, a2 the address just past the end of the list. Each number is one word, 4 bytes, so stepping to the next means adding 4 to a0.

lw, load word, copies the word at the address in a0 into t0. slti, set if less than, puts 1 into t1 if the number is below 128, and 0 if not. bnez, branch if not zero, is the fork of our if: when t1 is 1 it jumps to skip, past the add. add adds the number to the total.

addi, add immediate, adds the fixed number 4 to a0. bne, branch if not equal, is the loop's own fork: until a0 reaches a2 it jumps back to loop. Six steps, exactly Chapter 0's list.

The first wait

Look at the second line. slti needs t0, the number that lw is still fetching from memory. On the line, slti enters decode one tick after lw, and decode is where an instruction reads its registers. At that moment lw has not even been to the memory stage. An instruction that needs a result an earlier instruction has not finished yet, the cheese person waiting for the toast, is a data hazard.

The simplest cure is to hold the waiting instruction back until the result has been written into its register in the write-back stage. The line keeps moving, so the held-back instruction leaves an empty slot travelling down it, like an empty tray on the counter: a bubble, also called a stall.

Counting the waits

How long is the wait? A register is written in write-back and may be read in decode in that same tick: the write happens in the first half of the tick, the read in the second. An instruction decoded at tick p executes at p + 1, uses memory at p + 2 and writes back at tick p + 3. The instruction right behind it would decode at p + 1, so it waits 2 ticks; two behind, it would decode at p + 2 and waits 1 tick; three behind, none.

In general: waits = 3 minus the distance, never below zero. Hover over or tap each symbol:

waits

The ticks an instruction is held back in decode.

3

The ticks from a producer's decode to its write-back, when the result can first be read.

d

The distance: how many instructions after the producer this one comes (1 = right behind).

slti after lw: 3 − 1 = 2 · bnez after slti: 2 · bne after addi: 2 · six waits a number

Apply it to our loop. slti waits 2 for lw, bnez waits 2 for slti, and bne waits 2 for addi: 6 bubbles. The add needs t0 too, but it comes three behind lw, so by its turn the number is in the register. A number that gets added costs 6 instructions and 6 bubbles, 12 ticks; a number that is skipped, 5 and 6, 11 ticks. Step it yourself. The device's second setting, Forward the answer, hands each result straight across instead of waiting for write-back; the next section explains why that helps, and where it cannot:

Forwarding

But the answer exists long before write-back. slti's result is complete at the end of its execute stage, sitting in the pipeline register behind it. Add wires that hand it straight to the execute stage of the instruction behind, and nobody waits for write-back. It is passing the toast straight across the counter instead of sending it round the back.

Extra wires that hand a result straight from one stage to the instruction right behind it, instead of waiting for write-back, are called forwarding, also called bypassing. The course notes this chapter follows name the two paths exactly: from the pipeline register after execute, and from the one after memory, straight into the arithmetic of the execute stage. Turn on "Forward the answer" in the device above: the waits after slti and addi vanish.

The wait no wire removes

One wait survives. Try forwarding on the first pair, tick by tick. lw is decoded at tick p, executes at p + 1 (it works out the address), and reads memory at p + 2: its number arrives at the end of tick p + 2. slti, right behind, would execute at tick p + 2, the same tick.

It needs the number at the start of that tick; the number exists only at the end of it. No wire carries a value backwards in time. So slti executes one tick later: one bubble.

An instruction that uses a loaded number in the very next slot is a load-use hazard. The course notes put it in one line: when the instruction right after a load uses the load's result, the hardware must stall for one cycle. With forwarding, a number that gets added costs 6 + 1 = 7 ticks, and a skipped one 5 + 1 = 6.

with forwarding: 1 tick after a load, 0 after anything else

Hiding it

The processor cannot remove that tick, but the program can fill it, the way a cook makes the salad while the toast browns. addi does not need t0, and lw has already used a0, so addi can move up between them: lw, addi, slti, bnez, add, bne. Now two instructions separate the load from its use, and forwarding covers it: no bubbles, 6 ticks for a number that gets added, 5 for one that is skipped.

Rearranging instructions so a gap is filled with work that does not depend on it is instruction scheduling. You rarely do it by hand: compilers do it for you, reordering code to improve performance. Switch on "Move addi up" in the device above and watch the last bubble go.

The fork problem

One more wait hides in the forks. The line fetches a new instruction every tick, but it only learns which way bnez goes when bnez reaches execute, and the classic design acts on it in the memory stage. Until then it keeps fetching as if the branch were not taken, straight down the page. The line must fetch the next instruction before it knows which way the fork goes: that is a control hazard, the fork in the road again.

When the branch is taken after all, the three instructions fetched behind it are thrown away, like tipping the wrong sandwiches into the bin: a flush, three ticks lost. Designs that decide in execute lose two; those that decide in decode, one.

Now run our loop under that fixed guess, "not taken", with forwarding on. bne jumps back on every number, so every number pays 3 more ticks; bnez jumps on every small number, 3 more. A big number costs 7 + 3 = 10 ticks, a small one 6 + 3 + 3 = 12: 11 on average, sorted or not. A fixed guess cannot see that the numbers were sorted. Chapter 3 builds guesses that can.

Real small processors

The small, cheap processors that run a robot's motor boards are microcontrollers: a small processor on one chip that runs one program. Arm designs processors that other companies build into their chips, and its Cortex-M family is made for microcontrollers. Their lines are short:

Being able to start two instructions in the same tick, like two counters side by side, is called superscalar. A two-stage line has almost nothing to throw away at a fork. A six- or seven-stage line ticks faster and has more to lose, which is why the Cortex-M7 guesses its forks.

What the compiler really made

Everything so far used the six instructions we wrote by hand. But the processor runs what the compiler wrote, and it may have written something else. The instructions as the bytes the processor actually reads are the program's machine code. To see them, you turn the machine code back into assembly with a disassembler; on Linux, objdump -d.

Machine code is printed in hexadecimal: base 16, with the digits 0 to 9 and then a to f, two digits per byte, often written with 0x in front. The hexadecimal 7f, for example, is 7 × 16 + 15 = 127. Here is what objdump -d shows for the hot loop of a recent compiler's RISC-V build of Chapter 0's function (trimmed to the machine code and the instruction):

objdump -d4398        lw    a4,0(a5)
0791        addi  a5,a5,4
00e65363    bge   a2,a4
953a        add   a0,a0,a4
fed79be3    bne   a5,a3

Read it line by line. The first column is the machine code. 4398 is four hex digits, two bytes: a compressed instruction, one of the short 16-bit forms of the most common instructions, from an optional part of RISC-V called the C extension. 00e65363 is eight digits, four bytes, a full-size one.

lw a4,0(a5): load the number at the address in a5 into a4. addi a5,a5,4: step to the next number, and look where it is: the compiler already moved it up behind the load, exactly the fix from a few paragraphs back. bge a2,a4: if a2 is at least the number, jump past the add; for the loop to add only numbers of 128 or more, a2 must hold 127. The compiler folded our compare and branch into one instruction. add a0,a0,a4: the total. bne a5,a3: not at the end yet, jump back. (objdump also prints the address each jump goes to after its operands; the listing here leaves it out.)

Five instructions a number, not six, in 14 bytes, and the fork is still there.

The budget that was wrong in both directions

What happens. A team budgets its vision loop from the C source. Six instructions a number, and for noisy camera pixels, 20 ticks lost on half of them. On the Arm board the loop runs far faster than the budget. On the RISC-V board it matches.

What you measure. Disassemble each build with objdump -d and read the loop. On RISC-V: five instructions and a bge; the fork is there, and noisy pixels pay for it. On Arm: ldr, cmp, add, csel, cmp, b.ne. There is no fork around the add.

Picture working out both answers and keeping one: csel, a conditional select, picks the new total or the old one without a fork, so nothing is guessed. On x86-64 the same idea is called cmovg. A64 is Arm's 64-bit instruction set; x86-64 is the instruction set of Intel's and AMD's processors.

Here is the Arm loop from the same compiler, trimmed the same way:

arm a64ldr   w1,[x2],#4
cmp   w1,#0x7f
add   x1,x0,w1,sxtw
csel  x0,x1,x0,gt
cmp   x2,x3
b.ne

ldr w1,[x2],#4 loads the number and steps the address on by 4 in one instruction. cmp w1,#0x7f compares the number with 127 (0x7f in hexadecimal), add works out total + number, and csel x0,x1,x0,gt keeps that new total only if the number was greater than 127. No fork around the add.

What you change. Budget from the disassembly of the exact build, with the compiler, its version and its flags (the settings it was run with, such as -O2) written down, never from the source. A new compiler, or one changed flag, can put the fork back or take it away.

Density

The same function, whole, takes 38 bytes on RISC-V with compressed instructions, a build named RV64GC (9 of its 14 instructions are short ones), 56 bytes without them, a build named RV64G, 56 on Arm's A64 and 46 on x86-64. How many bytes a piece of code takes for the same work is its density: fewer bytes, denser code. The short forms save about a third of the space: 38 ÷ 56 = 0.68. On a microcontroller with little room for code, a third is a lot.

worked exampleOur loop on the teaching line, one number, every fork
  guessed right
  waits without forwarding: 3 minus the distance, never below 0
    slti after lw (1 apart): 2    bnez after slti (1 apart): 2
    bne after addi (1 apart): 2                     = 6 bubbles
    a number that is added:   6 instructions + 6 bubbles = 12 ticks
    a number that is skipped: 5 instructions + 6 bubbles = 11 ticks
  with forwarding: only the load's user waits, 1 tick
    added: 6 + 1 = 7 ticks    skipped: 5 + 1 = 6 ticks
    half and half: 6.5 ticks a number
  addi moved up behind the load (lw, addi, slti, bnez, add, bne)
    without forwarding: 3 bubbles (slti 1, bnez 2): 9 and 8 ticks
    with forwarding:    0 bubbles:                  6 and 5 ticks

Forks on the teaching line, always guessing "not taken", 3 ticks
  lost per taken branch
  bne jumps back on every number (+3), bnez jumps on every small
    number (+3)
    added: 7 + 3 = 10    skipped: 6 + 3 + 3 = 12
    average 11.0 ticks, sorted or random

What gcc 14.2 made of the loop (-O2 -fno-tree-vectorize)
  RV64GC hot loop: 5 instructions, 2 + 2 + 4 + 2 + 4 = 14 bytes,
    keeps the fork (bge)
  A64 hot loop:    6 instructions, 6 × 4 = 24 bytes,
    no fork around the add (csel)
  x86-64 hot loop: 8 instructions, 3 + 3 + 3 + 3 + 4 + 4 + 3 + 2
    = 25 bytes, no fork around the add (cmovg)
  whole function:  RV64GC 38 bytes (9 of 14 compressed); RV64G 56;
    A64 56; x86-64 46
  compressed saving: 38 ÷ 56 = 0.68, about a third smaller

In the lab you write the rule that decides when an instruction may enter decode, with forwarding and without, and watch the bubbles appear in the line.

A barista at a busy café knows that the man in the grey coat always orders a flat white, so she starts steaming the milk as he walks through the door. Most mornings she hands it over the moment he pays. The morning he asks for tea, she tips the milk away and starts again: a little time lost, far less than she wins on all the other mornings. Your processor does the same thing at every fork in your program, billions of times a second.

Why guess at all

In Chapter 2's line, the processor learns which way a fork goes two or three ticks after fetching it. A big processor fetches far more per tick: one big Arm core has been measured fetching and decoding ten instructions per tick. The part of the core that fetches and decodes instructions, the order counter of the café, is its front end. Waiting at every fork would leave that front end idle for many ticks, ten instructions' worth of work lost for each one.

So processors like these do what the barista does. They guess, and keep fetching, decoding and even computing down the guessed road, keeping the work only if the guess was right. Working down the guessed road before the fork is settled, and keeping the work only if the guess was right, is speculative execution. A branch that jumps is taken; one that lets the processor carry on is not taken. And the part of the core that makes the guesses, the barista's memory of her regulars, is the branch predictor.

The fixed guess

The simplest predictor always makes a flat white. Chapter 2's line used one fixed guess for every fork, "not taken": static prediction. For our loop that is wrong on every backward jump and on every small number: 11 ticks a number, sorted or not. A fixed guess cannot learn anything, including that the numbers were sorted.

Same as last time

The simplest guesser that learns remembers what this fork did last time and guesses the same: a one-bit predictor, since one bit is enough to remember "jumped" or "did not". It is good at forks that keep doing the same thing, and it has one weakness worth watching.

Take a loop of 8: its fork jumps back seven times and then falls out. That fools the one-bit guesser twice per pass. At the exit it guessed "jump", and the loop ended. Then, at the next pass's first jump, it remembers "fall out" and guesses wrong again. Six right out of eight: 75%.

In general a loop of N passes is guessed right 1 − 2 ÷ N of the time, so a loop of 100 gives 98%.

Two strikes

Better: make the guesser need two surprises in a row to change its mind. Keep a counter from 0 to 3. Step it up after a taken branch and down after a not-taken one, and stop it at the ends; 0 and 1 guess not taken, 2 and 3 guess taken. That is a two-bit saturating counter, "saturating" because it stops at 0 and 3 instead of wrapping around.

At a loop's exit the counter drops from 3 to 2 and still guesses "jump", so the next pass costs nothing: one wrong guess per pass, 7 of 8, 87.5%; a loop of 100, 99%. But on a fork that alternates, jump, fall through, jump, fall through, it swings between 0 and 1 and is right only half the time: 50%. Here is the whole counter in a few lines of Python, with its real output:

pythondef two_strikes(pattern):
    # 0 and 1 guess "no jump", 2 and 3 guess "jump"
    c, right = 0, 0
    for jumped in pattern:
        right += (c >= 2) == jumped
        # one step toward what happened, never past 0 or 3
        c = min(3, c + 1) if jumped else max(0, c - 1)
    return right / len(pattern)

# one pass of a loop of 8, starting cold
print(two_strikes([True] * 7 + [False]))
print(two_strikes(([True] * 7 + [False]) * 1000))   # a thousand passes

output0.625
0.87475

Cold, on a single pass, it is right 5 times out of 8 while it climbs from 0 to 2 (the first two jumps are guessed wrong, the next five right, the exit wrong); over a thousand passes it settles at 87.5%, the 0.025% gap being those first two wrong guesses.

A memory of the last few forks

Some forks follow a pattern that only makes sense in context: an alternation, or a loop's exit that comes after exactly seven jumps. A barista who remembers the last eight orders can tell that after two flat whites the grey coat always asks for tea. So keep the outcomes of the last few forks as a row of bits, the history, and give every different recent history its own counter.

One well-known design from 1993 does exactly this. It combines the history with the fork's own address in memory using XOR, a bit-by-bit rule that gives 1 where two numbers differ and 0 where they agree (1100 XOR 1010 is 0110), and uses the result to pick the counter. Its name is gshare. With 8 bits of history, each position inside the loop of 8, and each phase of the alternation, lands on a counter of its own, because the last eight outcomes are different at every position.

Once the counters have learned, the history guesser is right every time: 100%. Learning takes a while, because each counter starts knowing nothing: the history guesser needs 21 wrong guesses on the loop, and 6 on the alternation, before it settles. Race all three on the same patterns:

Random and sorted

Now feed all three the random pattern from Chapter 0. Each lands near 50%, the same as a coin. There is no pattern to learn, and a guesser can only learn patterns. Then feed them the sorted list: 16,384 small numbers, then 16,384 big ones. At the one switch, "same as last time" is wrong once, "two strikes" twice and the history guesser once, and then right for the rest of the list.

That is Chapter 0's mystery, solved from the inside: the sorted list is one long, easy pattern, and the random list is no pattern at all.

Newer guessers, and where jumps go

Guessers have kept growing. A 2006 design is named for what it keeps, tagged geometric history lengths: histories of several lengths, each longer than the last by a fixed factor. Its name is TAGE.

Guessing the direction is half the job. The front end must also know where a jump goes before it has decoded it, or it cannot fetch from there. So it keeps a table of where each jump went last time, the branch target buffer. It also keeps a small stack of return addresses for function calls, the return stack, like a stack of bookmarks: when a function finishes, the program must jump back to wherever it was called from, and the top bookmark says where. On the big Arm core measured above, the first table tracks about 2,048 jumps, slower tables up to 16,384 with targets two to three ticks later, and the return stack holds 29 addresses.

What a wrong guess costs

Every wrong guess throws away the work in flight behind the fork, so its cost follows the length of the line. Here is what careful measurements found on well-known processors:

Chapter 0's arithmetic found 20.1 ticks on its desktop processor, which agrees with the at least 17 measured for that family.

Why the same fork costs more on a bigger machine

Write the ticks a number costs as the work plus the wrong guesses: ticks = b + m × P, where b is the work per number, m the share of guesses that are wrong and P the ticks each wrong guess throws away.

ticks

The ticks one number costs, on average.

b

The ordinary work per number: 6.5 ticks on the teaching line, 2.5 on the big-core toy.

m

The share of guesses that are wrong: about one half in random order, almost none sorted.

P

The ticks each wrong guess throws away: 1 to 3 on the teaching line, about 20 on a big core.

On Chapter 2's teaching line, with forwarding and half the numbers added, b = 6.5, and a wrong guess settled in the memory stage costs P = 3. Random data costs 6.5 + 0.5 × 3 = 8.0 ticks against 6.5 sorted, only 1.23 times more. On a big core, b = 2.5 and P = 20, the numbers Chapter 0 worked back from the measurement: 12.5 against 2.5, 5.0 times.

teaching line: 6.5 + 0.5 × 3 = 8.0, 1.23 times · big core: 2.5 + 0.5 × 20 = 12.5, 5.0 times

The big core does the ordinary work of a number in fewer ticks, because it overlaps many instructions (Chapter 4), and it throws away more per wrong guess, because its line is deeper. Both push the ratio up. The same fork, the same data: a mild nuisance on a small line, the whole story on a big one.

Finding a bad fork: count

You do not have to guess which forks are guessed badly. The processor counts, like a tally counter clicking at a door: it has circuits that count events such as ticks, finished instructions and wrong guesses, called performance counters. Linux, the software in charge of many robots' computers (Chapter 6 says more about it), has a tool for reading them around one program: perf stat. You name the events you want counted after -e, and the program to run after them:

shellperf stat -e cycles,instructions,branches,branch-misses ./filter

Here is the example output printed in perf's own manual:

perf stat   229,570,665,834      cycles:u                  #    2.742 GHz
   313,163,853,778      instructions:u         #    1.36  insn per cycle
    69,704,684,856      branches:u                #  832.559 M/sec
     2,078,861,393      branch-misses:u       #    2.98% of all branches

Read it line by line. cycles is ticks: 229.6 billion. instructions is instructions finished: 313.2 billion. perf divides the two and prints 1.36 insn per cycle: instructions finished per tick, which is called IPC, the flip side of Chapter 0's CPI (1 ÷ 1.36 = 0.73 ticks an instruction).

branches is forks: 69.7 billion. branch-misses is wrong guesses: 2.08 billion, which perf prints as 2.98% of all branches. The :u after each name means perf counted only the instructions of the program itself, and the GHz and M/sec figures are perf's own arithmetic on the counts and the time.

2.98% sounds small. But multiply it by the price. At about 20 ticks each, 2,078,861,393 wrong guesses cost 41.6 billion ticks: 18.1% of all 229.6 billion. Remove every one and the program could run at most 1.22 times faster.

worked exampleGuessers on made-up patterns, after they settle
  a loop of 8 (7 jumps, then fall out):
    same as last time 1 − 2/8 = 75.0%   two strikes 1 − 1/8 = 87.5%
    history 100%
  a loop of 100:
    1 − 2/100 = 98%   1 − 1/100 = 99%
  alternating:
    0.0%   50.0%   100%
  random (coin flips):                  about 49 to 51% for all three
  sorted halves: wrong only at the switch (once, twice, once), then
    right: 100.0% to one decimal

The same fork on two machines: ticks = b + m × P
  teaching line: b = 6.5, P = 3:  6.5 + 0.5 × 3  =  8.0 against 6.5:
    1.23 times
    deciding in execute (P = 2): 7.5, 1.15 times;
    in decode (P = 1): 7.0, 1.08 times
  big-core toy:  b = 2.5, P = 20: 2.5 + 0.5 × 20 = 12.5 against 2.5:
    5.0 times

Reading perf's own example
  instructions ÷ cycles  = 313,163,853,778 ÷ 229,570,665,834
    = 1.36 per tick (IPC), 0.73 ticks an instruction (CPI)
  branch-misses ÷ branches = 2,078,861,393 ÷ 69,704,684,856
    = 2.98% of all forks
  wrong guesses per 1,000 instructions = 6.64
  at about 20 ticks each: 2,078,861,393 × 20 = 41.6 billion ticks
    = 18.1% of all ticks  (15 ticks: 13.6%; 10 ticks: 9.1%)
  remove every wrong guess: at most 1 ÷ (1 − 0.181) = 1.22 times faster

Gravel is slower than floor

What happens. A robot's obstacle filter keeps only the pixels above a brightness threshold. On camera frames of a smooth floor it keeps up with the camera; on frames of gravel, with exactly the same number of pixels, it falls behind.

What you measure. Run perf stat -e cycles,instructions,branches,branch-misses on the filter, once on a floor frame and once on a gravel frame. The gravel run shows far more branch-misses and a lower IPC: the threshold's if is a fork on noisy data, and noise is a coin flip.

What you change. Take the fork away. Code that computes the same answer with no fork is branchless code. Write the step so it adds the pixel or zero without an if, like the trick below; or keep the plain if and let the compiler turn it into a conditional select by itself, which compilers call if-conversion.

Check the disassembly (Chapter 2): a recent gcc, told not to use Chapter 5's many-numbers instructions, already turned this if into csel on Arm and cmovg on x86-64, and kept the fork on RISC-V. Sorting also works, as in Chapter 0, but only when the data can be put in order more cheaply than the wrong guesses cost; the 2012 test sorted before starting its stopwatch. Then measure again.

Here is the branchless trick from the 2012 answer, in C:

c/* all ones (-1) if the number is below 128, all zeros
   if not */
int t = (data[c] - 128) >> 31;
/* ~t flips it: keep the number, or keep nothing */
sum += ~t & data[c];

Step by step: data[c] − 128 is negative exactly when the number is below 128. Computers store a negative number so its leftmost bit is 1 (this lesson does not derive why); shifting a 32-bit number right by 31 places copies that leftmost bit all the way across, leaving only its sign: all ones for a negative number on the compilers this trick was written for, all zeros otherwise. ~t flips every bit, and & keeps the number where ~t is all ones and wipes it where it is zero. C leaves the right shift of a negative number to each compiler, which is one more reason to prefer letting the compiler write its own select. (If that bit trick is unfamiliar, the numpy version below keeps or drops each number with no bit shifting at all.)

In Python with numpy the same idea is a select over the whole list at once, with no fork per number:

pythonimport numpy as np
# 32,768 numbers from 0 to 255
x = np.random.default_rng(0).integers(0, 256, 32768)
# keep each number or 0, then add them all
total = int(np.where(x >= 128, x, 0).sum())

In the lab you build the two-strike counter and the history guesser yourself, and race them on the same four patterns.

An order comes into a kitchen: soup, a salad and bread. The soup needs twenty minutes on the stove. A good cook does not stand watching the pot. She starts the soup, makes the salad and slices the bread while it simmers, and plates everything together at the end. A cook who worked strictly down the ticket would stand idle for twenty minutes.

Now hand her an order where every dish needs the one before it: roast the bones, make the stock from the bones, make the sauce from the stock. No amount of cleverness makes that order faster. This chapter is about both kinds of order, and why a robot's map, stored the wrong way, becomes the second kind.

The line stops for slow things

Chapter 2's line takes instructions strictly in order, so one instruction that waits holds up everything behind it. Most waits are a tick or two, like the load-use bubble. But a number that has to come from far away in memory can take hundreds of ticks, and everything behind it stands still for all of them, even instructions that have nothing to do with that number.

Out of order

A big core does what the good cook does. It fetches far ahead into a waiting area and runs any instruction whose inputs are ready, even ahead of earlier ones that are still waiting: out-of-order execution. The waiting area of instructions it has fetched but not finished, like the rail of tickets above the stove, is the reorder buffer, or the window.

The shuffle stays inside the core. Results are made official strictly in program order, the way a kitchen plates dishes in the order they were ordered, however they were cooked: this is retiring each instruction in turn, so the program never sees the shuffle. That order is also what makes a wrong guess (Chapter 3) or a fault (Chapter 7) clean to undo: everything after the bad point has not been made official yet, so it is simply thrown away.

Names that collide

Our loop writes t0 for every number. Taken literally, the next number's load into t0 would have to wait until this number's add had finished reading t0, although the two have nothing to do with each other. It is like two dishes told to share one bowl: the second waits only because the bowl is busy. A wait caused only by reusing a register's name, not by needing its value, is a false dependency.

So the core hands out a fresh bowl for every dish. It gives every new result its own hidden register, so reused names stop colliding: register renaming. Each number's t0 is a different box inside the core, and the next number's load can start at once. Renaming removes waits over names. It cannot remove a wait for a value.

The chain ceiling

Take a run of instructions where each needs the answer of the one before: a dependency chain, like a relay where each runner waits for the baton. If each step takes L ticks from its start to its answer, step k + 1 cannot start before step k's answer exists. So the starts are at least L apart, and n steps take at least n × L ticks, however big the window: at most one step every L ticks.

ticks

The time for the whole chain, from the first start to the last answer.

n

The number of steps in the chain.

L

The ticks from the start of one step to its answer; for a load, the delay of the level where the data lives.

Look at what is missing from that sum: the window. A bigger window cannot beat it. Independent steps have no such limit: they are held back only by how many can be in flight at once and how fast new ones can start. If one may start every tick and the window is big enough, n independent loads finish about (n − 1) + L ticks after the first one starts.

How far away memory is

Memory is not one place. Think of a cook's ingredients: a few on the shelf at her elbow, more in the cupboard across the room, more in the storeroom down the hall, and everything else in a warehouse across town. The core keeps copies of recently used memory on small, fast stores close to it: caches. The nearest and smallest is L1, the shelf at your elbow; then L2 and L3, each bigger and slower, the cupboard and the storeroom.

Some chips add a system-level cache shared by everything on the chip. Behind them all sits the computer's main memory, far bigger and far slower than any cache: the DRAM, the warehouse across town.

Here is the measured ladder of one big Arm core, which ticks at about 4.0 GHz (its L3's 56 ticks are 14 ns), so one tick is a quarter of a nanosecond:

From the elbow shelf to the warehouse is 113 times as far.

Pointer chasing

Now a treasure hunt, where each note says where the next note is hidden. A pointer is a number that is an address: a note saying where the next note is. A linked list is a chain of records where each holds the address of the next; each record is a node. To reach node k + 1 you must first load node k, because node k holds its address. Walking a list, one load per node, is pointer chasing: a dependency chain made of loads.

So each step pays the full wait of wherever the nodes live. A million nodes of 64 bytes take 64 MB, bigger than the 16 MB system-level cache of the measured chip, so they live in main memory: 1,000,000 × 113 ns = 113 ms for one walk. Watch the chain against the same loads made independent:

The array walk

Store the same records side by side in memory, as an array, and every address is known in advance: the next is simply 4 bytes, or 64, further on. The loads no longer depend on each other, so the core can send many to memory at once and wait for all of them together, like a cook with several orders out at the warehouse at once. Many loads waiting on memory at the same time is memory-level parallelism (the next lesson, on caches, takes it apart).

In the device above, with its toy window of 16, 16 loads from main memory take 467 ticks as independent loads and 7,232 as a chain: 15.5 times apart. The window matters only for the independent loads. For the chain it changes nothing, whatever you set it to.

What this lesson does not claim matters too. How much faster a real array walk is depends on the chip's limit on loads in flight, which this lesson does not measure; the chain's cost is the solid number: one full trip per node. Here is the device's rule as Python, and its real output:

python# window.py: 16 loads, each L ticks from start to
# data; a chain versus independent loads (the
# device's rule)
def chain(n, L):
    # each load starts when the previous one's
    # data arrives
    return n * L

def independent(n, L, W):
    done = []  # the tick each load's data arrives
    for i in range(n):
        # at most one new load starts per tick
        start = i
        # at most W loads may wait at once
        if len(done) >= W:
            start = max(start, sorted(done)[-W])
        done.append(start + L)
    return max(done)

for name, L in [("L1", 4), ("L2", 12), ("L3", 56),
                ("main memory", 452)]:
    c = chain(16, L)
    print(f"{name:12s} chain {c:5d} ticks | "
          f"window 4: {independent(16, L, 4):5d} | "
          f"window 16: {independent(16, L, 16):4d}")

outputL1           chain    64 ticks | window 4:    19 | window 16:   19
L2           chain   192 ticks | window 4:    51 | window 16:   27
L3           chain   896 ticks | window 4:   227 | window 16:   71
main memory  chain  7232 ticks | window 4:  1811 | window 16:  467

And here is the classic measurement to run on your own machine. It builds a million nodes, links them in a shuffled order, walks them once as a chain and once as an array, and prints the time per node for each. The page claims no result for it: run it and compare the two numbers it prints.

c/* chase.c: walk the same nodes as a chain (each load
   needs the last) and as an array (each address known
   ahead) */
#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
    struct node *next; long value; char pad[48];
} node;   /* 64 bytes: one cache line, the
             memory-transfer unit Chapter 5 explains */

static double now(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

int main(void) {
    const long n = 1 << 20;         /* 1,048,576 nodes: 64 MB */
    node *pool = malloc(n * sizeof *pool);
    long *order = malloc(n * sizeof *order);
    for (long i = 0; i < n; i++) order[i] = i;
    for (long i = n - 1; i > 0; i--) {
        long j = rand() % (i + 1);
        long t = order[i]; order[i] = order[j]; order[j] = t;
    }
    for (long i = 0; i < n; i++) {
        pool[order[i]].next = &pool[order[(i + 1) % n]];
        pool[i].value = i;
    }

    double t0 = now();
    long sum = 0;
    node *p = &pool[order[0]];
    for (long i = 0; i < n; i++) {   /* the chain: the
                                        next address comes
                                        from this load */
        sum += p->value; p = p->next;
    }
    double t1 = now();
    for (long i = 0; i < n; i++) sum += pool[i].value;
    /* the array: every address is known in advance */
    double t2 = now();

    printf("chain %.1f ns a node, array %.1f ns a node (sum %ld)\n",
           (t1 - t0) / n * 1e9, (t2 - t1) / n * 1e9, sum);
    free(pool); free(order);
    return 0;
}

Build it with cc -O2 chase.c -o chase. The shuffle scatters the chain across all 64 MB, so almost every step misses every cache; rand() is good enough to scatter it.

worked exampleOne big Arm core's memory ladder, measured (4.0 GHz: 56 ticks = 14 ns,
  so a tick is 0.25 ns)
  L1 hit              4 ticks =   1 ns      1 times
  L2                 12 ticks =   3 ns      3 times
  L3                 56 ticks =  14 ns     14 times
  system cache  168 to 188    = 42 to 47 ns   42 to 47 times
  main memory       452 ticks = 113 ns    113 times

A chain of loads (a linked list) pays the full wait at every step
  1,000,000 nodes × 64 bytes = 64 MB, more than the 16 MB system
    cache: they live in main memory
  one walk: 1,000,000 × 113 ns = 113 ms
  if every node sat in L2: 1,000,000 × 3 ns = 3 ms
  a camera at 30 frames a second (illustrative) gives 33.3 ms a
    frame: 113 ÷ 33.3 = 3.4 frames

The toy window: 16 loads from main memory (452 ticks each), one
  may start per tick
  chain:                    16 × 452           = 7,232 ticks, 452 a load
  independent, window 4:    four rounds of 452   = 1,811 ticks,
    113 a load: 4.0 times sooner
  independent, window 16:   the last starts at tick 15 and lands
    at 15 + 452 = 467 ticks: 15.5 times sooner

The map that was three frames late

What happens. A robot's planner keeps the obstacles it has seen in a linked list, adding each new one wherever memory is free. A sweep over a million obstacles was estimated from the instruction count at a few milliseconds. It takes 113 ms, and the plan arrives more than three camera frames late.

What you measure. Time the sweep and divide by the number of nodes: about 113 ns a node, one full trip to main memory each. The count of instructions per tick (perf stat, Chapter 3) is tiny: the core spends almost every tick waiting on one load whose address came from the load before.

What you change. Store the obstacles in an array, or in a few large blocks, so the next address is known without a load. Keep the part the planner reads every sweep small enough to live in a cache. Then time it again.

Wider and wider

Big cores keep widening: the measured Arm core fetches ten instructions a tick and keeps two thousand jumps in its fastest target table. A wider front end and a bigger window help every independent piece of work. None of it moves the chain ceiling: a chain still runs at the speed of its links, which is why the fastest code on a big core is code that gives it independent work to do.

A graphics processor, a GPU, meets slow memory in another way. The lesson on GPUs shows what the rate at which memory delivers bytes, rather than its delay, does there.

You have 1,024 envelopes to mark with the same return address. With a pen you write 1,024 times. With a rubber stamp as wide as four envelopes laid side by side, you press 256 times. A robot's vision code is full of work like this: the same small step on every pixel of every frame. This chapter is about how wide a stamp a processor can have, and what a wider stamp does, and does not do, for the whole job.

One instruction, many numbers

The processor's rubber stamp is a single instruction that does the same thing to several numbers at once: SIMD, short for single instruction, multiple data. It works on a wide register that holds several numbers side by side, like an egg carton holds eggs: a vector register. Each position in it, each egg cup, is a lane.

Arm's SIMD, whose registers are always 128 bits, is called Neon. It has 32 vector registers of exactly 128 bits, four 32-bit numbers each. So one Neon instruction can multiply four numbers by 3 at once, and scaling 1,024 numbers takes 256 vector instructions instead of 1,024.

A stamp of any width

Arm's newer Scalable Vector Extension, SVE, lets each chip's maker pick the register size: anywhere from 128 to 2048 bits, in steps of 128, which is 16 possible sizes. Its 32 registers keep Neon's 128 bits as their lowest part.

But a wider choice raises a problem. A program written for exactly four lanes cannot use sixteen, and a program written for sixteen breaks on a chip with four. So SVE code is written the other way round: it asks the hardware how many lanes it has and steps through the data by that many, like a stamp that works whatever its width. Code written that way is vector-length agnostic, and the same program file runs on every size: 1,024 numbers take 256 passes at 128 bits, 128 at 256, 64 at 512 and 16 at 2048. Here is the idea as a Python sketch, with its real output:

python# vla.py: one loop, any vector length (a sketch of
# how vector-length-agnostic code steps)
import numpy as np
def scale(xs, k, vl_bits):
    # how many 32-bit numbers one vector register holds
    lanes = vl_bits // 32
    out, passes = np.empty_like(xs), 0
    # step by however many lanes this chip has
    for i in range(0, len(xs), lanes):
        # one vector instruction's worth of work
        out[i:i + lanes] = xs[i:i + lanes] * k
        passes += 1
    return out, passes
xs = np.arange(1024, dtype=np.int32)
for vl in (128, 256, 512, 2048):
    out, p = scale(xs, 3, vl)
    print(f"{vl:5d} bits: {vl // 32:3d} lanes, {p:4d} passes, "
          f"same answer: {bool((out == xs * 3).all())}")

output  128 bits:   4 lanes,  256 passes, same answer: True
  256 bits:   8 lanes,  128 passes, same answer: True
  512 bits:  16 lanes,   64 passes, same answer: True
 2048 bits:  64 lanes,   16 passes, same answer: True

RISC-V's stamp

RISC-V has a stamp too. Its vector extension, an optional part of the instruction set like Chapter 2's C extension, is called V. Because so many parts are optional, RISC-V names bundles of them: a list of extensions a chip must have to carry a given name is a profile. RISC-V's RVA23 profile, for the big application processors that run general-purpose software, makes V mandatory (in its user-level part, RVA23U64), where the older RVA22 left it optional.

Lined-up data

Now a practical snag. Eggs only come in boxes of one fixed size, and memory is the same: it travels between the caches and the core in blocks of 64 bytes, called cache lines. A buffer, a block of memory set aside for data such as one camera frame, that starts at an address that is a multiple of its block size is aligned, like a carton lined up with the edge of the box.

A 16-byte Neon load from an aligned buffer always sits inside one line: its four loads per line start at bytes 0, 16, 32 and 48. Start the same buffer 4 bytes late and the loads sit at bytes 4, 20, 36 and 52 of each line: the one at 52 covers bytes 52 to 67 and crosses into the next line. One load in four now touches two lines. With 32-byte loads it is one in two; with 64-byte loads, every single one; a 256-byte load touches five lines instead of four.

What a straddling load costs depends on the chip: from almost nothing on some big cores to 12 to 16 ticks on older or small ones. One careful measurer found about 12 ticks per straddling read on Intel's Core 2, hardly any on Nehalem, and 16 on the first Atom. Step through it:

The part you did not speed up

A trip is a long flight and a slow taxi ride. Make the flight twice as fast and the whole trip is not twice as fast: the taxi takes as long as ever. A program is the same. Vectorizing speeds up the loops you vectorize, and nothing else.

Derive it. Call the program's old running time 1. A share f of it is the part you speed up; the rest, 1 − f, you leave alone. Make the part s times faster: it now takes f ÷ s, while the rest still takes 1 − f.

The new time is (1 − f) + f ÷ s, and the speedup is the old time over the new. The speedup of the whole is held back by the part you did not speed up: Amdahl's law.

S

How many times faster the whole program becomes.

f

The share of the original time spent in the part you speed up.

s

How many times faster that part becomes (for SIMD, at most the number of lanes).

1 − f

The part you left alone: it takes as long as ever.

f = 0.9, s = 4: 1 ÷ (0.1 + 0.225) = 3.08 · the ceiling as s grows: 1 ÷ 0.1 = 10

Put numbers in. With 90% of the time vectorized at four times, the new time is 0.1 + 0.9 ÷ 4 = 0.325, and the whole runs 3.08 times faster. At sixteen times, 6.40. Now let s grow without limit: f ÷ s shrinks to nothing, and the speedup approaches 1 ÷ (1 − f). With an infinitely wide stamp, a program that is 90% vectorized is never more than 10 times faster, and one that is half vectorized can never pass 2.

The compiler vectorizes too

You rarely write vector instructions by hand. The settings you hand a compiler, called flags, include how hard to optimize: -O2, -O3. At high optimization, compilers rewrite simple loops to use SIMD by themselves, vectorizing them. The 2012 answer reports that Clang, and gcc from version 5 at -O3, vectorize Chapter 0's loop, and then there is no per-number fork left at all. That is why the build in Chapter 2 was made with -fno-tree-vectorize: to keep the loop simple enough to read.

worked exampleLanes and passes for 1,024 numbers of 32 bits
  128 bits ÷ 32 = 4 lanes    → 1,024 ÷ 4  = 256 passes
    (Neon, and the smallest SVE)
  256 bits      = 8 lanes    → 1,024 ÷ 8  = 128 passes
  512 bits      = 16 lanes   → 1,024 ÷ 16 =  64 passes
  2048 bits     = 64 lanes   → 1,024 ÷ 64 =  16 passes
  legal SVE sizes: 128 to 2048 in steps of 128: 2048 ÷ 128 = 16 sizes

Loads that straddle a 64-byte line when the buffer starts 4 bytes late
  16-byte loads start at 4, 20, 36, 52: the one at 52 covers 52 to 67
    and crosses 64: 1 in 4
  32-byte loads start at 4, 36: the one at 36 crosses: 1 in 2
  64-byte loads: every one crosses; a 256-byte load touches 5 lines
    instead of 4
  cost of a straddling load: about 12 ticks (Core 2), hardly any
    (Nehalem), 16 (first Atom)

Amdahl: S = 1 ÷ ((1 − f) + f ÷ s)
  f = 0.9,  s = 4:  1 ÷ (0.1 + 0.225)   = 1 ÷ 0.325 = 3.08
  f = 0.9,  s = 16: 1 ÷ (0.1 + 0.05625) = 6.40
  f = 0.9,  s → ∞:  1 ÷ 0.1             = 10
  f = 0.95, s = 8:  1 ÷ (0.05 + 0.11875) = 5.93
  f = 0.5,  s → ∞:  1 ÷ 0.5             = 2

Same filter, slower on some frames

What happens. A vectorized filter runs at one speed on most camera frames and noticeably slower on others, with the same size and the same kind of data. The slow frames come from one part of the program.

What you measure. Print where each frame's buffer starts within its cache line: (uintptr_t)p % 64, the address divided by 64, keeping the remainder. The fast buffers start at 0; the slow ones at 4, because that part of the program hands over a pointer 4 bytes into a larger block. The chip's own counters for loads that cross a line say the same thing (their names differ from chip to chip). Here is the check as a whole program, with its real output:

c/* align.c: where does a buffer start, relative to a
   64-byte cache line? */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    /* C11: start on a 64-byte boundary; the size
       must be a multiple of 64 */
    char *block = aligned_alloc(64, 8192);
    int *good = (int *)block;       /* starts at the start of a line */
    int *late = (int *)(block + 4); /* the same memory, 4 bytes later */
    printf("good starts %lu bytes into a line, late %lu\n",
           (unsigned long)((uintptr_t)good % 64),
           (unsigned long)((uintptr_t)late % 64));
    free(block);
    return 0;
}

outputgood starts 0 bytes into a line, late 4

What you change. Allocate frame buffers aligned to 64 bytes (C11's aligned_alloc(64, size), with size a multiple of 64), and keep each image row a multiple of the vector's width, so no load straddles two lines. Then time both kinds of frame again.

Wider and narrower at once

Arm's 2025 update to the architecture, Armv9.7-A, adds SVE instructions, and instructions for its matrix extension, SME, that work on MXFP6, a 6-bit number format for AI from the Open Compute Project. Wider and narrower at once: more numbers per instruction, fewer bits per number. A GPU takes the same idea to thousands of lanes; the lesson on GPUs shows how.

Your robot's computer runs a camera program that must finish every frame on time, and a mapping job that can take as long as it likes. The system monitor lists 16 processors. You put the mapping job on processor 8, far from the camera on processor 0, and the camera starts missing frames. Processors 0 and 8 turn out to be two halves of the same core. (The numbering in this story is illustrative; every machine lists its own.)

Who decides where things run

Two foundations first. Every building has a management that decides who works where. A computer's management is the software that runs all other software (Linux, Android and Windows are examples): the operating system. Its heart, the part with the most power over the machine, is the kernel.

One of the kernel's jobs is deciding which program runs on which core, and when, like a manager handing out desks: the part that does it is the scheduler. A program can have several lines of work, like several workers' to-do lists, that the scheduler places on cores separately: each is a thread. Put two threads on two cores and they truly run at the same time; put them on one core and they must share it.

Idle slots in a big core

A big core can start several instructions every tick (Chapter 3's big Arm core fetches ten). One thread rarely keeps it that busy. It waits on memory (Chapter 4), and it throws work away after wrong guesses (Chapter 3). During those waits, most of the core's machinery sits idle: arithmetic units with nothing to add, slots in the window with nothing ready.

Two threads, one core

Picture two cooks sharing one stove, each using the burners the other has left free. Some cores do exactly this. They keep the registers of two threads at once, the registers that say where each thread is up to, and fill one thread's idle slots with the other's work: simultaneous multithreading, or SMT. Intel calls it Hyper-Threading.

To the operating system each half looks like a whole processor, a logical processor, and two that share one core are siblings. That is why the system monitor in the opening listed 16 processors on a chip of 8 cores. And it is cheap to build: the first version cost under 5% of the chip's area.

What sharing buys

Intel's own measurement, on the big computers that run data centres: up to 30% more work per second on common server benchmarks, and 16 to 28% on three named server workloads. Not double. The two threads share one set of arithmetic units, one set of caches and one set of guessers.

A toy bound shows why it can never be double for a busy thread (illustrative numbers). If one thread alone keeps the core busy a share u of the time, a second can at best fill the rest, so two threads together are at most min(2, 1 ÷ u) times one. For a thread that keeps the core busy 77% of the time, 1 ÷ 0.77 = 1.3.

And some programs run slower on siblings than on separate cores, because two threads that both need the caches push each other's data out. No number is given here for that: you measure your own.

Two jobs, three placements

Take two jobs, each needing 10 seconds of a core to itself (illustrative). On two separate cores, both finish at 10 s. On one core's two siblings with sharing worth 30%, the core does 1.3 jobs' worth of work per second, shared between them, so the 20 seconds of work take 20 ÷ 1.3 = 15.4 s: both finish 1.54 times later than on separate cores. At 16%, 17.2 s. On one core with no sharing, taking turns, 20 s.

Big cores and little cores

Picture a garage with a sports car and a scooter: one fast and thirsty, one slow and frugal. Some chips mix fast, power-hungry cores with slow, frugal ones on the same chip: Arm calls this big.LITTLE. Now the scheduler must know how much work each core can do at its top speed, its capacity. The kernel's own definition multiplies two things (a hertz is one tick a second):

capacity

How much work a core can do at its top speed; the scheduler's number for each core.

work per hertz

How much a core gets done in each tick (a big core does more per tick than a little one).

top frequency

Its fastest clock, in ticks a second.

a little core at 40% of a big core's capacity (illustrative): 10 s of big-core work takes 10 ÷ 0.4 = 25 s

On such mixed chips, Linux can also predict how much energy each placement will cost and choose the cheapest that still gets the work done: Energy Aware Scheduling (EAS). It works only on mixed chips, and it needs a table of each core's power costs, the Energy Model; without one it does not start. NVIDIA's GB10 pairs ten Cortex-X925 cores with ten Cortex-A725 cores on one chip. The Jetson AGX Thor robot computer has 14 cores of one kind, Neoverse-V3AE; if they all run at the same top speed, the energy-aware mode has no mix to choose between. Place two threads yourself:

Reading the map, then pinning

So which processors are siblings? The kernel shows the hardware as a tree of small files under /sys, called sysfs, and one of them names the siblings of each processor. Linux numbers the logical processors cpu0, cpu1 and so on (CPU is short for central processing unit, another name for a processor):

shell# the logical processors in the same core as CPU 0
# (also exposed under its older, deprecated name
# thread_siblings_list)
cat /sys/devices/system/cpu/cpu0/topology/core_cpus_list
0,8

The 0,8 is an illustrative output: read your own.

Read it: cat prints a file, and core_cpus_list lists the logical processors in the same core as CPU 0. Here it says 0,8, so 0 and 8 are siblings. The same file is still exposed under its older name, thread_siblings_list, which the kernel marks deprecated.

Now you can place threads on purpose, like assigning someone a desk. The list of cores a thread may run on is its affinity; setting it by hand is pinning. The command taskset -c runs a program pinned to a list of processors, and taskset -p changes the affinity of one that is already running. The & lets the camera keep running while you type the next line, and time prints how long a program took:

shelltaskset -c 0 ./camera &            # the camera on processor 0
# the mapper on its sibling: they share one core
time taskset -c 8 ./mapper
# the mapper on a core of its own
time taskset -c 1 ./mapper
# move an already running program, number 4242, to
# processor 2
taskset -p -c 2 4242

worked exampleTwo jobs of 10 s each (illustrative), placed three ways
  two separate cores:              both finish at 10 s
  one core's two siblings, +30%:   20 s of work ÷ 1.3 per second
    = 15.4 s   (1.54 times later)
                           +28%:   20 ÷ 1.28 = 15.6 s
                           +16%:   20 ÷ 1.16 = 17.2 s
  one core, taking turns:          20 s
The toy bound (illustrative): busy 77% of the time alone → at most
  1 ÷ 0.77 = 1.30 times with a sibling
Capacity
  capacity = work per hertz × top frequency
  a little core at 40% of a big core's capacity (illustrative):
    10 s ÷ 0.4 = 25 s
Robot computers
  Jetson AGX Thor: 14 Neoverse-V3AE cores; 128 GB of 256-bit
    LPDDR5X at 273 GB/s (273 GB/s over 256 bits implies 8,533
    million transfers a second, LPDDR5X-8533: 256 bits × 8,533 ÷ 8
    = 273.1 GB/s; NVIDIA publishes only the bandwidth)
  NVIDIA GB10: 10 Cortex-X925 + 10 Cortex-A725 cores

Sixteen processors, eight cores

What happens. The camera thread misses frames whenever the mapping job runs on processor 8, and never when it runs on processor 1. The team had counted 16 processors and assumed 16 cores.

What you measure. Read /sys/devices/system/cpu/cpu0/topology/core_cpus_list: it prints 0,8, so processors 0 and 8 are siblings in one core. Pin the mapper to 8 with taskset -c 8, then to 1, and time the camera's frames in both: on the sibling, the camera shares its core's machinery with the mapper; on processor 1 it has a core of its own.

What you change. Keep the camera's sibling free, or pin every batch job to cores that share nothing with the camera. The sharing that gives a batch job up to 30% more throughput can cost a deadline thread its frame.

Robot computers now

Robot computers are now as big as servers. Thor pairs its 14 cores with 128 GB of main memory, a kind of DRAM called LPDDR5X, that can deliver 273 gigabytes a second over a connection 256 bits wide. With that many cores, the question is rarely whether there is a free core; it is whether the thread that has a deadline shares its core with one that does not. The lesson on Real-Time Linux takes this one step further and clears a core of every other job: a core of its own.

Your robot's Linux starts up and loads the driver for its camera, the part of the kernel that talks to the camera. The moment the driver reads the camera interface's first setting, the whole machine stops with an error. The driver's code is correct, and the same camera works on another board. The kernel is the most powerful software on the robot, isn't it? Something on this chip just refused it.

The kernel is powerful, but it is not in charge of the whole chip. This chapter climbs the chip's ladder of who may do what, and ends by reading the error that stopped the robot.

Why a chip needs levels

A robot runs code you trust, the kernel, and code you trust less: apps (the ordinary programs), plug-ins, a program downloaded last week. The chip must stop an app from driving the motors directly or reading another app's memory, even if the app is badly written or hostile. Asking nicely is not enough; the hardware itself has to say no.

Think of an office building where your keycard opens the lobby and your own floor, the office floors belong to the management, and the vault has a guard of its own. The chip works the same way. It enforces modes that decide which instructions and which memory a piece of code may use: privilege levels, the floors a keycard opens.

Arm's four levels

Arm calls its four levels exception levels, EL0 to EL3, running from least to most powerful: EL0 is the lobby, EL1 the office floors, EL2 building management, and EL3, the most powerful of all, the vault. The common arrangement puts apps at EL0 and the kernel, Linux, at EL1.

At EL2 sits a hypervisor, the building management: software that runs several operating systems side by side on one chip, each believing it has the machine to itself. At EL3 sits firmware, software built into the board below the operating system, like the building's own wiring, acting as the secure monitor: the vault's guard, and what it guards comes in a moment. The architecture does not force this assignment; it is the usual one. So the operating system is on the second rung of four.

Crossing up: exceptions

Code at one level cannot simply call code at a higher one, any more than a visitor can walk into the management offices. It rings the front desk. In the chip, that is an instruction that makes the processor stop what it is doing and jump to a handler, the code that deals with the request, at a higher level: an exception, also called a trap.

To do that, the processor abandons the instructions in flight behind the one that trapped, exactly as it abandons the work down a wrongly guessed road (Chapter 3), and starts fetching at the handler, now at the higher level. The same machinery that throws away a wrong guess is what lets the chip change who is in charge.

There are three such calls, one per rung. An app asks the kernel for something with SVC: that is a system call, the program's question at the front desk. The kernel asks the hypervisor with HVC. The kernel asks the secure firmware with SMC, the secure monitor call.

And there is no skipping rungs. From EL0 an app cannot call EL2 or EL3 directly. In Arm's own words, "the application at EL0 must use an SVC call to the kernel", and the kernel calls further up on its behalf.

The chip also writes down a code for the kind of exception, its exception class; the end of this chapter reads these codes.

Two worlds

Now picture two buildings on one foundation. Arm's TrustZone splits the chip into two worlds: the Non-secure world (also called normal), where Linux and your apps live, and the Secure world (also called trusted). At EL0, EL1 and EL2 the processor can be in either world, chosen by one bit in a control register at EL3 (its name is SCR_EL3.NS); EL3 itself is always Secure.

The Secure world's EL0 and EL1 hold a small, separate operating system that looks after secrets such as keys, like the vault's own staff: a trusted execution environment, or TEE.

Who runs where, on a real board

Here is who plays each part in one common open-source setup, open-source meaning free for anyone to read and change. One open-source secure monitor is Trusted Firmware-A, whose runtime part, BL31, runs at EL3. BL31 hands a call meant for the trusted OS to a plug-in inside itself, a dispatcher, which switches the chip into the trusted OS at Secure EL1 and carries its answer back: the vault guard buzzing the vault's own staff and relaying their reply.

OP-TEE is an open-source trusted OS designed to sit beside Linux on Arm chips, and it runs at Secure EL1. When Linux executes SMC, the monitor always catches it first and, if the call is for OP-TEE, switches the chip to it. The kernel never talks to the Secure world directly; it rings the vault's guard.

Who owns memory and devices

A block on the chip that does one job, like a room with one purpose, is a peripheral: a timer, a serial port, the camera interface. Every access to one travels over the chip's internal road network, like the corridors of the building: the interconnect, which carries every access between cores, memory and peripherals.

Most peripherals do not know about worlds at all: each is simply Secure or Non-secure. On most modern chips the interconnect checks each access, and when Non-secure code touches a Secure-only device, it answers with a fault, without the access ever reaching the device. Some devices are set Secure or Non-secure at start-up, when the computer boots, by the boot firmware, and until then they are Secure.

Memory is split the same way, by a gatekeeper that divides it into regions, each Secure or Non-secure, like a locked storeroom: a TrustZone Address Space Controller, such as Arm's TZC-400, which supports up to nine regions and whose own settings only Secure code may change. Trusted Firmware-A sets it to raise an error when a Non-secure access reaches into Secure memory; on Arm's own development platforms, as Trusted Firmware-A's design describes, the top 16 MB of main memory is kept Secure. Climb the ladder yourself:

The same ladder on RISC-V

RISC-V has a ladder too. It names its levels user, supervisor and machine; machine is the most powerful and the only one every RISC-V chip must have. Its hypervisor extension, H, turns supervisor mode into a hypervisor mode and adds a virtual supervisor mode for guest operating systems. RISC-V's RVA23 profile, announced as ratified in October 2024, makes H mandatory in its supervisor-level profile (RVA23S64), the one an operating-system kernel relies on.

Decoding the fault

When an exception comes to the kernel, the chip writes down why, like the first box on an incident report, into a register: the exception syndrome register, ESR_EL1. It is a 64-bit register, but everything this lesson reads sits in its lower 32 bits: Linux prints the whole value as sixteen hexadecimal digits, and the upper eight are zero here. The top six of those 32 bits, bits 31 to 26, are the exception class: which kind of exception it was. Here are the classes this lesson reads, with the names Linux's own source code gives them:

To read the class, shift the value right by 26 places and keep six bits. Shifting right by 26 moves bits 31 to 26 down to positions 5 to 0 and drops everything below them; on the full 64-bit register it also brings down the bits above 31, always zero here. Then & 0x3F keeps exactly those six bits and drops the rest, because 0x3F is 111111 in binary:

AArch64 is Arm's name for its 64-bit instruction set; the classes above that trap a 64-bit-only operation carry it in their name.

class

The exception class: which kind of exception it was.

ESR

The exception syndrome register's low 32 bits (the part that carries the class; the upper bits are usually zero).

>> 26

Shift right by 26 places: bits 31 to 26 move down to the bottom.

& 0x3F

Keep only the lowest six bits (0x3F is 111111 in binary).

0x96000010 → 100101 = 0x25: DABT (current EL)

Work one through. Take the value 0x96000010 (an illustrative value from a crash report). In bits it is 1001 0110 0000 0000 0000 0000 0001 0000; bits 31 to 26, the top six of its low 32 bits, are 100101, which is 0x25, or 37. Look 0x25 up: DABT (current EL).

DABT stands for a data abort, a data access that the chip refused or that failed, like a keycard reader flashing red. "Current EL" means it was taken at the kernel's own level: the kernel itself made the access. The kernel's name for a system error the chip reports is SError, class 0x2F; a Secure-only device can show up as either.

Here are the kernel's own definitions, and the same decode in Python with its real output:

c#define ESR_ELx_EC_SHIFT   (26)
#define ESR_ELx_EC_MASK    (UL(0x3F) << ESR_ELx_EC_SHIFT)
#define ESR_ELx_EC_SVC64   UL(0x15)
#define ESR_ELx_EC_DABT_CUR UL(0x25)
#define ESR_ELx_EC_SERROR  UL(0x2F)

python# esr.py: which kind of exception was it? (class names
# from Linux arm64 esr.h and traps.c)
NAMES = {
    0x00: "unknown", 0x15: "SVC (AArch64)",
    0x16: "HVC (AArch64)", 0x17: "SMC (AArch64)",
    0x18: "MSR/MRS (AArch64)", 0x24: "DABT (lower EL)",
    0x25: "DABT (current EL)", 0x2F: "SError",
}

def exception_class(esr):
    # bits 31 to 26 of the syndrome
    return (esr >> 26) & 0x3F

# an illustrative value from a crash report
esr = 0x96000010
ec = exception_class(esr)
print(f"{esr:#010x} -> bits {esr:032b}")
print(f"class {ec:#04x} = {ec:06b}: "
      f"{NAMES.get(ec, 'not in this table')}")

output0x96000010 -> bits 10010110000000000000000000010000
class 0x25 = 100101: DABT (current EL)

worked exampleThe ladder (the common arrangement; the architecture does not
  force it)
  EL0 apps  --SVC-->  EL1 kernel  --HVC-->  EL2 hypervisor
  EL1 kernel  --SMC-->  EL3 secure monitor (Trusted Firmware-A, BL31)
    -->  Secure EL1 trusted OS (OP-TEE)

Exception classes the chip records (names from Linux's esr.h and
  traps.c)
  0x15 = 010101   SVC (AArch64): a system call
  0x16 = 010110   HVC (AArch64): a hypervisor call
  0x17 = 010111   SMC (AArch64): a secure monitor call
  0x18 = 011000   MSR/MRS (AArch64): a forbidden register access
  0x24 = 100100   DABT (lower EL): a data abort from a lower level
  0x25 = 100101   DABT (current EL): a data abort at the kernel's
    own level
  0x2F = 101111   SError

Decoding 0x96000010 (illustrative)
  in bits: 1001 0110 0000 0000 0000 0000 0001 0000
  bits 31 to 26, the top six of its low 32 bits: 100101 = 0x25 = 37
  (0x96000010 >> 26) & 0x3F = 0x25 → DABT (current EL): the kernel's
    own data access failed

Memory and devices
  TZC-400: up to 9 regions, each Secure or Non-secure, settings
    changeable only from the Secure world
  Arm's development platforms (Trusted Firmware-A's design): the
    top 16 MB of main memory Secure
  a device set at start-up: Secure until the boot firmware says
  otherwise

The camera the kernel could not touch

What happens. The robot's kernel boots, the camera driver reads the camera interface's first setting, and the machine stops with an abort. The same driver works on another board.

What you measure. Read the crash report's syndrome value and take bits 31 to 26, the top six of its low 32 bits: 0x25, a data abort at the kernel's own level (or the kernel reports an SError). The access never reached the camera: the interconnect refused it, because on this board the camera interface is a device the boot firmware sets up, and it was left Secure, the default.

What you change. Mark the camera interface Non-secure in the boot firmware's platform setup, where Trusted Firmware-A configures the board. Or, if the Secure world is meant to own the camera, for example to protect its images, stop touching it from Linux and ask the trusted OS for frames through an SMC.

More rungs above the kernel

Arm's newer chips can add two more security states, one of them for what Arm calls Realms, separate from both worlds, and RISC-V now requires the hypervisor extension in its operating-system profile. The ladder keeps growing rungs above the operating system. Where the secure monitor itself comes from, the chain of firmware that starts the chip, is the subject of a coming lesson on the boot chain.

A robot's logger writes a short line to a file thousands of times a second, and every write is a trip into the kernel. After a routine update that switched on the kernel's full set of security fixes, the logger uses noticeably more of the processor. Not one line of its code changed. Where did the time go, and how much more should you expect?

The short answer: a cost that triples only matters in proportion to how often you pay it. This chapter prices one trip, then turns the price into a prediction for the whole program.

One crossing, priced

A system call (Chapter 7) enters the kernel and comes back: up the ladder and down again. One careful measurement on two hosts with the same processor priced calls that ask the kernel for almost nothing, so that nearly all their cost is the crossing itself. getuid, which asks the kernel for the number of the user running the program, took 78 ns with the security fixes switched off and 239 ns with them on.

The plainest call in the same table, made through the general-purpose syscall function, took 76 and 233 ns: 3.07 times dearer. close, which closes a file, moved from 93 to 257 ns. Across the 15 machines measured, that plainest call ranged from 76 to 620 ns; in the measurer's words, the switches between a program and the kernel cost "a few hundred nanoseconds, on all hosts".

Why the fixes exist

Go back to Chapters 3 and 4. The processor works ahead on guesses and throws the work away when a guess was wrong. Thrown-away work was supposed to leave no trace. It turned out it can leave traces, like footprints in the snow: for example in which memory is now sitting in the caches, and a program can time its own loads to read those traces. Attacks that read secrets through the traces that thrown-away guessed work leaves behind are speculative execution exploits, and they could read memory across the boundary between a program and the kernel.

The fixes, like a second lock on the door, are called mitigations. They do extra work at the boundary, which is why every crossing got dearer. The kernel's mitigations= setting, given on its command line, the settings handed to the kernel as it starts, chooses how much of it to do. auto, the default, mitigates everything and leaves simultaneous multithreading on. off disables every optional mitigation, which, in the kernel's own words, "improves system performance, but it may also expose users to several CPU vulnerabilities".

Amdahl's law, run backwards

Chapter 5 sped a part up. Now a part slows down, and the same arithmetic answers it. Call the old running time 1, with a share f spent crossing into the kernel. Make each crossing r times dearer: the crossing part now takes f × r, while the rest still takes 1 − f. The new time is (1 − f) + f × r, which is the same as 1 + f × (r − 1).

T_new

The new running time, with the old one counted as 1.

f

The share of the old time spent in the part that changed, here crossing into the kernel.

r

How many times dearer that part became: 233 ÷ 76 = 3.07 on the measured pair of hosts.

1 − f

Everything else, unchanged.

f = 5%: 0.95 + 0.05 × 3.066 = 1.103, 10.3% slower

So a service that spends 5% of its time crossing, each crossing 3.07 times dearer (3.066 before rounding), runs 0.95 + 0.153 = 1.103 of its old time: 10.3% slower. Not 207% slower. The slowdown in percent is 100 × f × (r − 1), which is about 207 × f: small shares stay small.

It is Chapter 5's law with the arrow reversed. Speed a share f up s times and the whole is 1 ÷ ((1 − f) + f ÷ s) times faster; slow it down r times and the whole is (1 − f) + f × r times slower. Both say the same thing: the part you change counts only by its share.

S

How many times faster the whole becomes when a part is sped up.

f

The share of the old time in that part.

s

How many times faster that part became.

The whole-workload measurements agree

Red Hat measured whole workloads when these fixes first shipped. Workloads with many crossings between programs and the kernel (databases, heavily cached memory work, benchmarks that cross constantly) ran 8 to 19% slower; moderate ones 3 to 7%; work that mostly computes 2 to 5%; and systems that bypass the kernel entirely, under 1%. A later, cheaper software fix, retpoline, cut those to 4 to 8%, 2 to 5% and 1 to 2%.

Now run the formula backwards. A measured slowdown of s percent means a share f = s ÷ (100 × (r − 1)) of the time was spent crossing. At r = 3.07, 8 to 19% slower means 0.08 ÷ 2.07 = 3.9% to 0.19 ÷ 2.07 = 9.2% of the time spent crossing. The measured slowdowns are exactly what a few percent of crossings predicts. Drag the share yourself:

Budgets

Price your own crossings before they surprise you (the rates here are illustrative). A logger writing 10,000 lines a second at 233 ns a crossing spends 2.33 ms of every second crossing: 0.23% of a core, or 0.08% without the fixes. A network loop that crosses once per message, a packet, at 1,000,000 packets a second spends 23.3% of a core crossing, against 7.6% without them.

The cure is fewer crossings, not no fixes. Write many lines per call instead of one. Or let a program talk to the device directly, without crossing into the kernel for every message: kernel bypass, which Red Hat measured under 1%.

And notice that this is still Chapter 0's equation: time = instructions × ticks per instruction × length of a tick. The fixes add instructions and ticks inside the crossing, and nowhere else. That is why the share of time spent crossing is the whole story.

worked exampleOne crossing, measured on two hosts with the same Xeon Gold 6256
  processor (2021)
  raw system call: 76 ns with mitigations off, 233 ns with them:
    233 ÷ 76 = 3.07 times
  getuid: 78 → 239 ns (3.06 times)     close: 93 → 257 ns (2.76 times)
  across 15 machines: 76 to 620 ns for the raw call

Amdahl run backwards: new time = (1 − f) + f × r, with r = 233 ÷ 76
  = 3.066 (3.07 rounded)
  f = 2%:   0.98 + 0.02 × 3.066 = 1.041 → 4.1% slower
  f = 5%:   0.95 + 0.05 × 3.066 = 1.103 → 10.3% slower
  f = 10%:  0.90 + 0.10 × 3.066 = 1.207 → 20.7% slower
  f = 20%:  0.80 + 0.20 × 3.066 = 1.413 → 41.3% slower

Red Hat's measured 8 to 19%, run backwards
  f = 0.08 ÷ 2.07 = 3.9%   to   f = 0.19 ÷ 2.07 = 9.2% of the time
    spent crossing

Budgets (illustrative rates)
  10,000 crossings a second:    10,000 × 233 ns = 2.33 ms a second
    = 0.23% of a core   (at 76 ns: 0.08%)
  1,000,000 crossings a second: 1,000,000 × 233 ns = 233 ms a
    second = 23.3% of a core (at 76 ns: 7.6%)

Here is both directions of the law in a few lines of Python, with its real output:

python# amdahl.py: a share f of the time made s times
# faster, or r times slower
def speedup(f, s):  return 1 / ((1 - f) + f / s)
def slowdown(f, r): return (1 - f) + f * r

print(f"90% made 4 times faster: {speedup(0.9, 4):.2f} "
      f"times faster overall")
# two hosts, same Xeon Gold 6256, one with
# mitigations=off: a system call 3.07 times dearer
r = 233 / 76
for f in (0.02, 0.05, 0.10, 0.20):
    print(f"{f:4.0%} of the time crossing into the "
          f"kernel: {100 * (slowdown(f, r) - 1):4.1f}% slower")

output90% made 4 times faster: 3.08 times faster overall
  2% of the time crossing into the kernel:  4.1% slower
  5% of the time crossing into the kernel: 10.3% slower
 10% of the time crossing into the kernel: 20.7% slower
 20% of the time crossing into the kernel: 41.3% slower

Nothing changed but the kernel

What happens. After a kernel update, a service that makes many small system calls runs about a tenth slower. Its code, its data and its load are the same.

What you measure. On a test machine, time a million system calls that do almost nothing, once booted normally and once with mitigations=off on the kernel's command line (the program below). Call the kernel with syscall(SYS_getpid), not plain getpid(): some versions of glibc, the standard C library on Linux, remembered the answer and never crossed at all, and one measured 1 to 2 ns for it. Then find the share of time the service spends in system calls, and multiply: 1 + f × (r − 1). A service that crosses for 5% of its time and pays 3.07 times per crossing should run about 10% slower, and it does.

c/* crossing.c: what one trip into the kernel costs on
   this machine (Linux) */
#define _GNU_SOURCE
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <sys/syscall.h>

int main(void) {
    const long n = 1000000;
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (long i = 0; i < n; i++)
        /* a real trip into the kernel; the C
           library's getpid() may answer from a cache */
        syscall(SYS_getpid);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double ns = ((t1.tv_sec - t0.tv_sec) * 1e9
                 + (t1.tv_nsec - t0.tv_nsec)) / n;
    printf("%.0f ns per system call\n", ns);
    return 0;
}

Build with cc -O2 crossing.c -o crossing and run it twice, booted normally and booted with mitigations=off on a test machine; the ratio of the two numbers is your r.

What you change. Cut the crossings: batch small writes into large ones, or bypass the kernel for the busiest path. Switching the mitigations off buys the time back, but it reopens the holes; on a robot that talks to a network, that trade is rarely worth it.

A moving target

The fixes have kept changing since they first shipped, and newer processors take some of the work into the hardware. The measured numbers above are one pair of servers in 2021 and one vendor's measurements of whole workloads. Measure your own robot's computer with the program above, and trust that number over any in this chapter.

A processor is an assembly line that guesses. It ticks as fast as its slowest stage allows, keeps five or more instructions moving at once, hands answers across instead of waiting for them, and works ahead down every fork on a guess. When the guess is right the work is free; when it is wrong, about 20 ticks go in the bin on a big core, which is how the same loop ran 11.8 seconds on random numbers and 2.4 on sorted ones.

A big core also runs later work early, but never ahead of a chain; stamps many numbers at once, but only speeds the part it stamps; shares a core between two threads, but never doubles it. And it keeps a ladder of privilege where the kernel is the second rung of four, where the Secure world can refuse the kernel outright, and where every crossing between rungs has a price you can measure and a share of your time you can predict.

The checklist

1. Compare processors by your own loop's ticks per instruction, never by the clock alone: perf stat -e cycles,instructions ./your_loop (Chapters 0 and 3).
2. Budget from the disassembly of the exact build, with compiler, version and flags written down: objdump -d (Chapter 2).
3. Find loads whose result is used straight away, and let the compiler, or you, move independent work between them (Chapter 2).
4. Find forks on noisy data: branch-misses ÷ branches, times about 20 ticks each on a big core; 3% can cost close to a fifth of the time (Chapter 3).
5. Remove a fork you cannot predict: a conditional select (csel, cmov) or the branchless trick; sort only if sorting costs less than the misses (Chapter 3).
6. Never walk a linked list you could store as an array: each step pays the full wait of wherever its nodes live, up to 113 ns from main memory on the measured Arm core (Chapter 4).
7. Vectorize the hot loop, and predict the whole with Amdahl first: 90% made four times faster is 3.08 times overall (Chapter 5).
8. Align buffers to 64 bytes; a load that straddles two lines costs from almost nothing to 16 ticks, depending on the chip (Chapter 5).
9. Read core_cpus_list before placing a thread with a deadline; pin with taskset -c; siblings share one core, worth up to 30% more work, never double (Chapter 6).
10. Know which of your cores are big and which little; the energy-aware scheduler acts only on mixed chips with an Energy Model (Chapter 6).
11. When a boot or a driver dies with an abort, decode the class, (esr >> 26) & 0x3F; a 0x25 or an SError on a device access can mean the peripheral was left Secure (Chapter 7): check that device's setting in the boot firmware's platform setup before blaming the driver.
12. Price a system call on your own machine with syscall(SYS_getpid) in a loop, predict the whole with 1 + f × (r − 1), and cut crossings before you consider mitigations=off (Chapter 8).

The numbers

Two programs to run yourself

The first is Chapter 0's experiment, whole. It fills a list with 32,768 numbers from 0 to 255, times the loop, sorts the list, and times it again:

c/* sorted_vs_random.c: the 2012 loop, timed with and
   without sorting first */
#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static int cmp(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

static double run(const int *data, unsigned n) {
    struct timespec t0, t1;
    long long sum = 0;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    /* read the whole list 100,000 times */
    for (unsigned i = 0; i < 100000; ++i)
        for (unsigned c = 0; c < n; ++c)
            if (data[c] >= 128)                    /* the fork */
                sum += data[c];
    clock_gettime(CLOCK_MONOTONIC, &t1);
    /* print it so the compiler keeps the loop */
    printf("  sum %lld\n", sum);
    return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
}

int main(void) {
    const unsigned n = 32768;                      /* 32,768 numbers */
    int *data = malloc(n * sizeof *data);
    /* 0 to 255, like pixel brightnesses */
    for (unsigned c = 0; c < n; ++c) data[c] = rand() % 256;
    double t_random = run(data, n);
    /* sort BEFORE the timer starts */
    qsort(data, n, sizeof *data, cmp);
    double t_sorted = run(data, n);
    printf("random order %.2f s, sorted %.2f s, ratio %.2f\n",
           t_random, t_sorted, t_random / t_sorted);
    free(data);
    return 0;
}

Build it with cc -O2 sorted_vs_random.c -o svr, run it, then look before you believe the ratio: objdump -d the binary and find the loop. If there is no conditional jump around the add, your compiler removed the fork (Chapter 2), and both orders will take about the same time. gcc 14.2 at -O2 -fno-tree-vectorize kept the fork on RISC-V and removed it on Arm and x86-64; at -O3, Clang and gcc from version 5 vectorize the loop and there is no fork at all. Then run perf stat -e cycles,instructions,branches,branch-misses on it and watch branch-misses rise in random order.

The second reads the output of perf stat and says where the ticks went, the way Chapter 3 read perf's own example by hand:

python# why_slow.py: read `perf stat -e cycles,instructions,
# branches,branch-misses` output, say where the ticks went
import re, sys

def counts(text):
    """Pull the four counts out of perf stat's text
    output (commas and the :u tag are ignored)."""
    got = {}
    for line in text.splitlines():
        m = re.match(r"\s*([\d,]+)\s+([a-z-]+)(?::u)?\b", line)
        if m:
            got[m.group(2)] = int(m.group(1).replace(",", ""))
    return got

def report(c, penalty=20):
    # instructions finished per tick
    ipc = c["instructions"] / c["cycles"]
    # share of forks guessed wrong
    miss = c["branch-misses"] / c["branches"]
    # share of all ticks spent recovering
    lost = c["branch-misses"] * penalty / c["cycles"]
    print(f"instructions per tick (IPC): {ipc:.2f}   "
          f"ticks per instruction (CPI): {1/ipc:.2f}")
    print(f"forks guessed wrong: {100*miss:.2f}%   "
          f"per 1,000 instructions: "
          f"{1000*c['branch-misses']/c['instructions']:.2f}")
    print(f"at about {penalty} ticks per wrong guess: "
          f"{100*lost:.1f}% of all ticks were spent recovering")
    print(f"remove every wrong guess and the program could "
          f"run at most {1/(1-lost):.2f} times faster")

if __name__ == "__main__":
    penalty = int(sys.argv[1]) if len(sys.argv) > 1 else 20
    report(counts(sys.stdin.read()), penalty=penalty)

Its output on the perf manual's example from Chapter 3, with python3 why_slow.py < example.txt:

outputinstructions per tick (IPC): 1.36   ticks per instruction (CPI): 0.73
forks guessed wrong: 2.98%   per 1,000 instructions: 6.64
at about 20 ticks per wrong guess: 18.1% of all ticks were spent
  recovering
remove every wrong guess and the program could run at most 1.22
  times faster

Pass the penalty for your own chip from Chapter 3's table: python3 why_slow.py 15 < out.txt gives 13.6% and 1.16 times on the same example.

Sources and their setups

Where this lesson sits

• Before it, on the site now: Embedded Systems (registers, timers and interrupts on a small chip) and Embedded C.
• Beside it, on the site now: Embedded Real-Time Systems (a Cortex-M4 at the register level), C Programming II (pointers and linked lists, Chapter 4's chain), GPUs (Chapter 5's lanes taken to thousands), and Real-Time Linux (giving a thread a core of its own).
• Next in this track: Caches and Coherence (coming): the 64-byte line, many cores sharing it, and memory-level parallelism; then DRAM and Bandwidth, Virtual Memory and DMA, and the SoC and its Interconnect (all coming).
• Beside it in the Physical AI track: From the Vector Table to main (coming: what the processor does from reset), The Boot Chain (coming: where Trusted Firmware-A starts), and perf, ftrace and Flame Graphs (coming: perf beyond perf stat).

Go back to the numbers at the top of the page: switch between random and sorted, then take the if out. Every part of it now has a name. The purple guess is Chapter 3's predictor, and the red flash is its penalty, about 20 ticks of work in flight thrown away. The 2.5 ticks each number costs when the guess is right is Chapter 2's assembly line with Chapter 4's running ahead. The ticks themselves are Chapter 1's clock. Then open Present and explain the five-times gap to someone, or open Teach and draw where the ten seconds went.