Guidebook · Rust performance engineering

Rust Performance Engineering: From "It Feels Faster" to "I Can Prove It"

Status of this file: Complete. All 9 Parts (40 chapters), the 11 capstone projects, the teaching kit, the glossary, and the reading map are written. Every Part ends with its own verification notes (what was run, what was checked against sources, and what was not). Corrections to earlier chapters are marked where they were made, and listed in Chapter 40.

What this guidebook promises

By the end, you will be able to take a slow Rust program (a parser, an interpreter, a compiler pass, a matrix routine) and do four things with it:

1. Measure it honestly, so you know the number you see is real.
2. Find where the time goes, using the right tool for the question.
3. Explain why it is slow, down to cache lines, memory pages, pipelines, and cores.
4. Fix it, and prove the fix worked, and teach the whole thing to other people.

You will not just know the tools. You will know why each tool works, what it can see, and what it cannot see. That is the difference between running a profiler and understanding performance.

How to use this guidebook

Every major idea is taught in three layers.

• The model (the "what"). The theory. The parts, the rules, the costs, and the numbers. This is what lets you define an idea and explain it to someone else.
• Build it (the "how"). Real code you run. Small first, then break it, then fix it. This is what lets you implement the idea in more than one way.
• Why it is this way (the "why"). The mental model. Why the designers chose this, what they gave up, and what would make the idea wrong. This is what lets you improve an idea or invent a new one.

Each chapter ends with exercises. Please do them. Reading gives you the feeling of understanding. Exercises give you the real thing. Each Part ends with a mini project, and the whole guidebook ends with 10 capstone projects.

Every number in this guidebook comes from a real run, unless it says otherwise. When I could not check something, I say so.

What you need before you start

• You can read basic Rust: structs, vectors, loops, closures, Option, and Result.
• A Linux machine (x86-64 is the default in this guidebook). A cloud VM or WSL2 works for most chapters. Some tools (like perf hardware counters) work best on real hardware, and I will say when.
• Rust stable. Part I and Part III used rustc 1.75 for the standalone programs, and Parts II and IV to IX mostly rustc 1.91.1 (each Part says which). Newer versions should work, and a few numbers will change.
• Later Parts will also use perf, valgrind, and a few Rust tools. Each one is introduced where it is first needed, with its install command.

The machine behind the numbers in this guidebook: an Intel Xeon at 2.1 GHz (the nominal speed the machine reports; in Chapter 37 I measure the core actually running at about 3.2 to 3.3 GHz), 1 core, running in a cloud virtual machine. L1 data cache 48 KiB, L2 2 MiB (as reported by lscpu). Your machine will give different numbers. The shapes should match.

Study paths

• I have a weekend. Part I (Ch 1 to 4), Part III (Ch 8, 9, 11), and Part IV (Ch 14 to 16). You will be able to measure, and to find hot spots with a flamegraph.
• I want to give a talk. Part I, Part III, Part IV, and the "Teach it back" box at the end of every Part. Then the teaching kit near the end.
• I want to speed up my parser, VM, or compiler. Part I, Part III, Part V, then Part VII. Do the mini projects.
• I want to know it all. Read in order. Do every Core exercise and the Part mini projects. Then the capstones.

Table of contents

Part I. Measuring honestly

1. What does "fast" even mean?
2. Noise, clocks, and distributions
3. Designing the workload and keeping the work alive
4. Build a tiny benchmark harness

Part II. Benchmarking in practice with Criterion

5. Install Criterion and read your first report
6. Estimates, outliers, and "is this change real?"
7. Groups, inputs, throughput, and baselines

Part III. The machine: memory and the CPU

8. Memory is not a box. It is a ladder.
9. Cache lines, the write path, and locality
10. Pages, address translation, and the TLB
11. Data layout: AoS, SoA, and hot/cold splits
12. Access patterns and the prefetcher
13. Pipelines, dependency chains, and branch prediction

Part IV. Profiling: finding where the time goes

14. Choose the evidence before the tool
15. perf stat and perf record
16. Flamegraphs, from folded stacks to a picture
17. Samply and timeline profiling
18. Instrumentation without fooling yourself (hotpath-rs and friends)
19. Top-down analysis and the roofline model
20. Cachegrind and Callgrind

Part V. Memory and allocation

21. What an allocation really costs
22. Heap profiling with DHAT
23. Reuse, arenas, SmallVec, and interning
24. What the Rust compiler does to your loop: bounds checks, iterators, inlining, LTO

Part VI. Many cores, shared state, and wide instructions

25. Cache coherence and false sharing
26. Atomics, locks, and contention
27. NUMA and finding contention with perf c2c
28. SIMD and auto-vectorization
29. Threads and data parallelism

Part VII. Applying it: four real systems

30. Matrix multiplication, from naive to blocked
31. Parsers
32. Interpreters and VMs
33. Compiler data structures: ASTs, interning, and arenas

Part VIII. Inside the tools

34. Inside Criterion
35. Inside perf and the hardware counters
36. Inside Valgrind
37. The silicon contract: frequency, cores, and what "a cycle" means

Part IX. Production practice

38. Performance as a maintained contract
39. From profile to safe change
40. Contribute and teach

Capstone projects (11) · Teaching kit · Glossary · Reading map

Part I. Measuring honestly

After this Part, you will be able to say with a straight face: "I measured it, and here is why you can trust the number."

Most performance work fails before it starts. Not because people write slow code. Because they measure wrong, and then they "fix" things that were never broken. So we start here. No tricks to make code fast yet. Only how to know what is true.

Chapter 1. What does "fast" even mean?

In this chapter: You will learn what a performance question really is, why a fast-looking number can be completely fake, and the simple loop that every good performance fix follows.

You need first: Nothing.

The problem first

Here is how a lot of performance work goes.

You have a slow function. You read it. You spot something that "looks slow". You change it. You run the program. It feels faster. You commit the change and tell the team you made it faster.

But did you?

Maybe the program was faster only because the machine was less busy that minute. Maybe the part you changed was only 2% of the time, so you could never have made a real difference. Maybe the compiler already did the same trick for you. Maybe you made one case faster and another case slower and only tested the first.

You don't know. You feel. And feelings about performance are wrong a lot of the time, even for very good engineers.

So the first thing to learn is not how to make code fast. It is how to know.

The model (the "what")

A performance claim is an observation

Start with a plain idea. Every performance claim is secretly a sentence with five blanks:

"This code takes this long on this machine with this input under these conditions."

If any blank is missing, the claim is incomplete. "My parser is fast" fills in nothing. "My parser handles a 10 MB JSON file in 41 ms, on a 2.1 GHz Xeon, one core, file already in memory, release build" fills in all five. The second claim can be checked. The first can only be argued about.

Remember this: performance is not a property of the code alone. It is a property of the code, the data, and the machine, all together. Change any one, and the number changes.

Two different things people call "fast"

A few words you need, because people mix them up.

• Latency is how long one piece of work takes, from start to finish. "This request took 20 ms."
• Throughput is how much work gets done per unit of time. "This server handles 5,000 requests per second."

They are related, but they are not the same. Think of a road. Latency is how long one car takes to drive the road. Throughput is how many cars pass per hour. Widen the road to four lanes and the throughput goes up, but one car is not any faster. And a very fast car alone on the road has great latency and tiny throughput.

Why does this matter? Because the fix is different. If you need lower latency, you shorten the path. If you need higher throughput, you often add parallel lanes, or reduce wasted work per item. We will use both words all through this guidebook.

Two more words:

• Wall-clock time is the time you would measure with a stopwatch on the wall.
• CPU time is how long the CPU actually worked on your program. If your program waited for the disk, that waiting is wall time but not CPU time.

When you see a gap between the two, you have already learned something: the program is waiting for something, not computing.

Where speed-ups can and cannot come from

Say a program takes 100 seconds. A function inside it takes 80 of those seconds. You make that function 10 times faster. How fast is the whole program now?

Not 10 times faster. The 80 seconds become 8. The other 20 seconds did not change. So the total is 28 seconds. That is a speed-up of 100 / 28, about 3.6 times.

This is called Amdahl's law. In symbols: if a fraction p of the time is sped up by a factor s, the whole program speeds up by

            1
speedup = ─────────────
          (1 − p) + p/s

Let us try it for the same function (p = 0.8) with different values of s:

Look at the last row. Even if you made the function take zero time, the program only gets 5 times faster. Because the other 20% is still there. That is the limit.

Think about what this teaches. Before you spend a week on a clever trick, ask: how big is the part I am about to change? If it is 2% of the time, the best possible win is 2%. This is why we will spend a whole Part on profilers. A profiler tells you p.

Build it (the "how")

Now let's feel how easily a measurement can lie.

An experiment: the number that was too good

We write a function that does real work. It runs a small random-number loop 200 million times. The compiler cannot turn it into a simple formula.

use std::hint::black_box;
use std::time::Instant;

// A loop the compiler cannot turn into a simple formula.
fn heavy(n: u64) -> u64 {
    let mut x: u64 = 88172645463325252;
    for _ in 0..n {
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
    }
    x
}

fn main() {
    let n = black_box(200_000_000u64);

    // Version 1: we never use the answer.
    let t = Instant::now();
    let _ = heavy(n);
    let ns1 = t.elapsed().as_nanos();

    // Version 2: we use the answer through black_box.
    let t = Instant::now();
    let r = heavy(n);
    black_box(r);
    let ns2 = t.elapsed().as_nanos();

    println!("answer never used : {:>12} ns", ns1);
    println!("answer black_boxed: {:>12} ns", ns2);
}

Build it with optimizations on, the way real programs are built:

rustc -C opt-level=3 a_deleted.rs -o a_deleted && ./a_deleted

Here is what I got:

answer never used :          121 ns
answer black_boxed:    417133002 ns

Read those two lines again.

The first version says: 200 million loop steps took 121 nanoseconds. That is less than the time light needs to travel 40 meters. It is not possible. A real loop of that size needs about 0.4 seconds, which is what the second line shows.

So what happened? In the first version, nobody uses the answer. The compiler can see this. It thinks: "This function has no side effects, and the result is thrown away. I can delete the whole call." So it does. We timed (almost) nothing. The 121 ns is most likely just the cost of asking the clock for the time, twice. (I did not check the machine code to confirm. Exercise 1.4 shows you how to test it yourself.)

In the second version, we pass the result to black_box. black_box is a function that tells the compiler: "assume this value is used somewhere you cannot see." Now the compiler must really compute it. And black_box(200_000_000) on the input also stops the compiler from knowing the value of n in advance, so it cannot pre-compute the answer at build time.

The lesson is simple and a little scary. The compiler is on your side when you ship the code, and against you when you test it. It is allowed to remove any work whose result you do not use. A benchmark that doesn't keep its work alive can report a speed that is off by a factor of three million.

(One honest note: black_box is a best-effort hint from the Rust standard library, not a guarantee. It works well in practice, and we will use it everywhere. Chapter 3 shows where else to be careful.)

Why it is this way (the "why")

Why can the compiler delete work? Because of one deep rule: the compiler only has to keep the program's observable behavior the same. It does not promise to keep your code's steps. If deleting a step changes nothing anyone can observe, then deleting is allowed. That rule is the reason Rust code can run so fast. Your benchmark is the one place where "nothing observable" is a trap.

This leads to the habit that all good performance engineers share. It is a loop. Write it down and use it every time:

  1. QUESTION      "How long does X take on input Y?"  (all five blanks filled)
        │
        ▼
  2. HYPOTHESIS    "I think the time is in Z, because ..."  (write it BEFORE you measure)
        │
        ▼
  3. MEASURE       with a method you can defend
        │
        ▼
  4. EXPLAIN       Why is the number what it is?  (If you can't explain it, you don't understand it yet)
        │
        ▼
  5. CHANGE        one thing
        │
        ▼
  6. MEASURE AGAIN and compare with step 3
        │
        └──────────► back to 1, or stop when the goal is met

Two of these steps are usually skipped. Step 2: if you do not write down what you expect, you cannot be surprised, and surprise is where learning comes from. Step 4: a number you cannot explain is a warning sign. In the experiment above, "121 ns for 200 million steps" should have made you stop and ask why. That one question found the deleted loop.

There is a bigger idea behind this. A measurement is not the truth. It is a model of the truth, made by a tool, under conditions. A famous 2009 paper (Mytkowicz and co-authors, in the reading list) showed that even tiny, harmless-looking choices in an experiment, like the order in which a program is linked, can change the result enough to flip the conclusion. The authors checked 133 papers from top conferences and found that none of the ones with experimental results considered this kind of bias properly. So if experts at top conferences get it wrong, you should assume that you can get it wrong too. The right attitude is not "my number is true". It is "my number is evidence, and here is how I tried to break it."

Common mistakes

• Fixing what feels slow. The slow-looking part is often not the slow part. Measure first.
• Timing a debug build. Debug builds are often many times slower than release builds, and they can have a different shape. Always measure --release (or -C opt-level=3).
• Trusting a number that is too good. If it is impossible, it is probably a deleted loop.
• Comparing numbers from different days or machines. Compare runs from the same machine, back to back, with only one change between them.
• Forgetting Amdahl. Optimizing a part that is 2% of the time.

Say it simply

A performance claim always has five blanks: the code, the time, the machine, the input, and the conditions. A number with blanks is just a feeling. The compiler can delete any work whose result you don't use, so a careless benchmark can measure nothing at all. Good performance work is a loop: ask a precise question, guess the answer, measure, explain the number, change one thing, and measure again. The size of the part you change decides the most you can win.

Check yourself

Exercise 1.1 (Warm-up): Fill the blanks. Rewrite each claim so all five blanks are filled, inventing reasonable details: (a) "Our API is fast." (b) "Rust is faster than Python." (c) "This sort is O(n log n), so it is fast."

Exercise 1.2 (Warm-up): Amdahl by hand. A program spends 30% of its time in function A and 60% in function B. (a) You make A 100 times faster. What is the whole-program speed-up? (b) You make B 2 times faster. What is it now? Which change is better? Surprised?

Exercise 1.3 (Warm-up): Latency or throughput? For each, say which one is the problem and why: (a) A web page takes 3 seconds to show up. (b) A nightly job must process 10 million records in 6 hours, and it takes 9. (c) A game drops frames when many enemies appear.

Exercise 1.4 (Core): Delete the work yourself. Run a_deleted.rs. Then pick a different pure function (for example, one that sums the squares of 0..n) and test three cases: (a) the result is never used, (b) the result goes through black_box but the input n is a plain constant, (c) both the input and the result go through black_box. Time each one. Which cases did the compiler shrink or delete, and which did it not? Done when: you can explain each of the three cases in one sentence.

Exercise 1.5 (Core): The five-blanks report. Take any loop you wrote in the past (a parser step, a sort, a hash-map lookup). Write the full question with five blanks, then a hypothesis ("I expect about X ns per item, because ..."). Do not measure yet. Save the page; you will test it in Chapter 4.

Exercise 1.6 (Stretch): Design and defend. Your team lead says: "Let's rewrite the tokenizer in assembly. It is the slowest part of the compiler." You have no profile. Write half a page: what would you ask for before agreeing, and what would make you say yes?

What a strong answer includes: the question of how big p is, a request for a profile, a note about Amdahl's limit, the cost of maintaining assembly, and what would count as a successful result.

Chapter 2. Noise, clocks, and distributions

In this chapter: You will learn why running the same code twice gives two different times, how to describe a pile of timings honestly, and which clock to use.

You need first: Chapter 1.

The problem first

Run a function 2,000 times. You will not get one number. You will get 2,000 numbers.

Which one is "the time"?

The first one? The average? The smallest? Many programmers pick one without thinking, and the pick changes the story. Let me show you with real data, and then we will build the words to talk about it.

The model (the "what")

Where the wobble comes from

The same code on the same data takes a different time on every run. The reasons:

• Other programs on the machine use the CPU, the caches, and the memory.
• The operating system interrupts your program to do its own jobs. (These are called interrupts: a signal that makes the CPU stop what it is doing for a moment and handle something else.)
• The CPU changes its speed to save power or to avoid getting too hot. This is called frequency scaling.
• The first run is slower because the data is not in the cache yet. Later runs are faster.
• In a cloud VM, other users share the same physical machine.

All of this wobble is called noise: changes in the measured time that are not caused by your code.

We cannot remove noise. We can only describe it honestly and keep it from fooling us.

The words for describing a pile of numbers

You have many timings. Here are the summaries, in plain words:

• Minimum (min): the fastest run. It shows what the code can do when nothing gets in the way.
• Mean (average): add them all and divide. Easy, but one huge slow run drags it up.
• Median: sort the numbers and take the middle one. Half the runs are faster, half are slower. A few huge values barely move it.
• Percentile: the value below which a given share of runs fall. The 95th percentile (p95) means 95% of runs were at or below this number. The p99 is the same for 99%. Percentiles describe the slow tail.
• Median absolute deviation (MAD): a measure of spread that ignores outliers. Take each timing's distance from the median, then take the median of those distances. It tells you how far a "typical" run sits from the typical value.
• Distribution: the full picture of how the numbers are spread out. Not one number. All of them.

A good habit: never report one number alone. Report at least the median and some measure of spread (p95 or MAD).

Which clock?

Computers have more than one clock, and mixing them up is a common bug.

• A wall clock (in Rust, SystemTime) tells you the date and time. The operating system can change it, for example when it syncs with a network time server. It can even go backwards. Never use it to time code.
• A monotonic clock (in Rust, std::time::Instant) only moves forward, and it is not changed when the date changes. Monotonic means "never goes backwards". This is the one to use for timing.

Even a monotonic clock is not free. Asking it for the time takes a little time. If your code takes 5 ns, and reading the clock takes 30 ns, you are measuring the clock. We will fix this in Chapter 4 by timing many runs at once and dividing.

Build it (the "how")

Here is a small program. It sums 100,000 numbers and times each run. It does this 2,000 times, then prints the summary and a histogram. (A histogram counts how many values fall in each range, so you can see the shape.)

use std::hint::black_box;
use std::time::Instant;

fn work(data: &[u64]) -> u64 {
    let mut s = 0u64;
    for v in data { s = s.wrapping_add(*v); }
    s
}

fn main() {
    let data: Vec<u64> = (0..100_000u64).collect(); // 800 KB
    let runs = 2000;
    let mut t: Vec<u64> = Vec::with_capacity(runs);
    for _ in 0..runs {
        let s = Instant::now();
        black_box(work(black_box(&data)));
        t.push(s.elapsed().as_nanos() as u64);
    }
    let mut sorted = t.clone();
    sorted.sort();
    let q = |p: f64| sorted[((runs as f64 - 1.0) * p) as usize];
    let mean = t.iter().sum::<u64>() as f64 / runs as f64;
    println!("runs   = {}", runs);
    println!("min    = {:>9} ns", sorted[0]);
    println!("median = {:>9} ns", q(0.5));
    println!("mean   = {:>9.0} ns", mean);
    println!("p95    = {:>9} ns", q(0.95));
    println!("p99    = {:>9} ns", q(0.99));
    println!("max    = {:>9} ns", sorted[runs - 1]);
    // (the histogram code is in the exercises' starter file; the output is shown below)
}

What I got on this machine:

runs   = 2000
min    =     11756 ns
median =     12427 ns
mean   =     13891 ns
p95    =     19099 ns
p99    =     28683 ns
max    =    102613 ns

histogram (last row = everything above 2x median):
    11756 ns | ################################                   1282
    12848 ns | #####                                              201
    13939 ns |                                                    23
    15030 ns | #                                                  79
    16122 ns | ######                                             278
    17214 ns |                                                    29
    18305 ns |                                                    27
    19396 ns |                                                    34
    20488 ns |                                                    3
    21580 ns |                                                    3
    22671 ns |                                                    2
    23762 ns |                                                    5
    24854 ns |                                                   34

Let's read this like a detective.

The spread is large. The fastest run took 11.8 µs. The slowest took 102.6 µs. That is 8.7 times the fastest. Same code, same data.

Mean and median disagree. The mean is 13.9 µs and the median is 12.4 µs. The slow tail pulled the mean up. This is exactly why the median is the safer "typical" value.

The histogram has two humps. One big hump near 11.8 µs (most runs) and a second, smaller hump near 16.1 µs (278 runs). It is not one smooth bell shape. I can't tell you from this data why there are two. Possible causes include the CPU switching speeds, another tenant on the same VM host, or the way the loop was placed in memory. A good next step would be to repeat the test with a fixed CPU frequency, but I could not do that in this VM. This is a reminder: if you only report the mean, you never see the two humps. The shape of the distribution often holds the story.

So which number is "the time"? It depends on the question:

Why it is this way (the "why")

Why is noise almost always on the slow side? Think about what can go wrong in a run. Another program can steal the CPU. An interrupt can pause you. The cache can be cold. All of these add time. Almost nothing makes your code run faster than its natural best. So a distribution of timings has a hard floor near the best case and a long tail stretching up. This shape is called a right-skewed distribution (a long tail on the right, to the slow side).

That one fact explains a lot of what comes later:

• The mean is a bad summary of a skewed shape, because the tail pulls it.
• The min is a good estimate of the best case, but a poor estimate of what users see.
• Tail latency (p99, p99.9) matters a lot in real services, because a user who makes many requests will meet the slow tail often. The slow tail is not an edge case. It is the experience of some real person.

There is a deeper idea here. When we time code, we are not measuring a number. We are sampling from a distribution. One sample tells you almost nothing. Many samples tell you the shape. The honest way to say "this code takes X" is "when I sampled it N times, the median was X, and 95% of runs were below Y." That is a smaller claim than "it takes X". It is also true.

What would make this model wrong? The "noise only adds time" idea fails sometimes. A CPU can boost its speed for short bursts, so the first runs can be faster than the long-run speed. Caches can also help one run and hurt the next. So the min is not always the "true" cost. This is why we describe the whole distribution, and why Chapter 37 will explain what "a cycle" even means.

Common mistakes

• Reporting only the mean. One slow run can wreck it.
• Reporting only the min. You will promise speeds that users never see.
• Timing a single run. One run is one sample from a distribution.
• Using SystemTime to time code. It can jump.
• Ignoring the shape. Two humps, a long tail, or slow drift each mean something. Look at the histogram.

Say it simply

Running the same code many times gives many different times, because other things on the machine add noise. Noise nearly always makes runs slower, so the timings form a long tail on the slow side. The mean is dragged by that tail, so the median and the percentiles are safer. Use a monotonic clock, Instant, because the wall clock can jump. Never say "it takes X". Say "the median was X, and 95% of runs were under Y."

Check yourself

Exercise 2.1 (Warm-up): Predict, then check. Before running anything, guess: for the program above, will the mean be higher or lower than the median? By how much? Then run it. Were you right?

Exercise 2.2 (Warm-up): Summary by hand. Timings in ns: 100, 102, 101, 99, 103, 100, 400, 101, 100, 102. Compute the min, median, mean, and the MAD by hand. Which one best matches "a typical run"? Which is most changed by the 400?

Exercise 2.3 (Warm-up): Which clock? A friend times code with SystemTime::now() and gets a negative duration. Explain, in four sentences, how that can happen and what to use instead.

Exercise 2.4 (Core): Your noise report. Run b_noise.rs on your own machine three times: (a) with nothing else running, (b) while another program is compiling a big project, (c) while a video plays. Make a table with min, median, p95, and max for each. Which number moved the most? Which moved the least? Done when: you have a 3-row table and 5 sentences about what changed and why.

Exercise 2.5 (Core): Find the second hump. Add the histogram code to the program (bins from the min to twice the median). Does your machine show one hump or two? If two, try pinning the program to one core with taskset -c 0 ./b_noise and compare. What changes?

Exercise 2.6 (Stretch): The cost of the clock. Write a loop that calls Instant::now() twice in a row, 1 million times, and records the gap between the two calls. What is the median? What does it tell you about the smallest time you can trust on your machine?

Exercise 2.7 (Stretch): Design and defend. A service owner says: "Our average latency is 20 ms, so we are fine." You see that the p99 is 900 ms. Write a short note to explain why the average hides a real problem, using one real-life analogy.

What a strong answer includes: the right-skewed shape, the idea that tail users are real users, and a request to look at the histogram or percentiles.

Chapter 3. Designing the workload and keeping the work alive

In this chapter: You will learn that a benchmark is a small world you build. If the world is wrong, a precise number is precise about the wrong thing. You will see how the shape of the input can change the time by 200 times.

You need first: Chapters 1 and 2.

The problem first

You want to know how fast sort is. So you make a vector of numbers and time sort. Easy.

But which numbers? Random ones? Already sorted ones? Do you copy the vector before sorting each time, or sort the same vector again and again? And does that copy count as part of the time?

Every one of these choices changes the answer. And most of the time we make them without noticing.

The model (the "what")

A workload is the input and the sequence of operations you give to the code in a test. A good workload has these properties:

1. Representative. It looks like the real data the code will meet. A benchmark on tiny, neat data tells you about tiny, neat data.
2. Deterministic. The same every time. If you use random data, use a seeded random generator (one that starts from a fixed number so it makes the same sequence each run). Otherwise two runs are not comparable.
3. Sized on purpose. The size of the data decides which rung of the memory ladder it lives on (Chapter 8). A test with 1,000 items might sit in L1. The real program might use 100 million.
4. Setup outside the timer. Building the input, cloning it, and allocating it should not be counted, unless that cost is exactly what you want to know.
5. Alive. Every result must be used (with black_box), so the compiler cannot delete the work. Every input should pass through black_box too, so the compiler cannot pre-compute the answer from a constant it can see.
6. Honest about state. Is the cache warm or cold? Is the data fresh or reused? State it, because the answers differ.

Think about it this way: the benchmark is a tiny model of the real world. All models are wrong in some ways. The skill is choosing what to keep.

Build it (the "how")

We time slice::sort on 1 million u32 numbers. But we try five different shapes of input. The clone of the input happens before the timer starts, so we only time the sort.

use std::hint::black_box;
use std::time::Instant;

fn xorshift(s: &mut u64) -> u64 { let mut x = *s; x ^= x << 13; x ^= x >> 7; x ^= x << 17; *s = x; x }

fn best_ms(input: &Vec<u32>) -> f64 {
    let mut best = f64::MAX;
    for _ in 0..9 {
        let mut v = input.clone();          // clone is outside the timer
        let t = Instant::now();
        v.sort();
        black_box(&v);
        best = best.min(t.elapsed().as_secs_f64() * 1000.0);
    }
    best
}

fn main() {
    let n = 1_000_000usize;
    let mut s = 12345u64;                   // fixed seed: same data every run
    let random: Vec<u32> = (0..n).map(|_| xorshift(&mut s) as u32).collect();
    let mut sorted = random.clone(); sorted.sort();
    let mut reversed = sorted.clone(); reversed.reverse();
    let few: Vec<u32> = random.iter().map(|x| x % 4).collect();
    let mut nearly = sorted.clone();
    for i in (0..n).step_by(1000) { nearly.swap(i, (i * 7919) % n); }

    println!("sorting {} u32 values with slice::sort (best of 9)", n);
    println!("random          : {:>8.2} ms", best_ms(&random));
    println!("already sorted  : {:>8.2} ms", best_ms(&sorted));
    println!("reversed        : {:>8.2} ms", best_ms(&reversed));
    println!("nearly sorted   : {:>8.2} ms", best_ms(&nearly));
    println!("only 4 distinct : {:>8.2} ms", best_ms(&few));
}

What I got (rustc 1.75):

sorting 1000000 u32 values with slice::sort (best of 9)
random          :    79.12 ms
already sorted  :     0.34 ms
reversed        :    16.61 ms
nearly sorted   :    37.40 ms
only 4 distinct :    72.15 ms

Same function. Same count of numbers. The time goes from 0.34 ms to 79 ms, a gap of about 230 times, just from the shape of the data.

Here is what I think each line is telling us:

• Already sorted: 0.34 ms. The standard sort in this Rust version looks for runs of numbers that are already in order. If the whole input is one run, there is almost nothing to do. It just checks once and finishes.
• Random: 79 ms. This is the true hard case. No pattern to use.
• Nearly sorted: 37 ms. Long runs exist, but there are breaks. Half the work of the random case.
• Only 4 distinct values: 72 ms. Only a little better than random. This sort does not take much advantage of lots of equal values.
• Reversed: 16.6 ms. I expected this to be as fast as the sorted case, since a reversed run is just an ordered run backwards. I did not dig into why it is not. Treat it as an open question. (Also: newer Rust versions changed the sort algorithm, so your numbers may differ a lot. That is a lesson on its own: a benchmark number belongs to a specific version of the code.)

The point is not these exact numbers. The point is that if you had only tested one shape, you would have believed one of these numbers was "the speed of sort", and you would have been wrong for every other shape.

Why it is this way (the "why")

Why does the input shape matter so much? Because almost all fast code is fast by using something about the data. A sort that finds runs uses order. A hash map uses the spread of the keys. A cache uses repeated access. A branch predictor uses patterns in the choices. Faster code usually means more assumptions about the data. When the data breaks the assumption, the speed goes away.

This gives you a principle to carry: an algorithm's speed is a relationship between the code and the data, not a property of the code. When someone says "this is faster", always ask: "On what data?"

It also changes how you design a workload. Ask three questions:

1. What does the real data look like? Where can I get a sample? (Real samples beat invented ones.)
2. What are the best and worst shapes? Test both ends.
3. What assumption does this code use, and does my test data keep that assumption true?

What would make this wrong? If your benchmark data is chosen after you see the results (you pick the shape where your change wins), you are not measuring. You are advertising. A defense: pick the workloads before you try the change, and write them down.

Common mistakes

• Only one input shape or size. Test at least a small, a medium, and a large size, and the best and worst shapes.
• Timing the setup. Clone, allocate, and build outside the timer.
• Reusing an already-sorted vector. Sorting the same vector again and again means the second run sorts sorted data.
• Random data without a seed. You cannot compare two runs.
• Never passing the input through black_box. The compiler may compute the answer at build time.
• Choosing the data after seeing the result.

Say it simply

A benchmark is a small world you build, and the answer is only true in that world. A good workload is realistic, repeatable, sized on purpose, free of setup cost, and kept alive so the compiler cannot delete it. The shape of the input can change a time by hundreds of times, because fast code works by using something about the data. So never say "this code is fast." Say "this code is fast on this kind of data."

Check yourself

Exercise 3.1 (Warm-up): Spot the bugs. This benchmark has three problems. Find them. let v = vec![5, 3, 1, 4, 2]; let t = Instant::now(); for _ in 0..1000 { let mut c = v.clone(); c.sort(); } println!("{:?}", t.elapsed());

Exercise 3.2 (Warm-up): Predict. Before running, rank these four inputs from fastest to slowest for HashMap lookups: (a) 1,000 keys looked up repeatedly, (b) 10 million keys looked up in random order, (c) 10 million keys looked up in insertion order, (d) 1,000 keys but each lookup is for a key not in the map. Give a one-sentence reason for each rank.

Exercise 3.3 (Core): Run the sort experiment. Run c_inputs.rs on your machine and on a second Rust version if you can (rustup toolchain install a newer one). Compare tables. Which lines changed the most? Explain one change. Done when: a table with both versions and 5 sentences of explanation.

Exercise 3.4 (Core): Size sweep. Pick a function (for example, summing a Vec<u64>) and time it at sizes from 1,000 up to 100 million items, doubling each time. Plot time per item against size. Where do jumps appear? (Keep this plot. You will explain it fully in Chapter 8.)

Exercise 3.5 (Core): Break the benchmark. Write a loop that "benchmarks" x * 3 + 1 summed over 0..n and finds a time per step of 0.0 ns. Explain exactly which optimization removed the work. Then fix it so it is a fair test.

Exercise 3.6 (Stretch): Design and defend. You are benchmarking a JSON parser. List five input files you would choose, and what each one tests. Explain what you would do to make sure you did not pick them to flatter your code.

What a strong answer includes: tiny and huge files, deeply nested vs flat, many short strings vs a few long ones, number-heavy vs string-heavy, and real files from real sources written down before the change.

Chapter 4. Build a tiny benchmark harness

In this chapter: You will build a 60-line benchmark tool from scratch, one decision at a time. You will test the tool itself with a function of known cost. And you will see a case where the tool is right and the result is still surprising.

You need first: Chapters 1 to 3.

The problem first

Why build your own harness when tools like Criterion exist?

Because you cannot trust a tool you do not understand. Criterion is excellent (Part II), and you will use it in real work. But if you have once built the simplest version, you will know what every part of it is for, and why it is there. Later, when it gives a strange number, you will know where to look.

We also keep the harness small on purpose. A small tool that says clearly what it does not do is better than a big one that hides its guesses.

The model (the "what")

A benchmark harness has to solve three problems:

Problem 1: The clock is slow compared to fast code. If your code takes 5 ns and reading the clock takes 30 ns, one run tells you nothing. Solution: run the code many times in a batch and time the whole batch, then divide. This is called amortizing the clock cost: spreading one fixed cost over many items so it becomes tiny.

Problem 2: How big should the batch be? Too small and the clock cost still dominates. Too big and the test takes forever. Solution: calibration. Start with a batch of 1 call. Double it until one batch takes at least a chosen time (we use 2 ms). Now the clock cost is a tiny share.

Problem 3: One batch is one sample from a noisy distribution. Solution: take many samples (we use 100), then summarize with robust numbers (the median, p95, and MAD from Chapter 2).

And the harness must keep the work alive: pass each result to black_box.

Build it (the "how")

Here is the whole harness. Read it top to bottom. Each piece matches a decision above.

use std::hint::black_box;
use std::time::{Duration, Instant};

pub struct Report {
    pub iters_per_sample: u64,
    pub samples: usize,
    pub min: f64,    // all numbers are nanoseconds per call
    pub median: f64,
    pub p95: f64,
    pub mad: f64,    // median absolute deviation
}

fn median_of_sorted(v: &[f64]) -> f64 {
    let n = v.len();
    if n % 2 == 1 { v[n / 2] } else { (v[n / 2 - 1] + v[n / 2]) / 2.0 }
}

fn time_batch<F: FnMut() -> R, R>(f: &mut F, iters: u64) -> Duration {
    let start = Instant::now();
    for _ in 0..iters {
        black_box(f());
    }
    start.elapsed()
}

pub fn bench<F: FnMut() -> R, R>(mut f: F) -> Report {
    // Step 1: calibrate. Double the batch size until one batch takes at least 2 ms.
    let target = Duration::from_millis(2);
    let mut iters: u64 = 1;
    loop {
        if time_batch(&mut f, iters) >= target || iters >= (1 << 40) { break; }
        iters *= 2;
    }

    // Step 2: take many samples. Each sample is one batch, divided by its size.
    let samples = 100;
    let mut per_call: Vec<f64> = Vec::with_capacity(samples);
    for _ in 0..samples {
        let d = time_batch(&mut f, iters);
        per_call.push(d.as_nanos() as f64 / iters as f64);
    }

    // Step 3: summarize with numbers that ignore rare big spikes.
    per_call.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let median = median_of_sorted(&per_call);
    let p95 = per_call[(samples as f64 * 0.95) as usize - 1];
    let mut dev: Vec<f64> = per_call.iter().map(|x| (x - median).abs()).collect();
    dev.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let mad = median_of_sorted(&dev);

    Report { iters_per_sample: iters, samples, min: per_call[0], median, p95, mad }
}

(The small print helper that formats one line is in the starter file for the exercises.)

A few notes on the choices:

• FnMut lets the closure keep and change its own state between calls.
• The 1 << 40 limit stops the calibration loop if the closure does almost nothing, so we never loop forever.
• The calibration batches double as a warmup: they run the code a few times before we collect the real samples, so caches and branch predictors have settled.

Test the tool before the workload

Here is the most important habit in this chapter. Before you trust a measuring tool on something you don't know, test it on something you do know. A doctor calibrates the scale with a known weight first.

We have two known cases:

1. An empty closure. The true cost is almost zero. So whatever the harness reports is the harness overhead, the least it can ever show.
2. A function that spins for exactly 50 microseconds. The true cost is 50,000 ns. The harness must say about 50,000.

empty closure          median       0.36 ns  p95       0.45  min       0.33  MAD     0.01  (8388608 calls/sample)
spin 50 us (known)     median   50309.42 ns  p95   50774.86  min   50069.55  MAD   194.12  (64 calls/sample)

Read it:

• The empty closure says 0.36 ns per call. So the harness's own cost is about a third of a nanosecond. Anything we measure above a few ns is dominated by the real work. And look: calibration chose 8.4 million calls per sample. That is what it takes to make a 0.36 ns call last 2 ms.
• The 50 µs spin says 50,309 ns. That is within 0.6% of the truth. The harness passes. (It is slightly above 50,000, which makes sense: the spin loop checks the clock and can only stop after the time has passed.)

Now a real workload, summing 100,000 numbers:

sum 100k u64           median   11993.62 ns  p95   13051.83  min   11345.94  MAD   147.43

About 12 µs, with a small MAD. Stable and believable. (And it agrees with Chapter 2's plain loop: a median of 12.4 µs.)

The surprise

Here is something I did not plan. In the first version of this test, I ran the same summing code a second time, in a second closure, right after the first. I expected the same number. I got a different one, and I got it on both of two separate runs of the program:

sum 100k u64           median   11993.62 ns
sum 100k u64 (again)   median   17670.51 ns      <- 47% slower, same code

The second run was about 47% slower, and the MAD was small, so it was not random noise. It was stable and wrong.

I checked one idea: maybe it is about running second. So I made a function sum(&data) and called it from four closures in a row. Result:

run 1   median 11973.60 ns
run 2   median 11685.59 ns
run 3   median 12153.55 ns
run 4   median 12036.77 ns

All four are the same, within about 4%. So the slowdown is not about being second. It followed the code: the version where the loop was written directly inside the closure behaved differently from the version that called a shared function.

I can't tell you the exact cause. I have not looked at the machine code. Good guesses: the compiler made a different copy of the loop (for example, one vectorized and one not), or the two copies landed at different memory addresses, and the CPU treats those differently. In Chapter 14 and later, you will learn the tools to look at the machine code and settle this question properly.

This looks like the same kind of problem the Mytkowicz paper from Chapter 1 warns about, showing up in 60 lines of code. (I have not proven it is the same cause.) A harness can be perfectly correct, and the number can still depend on details that have nothing to do with the algorithm. That is why the answer to "my benchmark says B is faster than A" is always: "Did you check that it does not depend on code placement and compiler choices?"

Why it is this way (the "why")

Every part of the harness is a trade-off.

• Median, not mean. Because of the long slow tail (Chapter 2). The harness gives up the "exactness" of the mean to get stability.
• Many calls per sample. We trade a longer test for a lower clock cost.
• A 2 ms target. Why 2? Because the clock overhead is about tens of nanoseconds, so 2 ms makes it under 0.01% of the batch. Longer would be more precise and slower. This is a choice, not a law. It is okay to change it, as long as you know why.
• 100 samples. More samples give a better picture of the shape. But there is a limit: if the machine drifts (slow warm-up, other tenants), more samples just record the drift.

And now the important part: what does this harness NOT do? Writing this down is the honest thing, and it is how you avoid lying with the tool:

• It does not pin the program to one CPU core or fix the CPU frequency.
• It does not detect and remove outliers or give confidence intervals.
• It does not check that two copies of the same code behave the same (see the surprise above).
• It does not compare two versions with any statistics. If A shows 12.0 µs and B shows 11.7 µs, the harness cannot tell you whether that is a real difference.
• It does not reset the cache between samples, so it measures the warm case.

Criterion (Part II) addresses several of these. When you read its output, you will see each one of these problems handled in a specific way. That is the real reason to build the small one first.

The philosophy: a tool should make it easy to tell the truth and hard to tell a lie. The empty-closure test and the known-duration test are not extras. They are how a measuring tool earns the right to be believed.

Common mistakes

• Trusting a harness you never tested on a known case.
• Too few iterations per sample. The clock cost leaks into the answer.
• Forgetting black_box on the result. The work disappears (Chapter 1).
• Comparing two numbers 2% apart without any idea of the spread. Check the MAD first.
• Believing a number just because the MAD is small. A small spread says the result is repeatable. It does not say it is right. The surprise above had a small MAD and an odd result.

Say it simply

A benchmark harness fixes three problems: the clock is slow compared to fast code, the right batch size is unknown, and one batch is only one noisy sample. It fixes them by timing a big batch and dividing, doubling the batch size until it lasts a couple of milliseconds, and taking many samples and reporting the median and the spread. You must test the harness on something with a known cost before trusting it. Even a correct harness can give a stable but odd number when the compiler or the code placement changes, so always ask what the harness does not control.

Check yourself

Exercise 4.1 (Warm-up): Predict. The empty closure reported 0.36 ns. At a clock speed of 2.1 GHz, how many CPU cycles is that? (One cycle at 2.1 GHz lasts about 0.48 ns. The real core clock of this machine turned out to be about 3.3 GHz, see Chapter 37; do the exercise with both.) What does that number suggest the loop is doing?

Exercise 4.2 (Warm-up): Explain. In 5 sentences, explain to a friend why we time a batch of calls and divide, instead of timing each call. Use an analogy (for example, weighing a single sheet of paper).

Exercise 4.3 (Core): Build and validate. Type in the harness. Run the two known-cost tests on your machine. Report the error as a percent. Now write a third known-cost test: a function that does a fixed, known amount of work, and check it against what you expect. Done when: a table with 3 rows: harness overhead, the 50 µs spin, your own third test, each with the error.

Exercise 4.4 (Core): Is the second run really slower? Reproduce the surprise. Write two closures with the loop written out inline, and one that calls a shared function. Run all three on your machine. Do you see a difference? (It may not appear on your machine, and that is also a valid result.) Report what you saw. Hint: compile with rustc -C opt-level=3 --emit asm and compare the loops.

Exercise 4.5 (Core): Add what is missing. Extend the harness so it also reports the relative spread: MAD divided by the median, as a percent. Run the sum benchmark and write one sentence on what this percent tells you.

Exercise 4.6 (Stretch): Build the comparison. Write compare(a, b) that runs two closures interleaved (A, B, A, B, ...) with 100 samples each, and reports the ratio of medians. Why might interleaving give a fairer answer than running all of A and then all of B? Test it by comparing a function with itself. What ratio should you get? What do you get?

Exercise 4.7 (Stretch): Design and defend. A teammate wants to use the mean in the harness because it is "simpler and more standard". Write a half-page argument for or against, using a distribution from Chapter 2 as evidence.

What a strong answer includes: the skewed tail, the example of the mean being 12% above the median in Chapter 2's run, when the mean is still the right tool (total time for a big job), and what to do if the team still prefers the mean (report both).

Part I wrap-up

What you can now do:

• Turn a vague "it's fast" into a five-blank claim you can check.
• Explain how the compiler can delete a benchmark, and stop it.
• Describe a pile of timings with the median, the percentiles, and the spread, and pick the right one for the question.
• Design a workload on purpose, with a fixed seed, setup outside the timer, and realistic shapes and sizes.
• Build a small benchmark harness, test it on a known cost, and say exactly what it does not control.

Mini project: The honest benchmark report (2 to 4 hours). Pick a small function you care about (a tokenizer step, a hash, a sort, a matrix row sum). Using your harness:

1. Write the five-blank question and your hypothesis first.
2. Design at least three workloads (a small, a medium, and a large size, or three shapes) and write down why you picked them before measuring.
3. Measure with the harness. Include a known-cost test in the same run.
4. Report the median, p95, and MAD for each workload.
5. Check the stability: run the whole thing three times. How much did the medians move?

Done when: you have a one-page report where every claim has the five blanks filled, and a short list of "what this report does not show."

Write-up prompt: Half a page. What did you expect, what did you see, and what surprised you?

Teach it back: In 5 sentences, explain to a friend why "my benchmark says 3 ns" might be completely meaningless.

Reading list for Part I:

• Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter F. Sweeney, "Producing Wrong Data Without Doing Anything Obviously Wrong!", ASPLOS 2009 (pages 265 to 276). Short and shocking. It shows that tiny, innocent choices in an experiment can change the conclusion. Read the introduction and the first case study.
• John Ousterhout, "Always Measure One Level Deeper", Communications of the ACM, 2018. It turns the fear from the paper above into practical advice: when you measure a result, also measure what causes it.
• The Rust standard library documentation for std::hint::black_box. Read what it promises and, more importantly, what it does not promise.

Verification notes for this file so far: All code in Part I was compiled with rustc 1.75 and run on a 1-core Xeon VM (2.1 GHz). All printed outputs are real runs, shortened only where marked. The Mytkowicz paper details (title, venue, year, page numbers, the 133-paper survey) were checked against the authors' page and a course blog. The Ousterhout article is recommended based on its mention in a course reading and not read in full for this file. Not confirmed: the cause of the two-humped histogram in Chapter 2, the reason reversed sorts slower than expected in Chapter 3, and the cause of the 47% slowdown in Chapter 4. Each is marked as open and has an exercise to investigate.

Part II. Benchmarking in practice with Criterion

After this Part, you will be able to run a real benchmark tool, read every line of its report, and say whether a change is real, tiny, or just noise.

In Part I, we built a small harness by hand. Now we use the standard tool that most Rust projects use: Criterion.rs. Because you built the small one, Criterion will not feel like magic. Every line it prints answers a problem you already met.

Chapter 5. Install Criterion and read your first report

In this chapter: You will set up Criterion, write one benchmark, and read each line of the report. You will see that Criterion and your own harness agree on the same function.

You need first: Part I.

The problem first

You have a harness. It gives a median, a p95, and a MAD. So why use something else?

Because a harness like ours leaves out several jobs: it does not give a confidence interval for the answer, it does not compare with your last run, it does not draw plots, and it does not tell you if a change is real. Doing those jobs well takes statistics. Criterion does them for you, and does them in a way many people have checked.

But a tool you do not understand will lie to you politely. So let's learn what each line means.

The model (the "what")

Criterion.rs is a benchmarking library for Rust. You write a benchmark function. Criterion runs it many times, collects timings, and does statistics on them.

Here is the plan it follows for every benchmark:

  1. WARM UP     Run the code for a few seconds, so caches and the CPU settle.
        │
        ▼
  2. COLLECT     Take N samples (default 100). Each sample runs the code many times
        │        in a batch, like our harness. (Batches grow from sample to sample.)
        ▼
  3. ANALYZE     Estimate the time per call, and a range around it, using a statistics
        │        method called the bootstrap. (Chapter 34 opens this up.)
        ▼
  4. COMPARE     If there is a saved result from an earlier run, say whether the
                 time changed. (Chapter 6.)

Do not worry about the statistics yet. Think of it as our harness, with a better summary and a memory.

Some words:

• A sample is one timed batch.
• A confidence interval is a range that probably contains the true value. A 95% confidence interval is built by a method that, if you repeated the experiment many times, would capture the true value about 95 times out of 100. It is not "the true value is inside this range with 95% chance". It is a statement about the method. For our purpose: a narrow interval means a stable measurement, and a wide one means a noisy measurement.
• A bootstrap is a way to get a confidence interval by re-using your own samples many times (re-sampling with replacement) and seeing how much the answer wobbles.

The defaults of Criterion 0.8 (I checked these in its source code): 100 samples, 3 seconds of warm-up, 5 seconds of measuring, 100,000 bootstrap re-samples, a 95% confidence level, a 5% significance level, and a 1% noise threshold. The last two matter in Chapter 6.

Build it (the "how")

Set up

Criterion 0.8 needs a recent Rust. Its changelog says the minimum supported Rust version is 1.86. (Older versions are fine for older Criterion: 0.5 works with much older Rust. Check your own version with rustc --version.) For this guidebook, I ran Criterion 0.8.2 with rustc 1.91.1. The plain programs in Part I used rustc 1.75. That is fine, because those programs do not depend on newer compiler features.

Create a project:

cargo new --lib pc
cd pc

Edit Cargo.toml:

[package]
name = "pc"
version = "0.1.0"
edition = "2021"

[dev-dependencies]
criterion = "0.8"

[[bench]]
name = "sum"
harness = false

Two things to understand:

• [dev-dependencies] means Criterion is only used for tests and benchmarks, not in your final program.
• harness = false tells Cargo: "do not use the built-in test runner for this file. Criterion has its own main."

Optional: install gnuplot for nicer plots. Without it, Criterion uses another plot method. The numbers are the same.

Write the benchmark

Create benches/sum.rs:

use criterion::{criterion_group, criterion_main, Criterion};
use std::hint::black_box;

fn sum(data: &[u64]) -> u64 {
    let mut s = 0u64;
    for v in data {
        s = s.wrapping_add(*v);
    }
    s
}

fn bench_sum(c: &mut Criterion) {
    let data: Vec<u64> = (0..100_000u64).collect();
    c.bench_function("sum 100k u64", |b| b.iter(|| sum(black_box(&data))));
}

criterion_group!(benches, bench_sum);
criterion_main!(benches);

Read the pieces:

• c.bench_function("name", |b| ...) registers one benchmark with a name.
• b.iter(|| ...) is the heart. Criterion calls this closure again and again and times it. The setup (building data) is outside, so it is not timed. This is the "setup outside the timer" rule from Chapter 3.
• We use std::hint::black_box. Since 0.8, Criterion itself uses the standard one, and the old criterion::black_box is no longer the way to go.
• criterion_group! and criterion_main! are macros that create the main function.

Run it:

cargo bench --bench sum

The first build takes a while because Cargo compiles Criterion and its dependencies. (On this 1-core VM, it took about 2 minutes. Later runs are fast.)

Read the report

Benchmarking sum 100k u64: Warming up for 3.0000 s
Benchmarking sum 100k u64: Collecting 100 samples in estimated 5.0590 s (404k iterations)
Benchmarking sum 100k u64: Analyzing
sum 100k u64            time:   [12.024 µs 12.046 µs 12.070 µs]
Found 9 outliers among 100 measurements (9.00%)
  3 (3.00%) low mild
  2 (2.00%) high mild
  4 (4.00%) high severe

Go line by line.

"Warming up for 3.0000 s" is step 1. It ran the code for 3 seconds without recording.

"Collecting 100 samples in estimated 5.0590 s (404k iterations)" is step 2. Criterion guessed how many total runs fit in about 5 seconds: 404,000 runs of sum, split over 100 samples. (In this default mode, the batches grow from sample to sample, which lets Criterion separate the fixed cost per sample from the cost per call.)

time: [12.024 µs 12.046 µs 12.070 µs] is the answer. Three numbers: the lower end of the 95% confidence interval, the best estimate (middle), and the upper end. So the best guess is 12.046 µs, and Criterion is 95% confident, in the confidence-interval sense, that the true value is between 12.024 and 12.070. The interval is only 0.4% wide. That is a very stable measurement.

Compare with Part I. Our harness said a median of 11.99 µs. The plain loop in Chapter 2 said 12.4 µs. Criterion says 12.05 µs. Three different tools, within a few percent. When different methods agree, you can start to believe the number.

"Found 9 outliers among 100 measurements" reports samples that sit far from the others. We unpack these in Chapter 6.

Criterion also writes an HTML report, with plots, to target/criterion/report/index.html. Open it in a browser. It shows the distribution of samples, and a plot of time against the number of iterations. You will use it when a number looks strange.

Why it is this way (the "why")

Why does Criterion give a range and not a single number? Because of what we learned in Chapter 2: a timing is a sample from a distribution. A single number hides how much you can trust it. A range says: "this is how sure I am."

Why does it warm up for 3 seconds? Because the first runs are not typical (cold caches, CPU speed changing, memory pages not mapped yet). The warm-up is a decision: I want to measure the steady state. That is a choice about the question. If you care about the first call (a command-line tool that starts, runs once, and exits), steady-state numbers will mislead you. We said this in Chapter 3: be honest about state.

Why 100 samples and 5 seconds? These are defaults that work for many cases. Not laws. For a very fast function you may want fewer seconds. For a noisy machine, more samples. You can change them in code or on the command line. You will see --warm-up-time 1 --measurement-time 3 in later runs in this guidebook, to keep tests short.

One more idea. Criterion is a measuring instrument, not an oracle. It measures what you put inside b.iter. All the lessons from Part I still apply: keep the work alive, choose the workload on purpose, say what the state is. A beautiful confidence interval of 0.4% on a deleted loop is a very precise measurement of nothing.

Common mistakes

• Putting setup inside b.iter. Then you time the setup.
• Forgetting black_box on the input. The compiler may fold the answer at build time.
• Reading a narrow interval as "correct". It means stable, not right.
• Using the wrong Rust version for the Criterion version. Check the minimum supported version in the changelog.
• Benchmarking in debug mode. cargo bench builds in release-like mode already. Do not use cargo run or a debug build for timing.

Say it simply

Criterion is a benchmarking library that warms up, collects 100 timed samples, and reports a best estimate with a range around it. You write the code to test inside b.iter, keep setup outside, and pass inputs and outputs through black_box. The range tells you how stable the measurement is, not whether it is correct. On our summing loop, Criterion, our harness, and the plain loop all agreed within a few percent.

Check yourself

Exercise 5.1 (Warm-up): Read the line. time: [8.201 ms 8.455 ms 8.730 ms]. What is the best estimate? How wide is the interval, as a percent of the estimate? Is this a stable or a noisy measurement? Compare with [12.024 µs 12.046 µs 12.070 µs].

Exercise 5.2 (Warm-up): Explain. In 5 sentences, explain to a friend what a confidence interval is not. Use the "method, not the value" idea.

Exercise 5.3 (Core): Install and run. Set up the project above, run the benchmark, and open target/criterion/report/index.html. Describe what the plots show. Compare Criterion's number with your own harness from Chapter 4. Report the difference as a percent. Done when: you have both numbers side by side and one sentence on why they differ.

Exercise 5.4 (Core): Break it on purpose. Remove black_box from the input in the benchmark (write sum(&data)). Does the number change? Now also make data a constant array known at compile time. What happens? What did the compiler do? Hint: look at the HTML report. A tiny time per call is a sign of folded work.

Exercise 5.5 (Core): Move the knobs. Run with -- --warm-up-time 1 --measurement-time 2 and then with -- --sample-size 20. How does the interval width change? Which run would you trust more, and why?

Exercise 5.6 (Stretch): Design and defend. A command-line tool is run once, reads a file, parses it, prints a result, and exits. A teammate benchmarks the parse function with Criterion and finds it takes 40 µs. In real use, the parse takes 2 ms. Give three reasons the numbers could disagree.

What a strong answer includes: cold caches and cold code on the first call, warm-up hiding page faults, the file read cost, and a different input shape.

Chapter 6. Estimates, outliers, and "is this change real?"

In this chapter: You will learn the three ideas that decide whether Criterion says "improved", "regressed", or "no change". You will see a case where the same code gets flagged as changed, and learn why that happens.

You need first: Chapter 5.

The problem first

You change a function. You run the benchmark. It says 12.2 µs, and last time it said 12.0 µs.

Did you make it slower? Or is that just wobble?

Without a rule for deciding, every small difference starts an argument. With a rule, you get a decision. Criterion has a rule. But the rule has two parts, and you must know both, because each part can fool you in its own way.

The model (the "what")

When a saved result from an earlier run exists, Criterion runs the new benchmark and compares. It reports a line like:

change: [−0.6926% −0.0294% +0.5305%] (p = 0.93 > 0.05)
No change in performance detected.

Three pieces:

1. The change estimate with its interval: [low, middle, high] as a percent change in the time. Negative means faster. Positive means slower. The middle is the best guess.

2. The p-value: Criterion asks: "If the old and new code were truly the same speed, how likely would I be to see a difference at least this big, just from noise?" That chance is the p-value. A tiny p-value means "that would be very surprising if nothing changed." The cut-off is the significance level, 0.05 by default (5%).

3. The noise threshold: a size cut-off, 1% by default. Even if a change is statistically real, it is ignored if it is too small to matter.

Here is the exact rule, from reading Criterion's source:

IF  p-value is NOT below 0.05
        →  "No change in performance detected."
ELSE (the change looks real, statistically)
    IF  the WHOLE confidence interval of the change is below −1%
            →  "Performance has improved."
    ELIF the WHOLE confidence interval is above +1%
            →  "Performance has regressed."
    ELSE
            →  "Change within noise threshold."

Look at this carefully, because it tells you what each part does:

• The p-value asks: is there a difference at all?
• The noise threshold asks: is the difference big enough to care about?
• "Whole interval beyond ±1%" means the tool wants to be sure even the least extreme end of the interval is bigger than 1%.

Two different kinds of "not important" can happen. A difference can be not statistically real (p is big). Or it can be real but tiny (p is small, but the change is under 1%). Both end in "not worth acting on", but for different reasons.

Outliers

The report also says things like:

Found 9 outliers among 100 measurements (9.00%)
  3 (3.00%) low mild
  2 (2.00%) high mild
  4 (4.00%) high severe

An outlier is a sample far from the others. Criterion uses a classic rule from statistics (Tukey's fences): take the first quartile (the value that 25% of samples fall below), the third quartile (75%), and the gap between them, called the IQR (interquartile range). A sample more than 1.5 × IQR beyond the quartiles is a mild outlier, and one beyond 3 × IQR is a severe outlier. "Low" means faster than most, "high" means slower than most. (I confirmed the 1.5 factor in the source. The 3× severe step is the standard rule.)

What do outliers tell you? Not that the answer is wrong. They are a hint about noise. Many high outliers means something slowed some samples: other programs, interrupts, a noisy VM neighbor. A lot of outliers (more than about 10%) is a signal to quiet the machine and run again.

Build it (the "how")

I ran the benchmark from Chapter 5 several times, changing the code between some runs. Here is what Criterion said. (I used -- --warm-up-time 1 --measurement-time 3 for runs 2 to 5, to keep them short.)

Run 2: the same code, run again.

sum 100k u64            time:   [12.116 µs 12.200 µs 12.285 µs]
                        change: [−0.6926% −0.0294% +0.5305%] (p = 0.93 > 0.05)
                        No change in performance detected.

Good. The change is −0.03%, the p-value is 0.93, very far above 0.05. The code is the same, and Criterion says so.

Run 3: the same code, run once more.

sum 100k u64            time:   [12.143 µs 12.242 µs 12.377 µs]
                        change: [+0.6944% +1.7265% +2.8612%] (p = 0.00 < 0.05)
                        Change within noise threshold.

This is the interesting one. The code did not change at all. Yet Criterion says the p-value is 0.00, far below 0.05, so the difference looks "statistically real". The best estimate is +1.7% slower. But the interval is [+0.69%, +2.86%]. The lower end, +0.69%, is not above the 1% threshold. So the whole interval is not beyond +1%, and the verdict is "within noise threshold".

Why would identical code give a "real" difference? Because the machine was a bit different between the two runs: another tenant on the VM host, a different CPU speed, a slightly different cache state. Criterion measures the machine and the code together. The p-value is honest: the two sets of samples really did differ. But the cause was not your code. Statistical significance is not the same as caused by your change.

And that is exactly why the noise threshold exists. Without it, Run 3 would be flagged as a regression. With it, a 1.7% shift that is likely caused by the environment is quietly set aside.

Run 4: I made the code slower on purpose (a black_box call inside the loop for each element, which stops the compiler from combining the work):

sum 100k u64            time:   [54.748 µs 56.503 µs 58.303 µs]
                        change: [+356.13% +369.08% +382.42%] (p = 0.00 < 0.05)
                        Performance has regressed.

A real change. The whole interval is far beyond +1%. Criterion says "regressed". Also, the interval got wider (about 6% wide, versus 0.7% before). The new code is less stable.

Run 5: I put the fast code back.

sum 100k u64            time:   [12.633 µs 12.832 µs 13.034 µs]
                        change: [−78.948% −78.364% −77.738%] (p = 0.00 < 0.05)
                        Performance has improved.

A real change in the other direction. The new time (12.8 µs) is also a bit higher than runs 1 to 3 (about 12.0 to 12.2 µs). So, even for the "same fast code", the level drifts by about 5% between runs on this VM. Remember that number. It is the size of change this machine can invent.

The summary of what we saw

The runs show a big change is easy to see, and a small one is hard.

Why it is this way (the "why")

Why two tests (p-value and threshold) and not one? Each one answers a different question.

Think about a thermometer with a very high resolution. It can tell you the room warmed by 0.0003 degrees. That is statistically real. It is also useless. A p-value can only tell you if a difference is detectable. As your measurement gets more precise (more samples, a quieter machine), you can detect smaller and smaller differences, down to ones nobody cares about. The noise threshold is how you say "below this size, I don't care". It is a human decision about what matters, put into the tool.

So the philosophy is: statistics tells you what is real. Your goals tell you what is important. Both are needed.

Now the dangerous part. The 5% significance level means that if you compare identical code many times, about 1 in 20 comparisons will look "significant" by pure chance. (That is the definition of the level, in the ideal case where noise is purely random.) On a real machine, noise is not purely random: it drifts, and it has patterns. So the real false-alarm rate can be higher. Chapter 7 shows a real false alarm from this very machine.

What would make the rule wrong? Three things:

1. The noise is not random. The t-test and the bootstrap assume a certain kind of independent noise. A machine that drifts breaks that.
2. The comparison is not like for like. If the old result was saved a week ago on a different machine state, Criterion cannot know.
3. You make many comparisons. If you compare 40 benchmarks at once, you should expect about 2 false alarms at the 5% level. A single flagged benchmark among forty is weak evidence.

A good habit follows: measure your own measurement. Run the unchanged code twice (as in Runs 2 and 3) and see how much it moves. That tells you the size of the wobble on your machine. A real change should be clearly bigger than that wobble. On this VM, I'd call anything under about 5% suspicious.

Common mistakes

• Treating "p < 0.05" as "my change caused it". It only says the two sets of runs differ.
• Ignoring the size. A "significant" 0.8% change is rarely worth any work.
• Skipping the unchanged-code test. You have no idea how big your machine's wobble is.
• Reading outliers as errors. They are a hint about noise, not a verdict.
• Reading a single flagged benchmark among many. Expect some false alarms.
• Comparing against a baseline from a different day, machine, or Rust version.

Say it simply

Criterion decides "improved", "regressed", or "no change" with two tests. The p-value asks whether the two sets of timings differ more than noise would explain. The noise threshold, 1% by default, asks whether the whole confidence interval of the change lies beyond that size. A change can be real but too small to matter, and identical code can still look "real" when the machine drifts. So run your unchanged code twice to learn the size of your own wobble, and treat anything near that size as noise.

Check yourself

Exercise 6.1 (Warm-up): Read the verdict. For each, say what Criterion's rule gives: (a) change: [−0.4% +0.1% +0.7%] (p = 0.60) (b) change: [+2.1% +3.0% +3.9%] (p = 0.00) (c) change: [+0.2% +1.4% +2.6%] (p = 0.01) (d) change: [−9.0% −7.5% −6.0%] (p = 0.00).

Exercise 6.2 (Warm-up): Explain. In 5 sentences, explain to a friend why a very precise thermometer is a good analogy for the difference between "statistically real" and "important".

Exercise 6.3 (Core): Measure your own wobble. Run the unchanged benchmark 10 times in a row (cargo bench --bench sum -- --warm-up-time 1 --measurement-time 3). Record the middle estimate and Criterion's verdict each time. How big is the largest swing? How many runs got a verdict other than "no change"? Done when: you have a table of 10 rows and a sentence like "on my machine, a change under X% is indistinguishable from noise".

Exercise 6.4 (Core): Make a real change. Make the function slower in a small way (for example, add one extra wrapping_add per element). What is the smallest change Criterion can reliably flag on your machine? Try three sizes of change.

Exercise 6.5 (Core): The outlier test. Run the benchmark while another program uses the CPU heavily. How does the outlier count change? Does the best estimate change? Does the interval get wider? Write 4 sentences about what the outlier report told you.

Exercise 6.6 (Stretch): Move the threshold. Run with --noise-threshold 0.05 and then --noise-threshold 0.001, and re-run the unchanged-code test. How does the number of false alarms change? What does this tell you about choosing the threshold? Hint: the flag is --noise-threshold. I saw it in the source code.

Exercise 6.7 (Stretch): Design and defend. Your team runs 60 benchmarks on every pull request, and the CI fails if any benchmark is flagged as "regressed". After a month, people ignore the failures. Explain why this happens using what you learned, and propose a better rule.

What a strong answer includes: false alarms from many comparisons at a 5% level, noisy shared CI machines, the idea of a larger threshold or a repeat-before-fail rule, comparing on dedicated hardware, and the cost of crying wolf.

Chapter 7. Groups, inputs, throughput, and baselines

In this chapter: You will learn to benchmark the same idea at many sizes, to report speed as "items per second", and to save a result and compare against it later. You will see a real false alarm, and learn that one trick can help at one size and do nothing at another.

You need first: Chapters 5 and 6.

The problem first

One number from one input is almost never what you need. You want to know: "How does this behave as the data gets bigger?" And: "Is version A better than version B, at which sizes?" And later: "Did my change since last week help?"

Criterion has tools for all three: groups with inputs, throughput, and baselines.

The model (the "what")

• A benchmark group is a named set of related benchmarks. Their results are shown together, with a shared plot.
• A benchmark ID names one run inside a group, like one_acc/100000: a function name and a parameter.
• Throughput tells Criterion how much work one iteration does: Throughput::Elements(n) for n items, or Throughput::Bytes(n) for n bytes. Criterion then reports a rate like "Gelem/s" (billions of elements per second) next to the time. Rates make runs of different sizes comparable: 100 ns for 1,000 items and 12 µs for 100,000 items look very different as times, but both are about 8 to 9 billion items per second.
• A baseline is a saved set of results with a name. You can save one (--save-baseline name) and compare a later run against it (--baseline name). Without names, Criterion compares with the last run. Named baselines let you keep a "before my change" reference for as long as you want.

Build it (the "how")

We compare two ways to sum numbers, at three sizes. The first, one_acc, is the plain loop. The second, multi_acc, uses four separate running totals (accumulators), so four additions can happen side by side.

Create benches/groups.rs (and add a second [[bench]] entry named groups with harness = false to Cargo.toml):

use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion, Throughput};
use std::hint::black_box;
use std::time::Duration;

fn one_acc(m: &[u64]) -> u64 {
    let mut s = 0u64;
    for v in m { s = s.wrapping_add(*v); }
    s
}

fn multi_acc(m: &[u64]) -> u64 {
    let (mut a, mut b, mut c, mut d) = (0u64, 0u64, 0u64, 0u64);
    for ch in m.chunks_exact(4) {
        a = a.wrapping_add(ch[0]);
        b = b.wrapping_add(ch[1]);
        c = c.wrapping_add(ch[2]);
        d = d.wrapping_add(ch[3]);
    }
    a.wrapping_add(b).wrapping_add(c).wrapping_add(d)
}

fn bench_sums(c: &mut Criterion) {
    let mut group = c.benchmark_group("sum");
    group.warm_up_time(Duration::from_secs(1));
    group.measurement_time(Duration::from_secs(2));
    for &n in &[1_000usize, 100_000, 4_000_000] {
        let data: Vec<u64> = (0..n as u64).collect();
        group.throughput(Throughput::Elements(n as u64));
        group.bench_with_input(BenchmarkId::new("one_acc", n), &data, |b, d| {
            b.iter(|| one_acc(black_box(d)))
        });
        group.bench_with_input(BenchmarkId::new("multi_acc", n), &data, |b, d| {
            b.iter(|| multi_acc(black_box(d)))
        });
    }
    group.finish();
}

criterion_group!(benches, bench_sums);
criterion_main!(benches);

New pieces: benchmark_group makes the group. bench_with_input passes the data as an input, so the same code runs for each size. BenchmarkId::new("name", n) builds the ID. group.throughput(...) must be set before the benchmarks it applies to.

Run and save the result as a baseline named before:

cargo bench --bench groups -- --save-baseline before

Here is what I got (the time line and the rate line for each):

Read the table like a detective.

At 1,000 numbers, the four-accumulator version is about 29% faster. The data is tiny (8 KB), so it sits in the L1 cache, and the loop is limited by how fast it can do the additions.

At 100,000 and 4,000,000 numbers, the two are tied. The trick does nothing. Let's do some math: 8.3 billion numbers per second × 8 bytes each is about 66 GB/s at 100,000 numbers. At 4 million, 3.6 billion × 8 is about 29 GB/s. In both cases, the data arrives from the cache or memory at some rate, and the loop does not even need to be fast, because it spends its time waiting for data. When the loop is waiting for memory, making the adding faster changes nothing. (This is the Chapter 8 lesson in action. Treat these GB/s numbers as rough, because the machine is a shared VM.)

So the same trick helps at one size and does nothing at two others. If you had benchmarked only 1,000 numbers, you would have called multi_acc a 29% win. If you had benchmarked only 4 million, you would have called it useless. Both are true, at different sizes. This is why we use groups with several inputs.

One more surprise. I expected the plain loop to be slow here, and it wasn't. At 100,000 numbers, it moves data about as fast as the four-accumulator version. I think the compiler already turned the plain integer loop into wide instructions, since adding integers in any order gives the same answer, so the compiler is allowed to reorder. But I did not read the machine code to check that. (With floating-point numbers, the order does change the answer slightly, so the compiler may not reorder them, and the multi-accumulator trick pays off much more. Chapters 13 and 28 return to this.)

Baselines: compare against a saved result

Now I changed multi_acc to use eight accumulators and compared with the baseline before:

cargo bench --bench groups -- --baseline before

sum/one_acc/1000        time:   [111.54 ns 112.59 ns 113.96 ns]
                 change:  Performance has regressed.
sum/multi_acc/1000      time:   [66.837 ns 67.023 ns 67.207 ns]
                 change:  Performance has improved.
sum/one_acc/100000      time:   [12.073 µs 12.116 µs 12.164 µs]
                 change:  Change within noise threshold.
sum/multi_acc/100000    time:   [12.380 µs 12.587 µs 12.842 µs]
                 change:  Change within noise threshold.
sum/one_acc/4000000     time:   [1.1095 ms 1.1206 ms 1.1324 ms]
                 change:  Change within noise threshold.
sum/multi_acc/4000000   time:   [1.0726 ms 1.0905 ms 1.1087 ms]
                 change:  No change in performance detected.

(I removed the numeric percent lines to keep this short. The verdicts are exactly as printed.)

Look at what happened:

• multi_acc/1000 improved: from 76.7 ns to 67.0 ns, about 12.6% faster. That is the change I made, and it shows up where the loop was limited by additions.
• multi_acc at the big sizes: no change. As before, memory is the limit there.
• Now look at one_acc/1000. I did not touch that function. Yet Criterion says "Performance has regressed". The time moved from 107.8 ns to 112.6 ns, about 4.4% slower, and the whole interval landed beyond the threshold.

This is a false alarm, on a real machine, with unchanged code. It is the same effect as Run 3 in Chapter 6, but bigger this time. A tool with a 1% threshold can't tell a 4% wobble from a real change if the wobble happens to be steady during the whole run. How would you know it was a false alarm? Because you know you did not change the function. That is the point: a flagged regression is a question, not an answer. The next step is to ask "what changed?" and to re-run.

Provenance: remember where the number came from

A number saved in a baseline is only useful if you know where it came from. When you save a baseline or share a result, also write down:

• the Rust version (rustc --version) and Criterion version,
• the CPU model and whether the machine was idle,
• the commit of the code,
• the exact command used.

Provenance just means "where the data came from". Without it, three weeks later, nobody can tell why this month's number is different.

Why it is this way (the "why")

Why does the same trick help at one size and not at another? Because speed is limited by the slowest part in the chain, and which part is slowest depends on the size of the data.

Think of a kitchen. A fast cook (the CPU) and a slow delivery of ingredients (memory). If the ingredients are right on the counter (tiny data in L1), the cook's speed is the limit, so a faster cook helps. If the ingredients come from a far warehouse (big data), the delivery is the limit, and hiring a faster cook changes nothing. The analogy breaks in one place: a real kitchen cannot start preparing the next ingredient before the last one arrives, but a real CPU can, up to a point. (It can look ahead and fetch early. We study that in Chapter 12.)

This gives a general principle: before you optimize, find the limit. Is it the arithmetic (compute-bound), or the data arriving (memory-bound)? An optimization for the wrong limit is wasted effort. The tool for finding this is the throughput number plus the size sweep. We will make this precise with the roofline model in Chapter 19.

And the philosophy of baselines: a performance claim needs a reference. "It is 12 µs" means little. "It is 12.6% faster than the version from last Tuesday, measured the same way on the same machine" is a claim someone can check. A baseline turns a number into a comparison, and comparisons are what we use to decide.

What would make this wrong? Benchmarking at three sizes is still a sample of the real range of sizes. And the cache is warm in all these tests. If real use always begins cold, the table could look different.

Common mistakes

• One size only. You cannot see where behaviour changes.
• Forgetting group.throughput before the benchmark. The rate lines will not appear (or apply to the wrong ones).
• Reading a flagged regression on code you did not touch as a real regression. Check what changed, and re-run.
• Saving a baseline and forgetting its context. Write down the machine, the versions, and the commit.
• Comparing a baseline across Rust versions or machines. The compiler and the CPU are part of the measurement.
• Judging a trick at one size. It may help at one size and do nothing at another.

Say it simply

A benchmark group runs the same test over many inputs and shows them together. Throughput turns "time per call" into "items per second", so different sizes can be compared. A named baseline saves a result so you can compare a later run against it. Our summing trick was 29% faster at 1,000 numbers and did nothing at 100,000 or 4 million, because at large sizes the loop waits for data. A flagged regression on code you did not change is a false alarm, so always ask what really changed.

Check yourself

Exercise 7.1 (Warm-up): Predict, then check. You sum 10,000 u64 numbers (80 KB) and 400,000 u64 numbers (3.2 MB) on a CPU with a 48 KB L1 and a 2 MB L2. Before running, predict whether the four-accumulator trick helps more at 10,000 or at 400,000, and why. Then run it.

Exercise 7.2 (Warm-up): Rates. A function takes 12.0 µs for 100,000 u64 numbers. What is the throughput in billions of elements per second? In GB/s? Show the math.

Exercise 7.3 (Core): Add a third size. Add 16,000 and 1,000,000 elements to the group. Draw the throughput against size. Where are the steps? Do they match your CPU's cache sizes (lscpu)? (Chapter 8 explains the steps.)

Exercise 7.4 (Core): Baseline discipline. Save a baseline, change one function, compare. Then run the comparison again without changing anything. Did the verdicts stay the same? Which ones moved? Report how many "verdict flips" you saw across 3 repeated comparisons.

Exercise 7.5 (Core): Floats vs integers. Write the same two benchmarks for f64 (sum with one accumulator and with four). Does the four-accumulator version help at the large sizes too? Why might the integer and float cases differ? (Check the machine code for the plain loop in both cases if you can: cargo rustc --release -- --emit asm.) Hint: floating-point addition is not associative. (a + b) + c may differ from a + (b + c) in the last digits.

Exercise 7.6 (Stretch): Find the false-alarm rate. Write a script that runs the unchanged group benchmark 20 times against the same baseline, and counts how many of the 6 benchmarks per run got "regressed" or "improved". What was the false-alarm rate on your machine?

Exercise 7.7 (Stretch): Design and defend. You are comparing two string-search algorithms. List the groups, inputs, and rates (items or bytes per second) you would use, and what you would write down as provenance. Explain what result would make you pick algorithm A, and what would make you pick B.

What a strong answer includes: several text sizes and several pattern lengths, hit-heavy and miss-heavy inputs, bytes-per-second as the rate, sizes that cross the cache boundaries, the Rust and CPU versions, and the idea that the answer may depend on the workload.

Part II wrap-up

What you can now do:

• Set up Criterion, write a benchmark, and read every line of its report.
• Explain the confidence interval, the p-value, and the noise threshold, and give the exact rule Criterion uses for its verdicts.
• Measure your own machine's wobble and use it to judge changes.
• Benchmark the same idea across sizes with groups, inputs, and throughput.
• Save a baseline, compare against it, and write down where a number came from.
• Say why one optimization can help at one size and do nothing at another.

Mini project: The bake-off (3 to 5 hours). Choose two or three versions of a small function you care about (for example, three ways to count bytes equal to a value, or three ways to find the maximum). Using Criterion:

1. Write the question and the workloads first (at least 3 sizes, and 2 shapes of data).
2. Build a group with inputs and throughput.
3. Save a baseline. Run the unchanged code 5 more times and measure your wobble.
4. Make one change to one version. Compare against the baseline and decide, using the rule from Chapter 6, whether the change is real.
5. Run your own Chapter 4 harness on the same functions and compare its numbers with Criterion's.

Done when: a one-page report with a table of times and rates, your measured wobble, one real change and one false alarm (if you saw one), and a provenance block.

Write-up prompt: Half a page. What did you expect, what did you see, and which result did you least trust, and why?

Teach it back: In 5 sentences, explain to a friend why "Performance has regressed" does not always mean you made the code slower.

Reading list for Part II:

• The Criterion.rs user guide and its repository (now at criterion-rs/criterion.rs). The guide explains the analysis steps and every command-line flag. Read "Analysis Process" first. Also read the changelog for the version you use.
• John W. Tukey, Exploratory Data Analysis (1977). The source of the box-plot fences used for outliers. Optional, but short chapters on the idea are rewarding.
• Bradley Efron, "Bootstrap Methods: Another Look at the Jackknife", The Annals of Statistics, 1979. The original bootstrap paper. Read the introduction only.

Verification notes for Part II: Criterion 0.8.2 and rustc 1.91.1 were installed and run in this session on the same 1-core Xeon VM; all benchmark outputs are real. The defaults (100 samples, 3 s warm-up, 5 s measurement, 100,000 re-samples, 0.95 confidence, 0.05 significance, 0.01 noise threshold), the verdict rule, and the 1.5 × IQR outlier fence were read from the Criterion 0.8.2 source code. The minimum Rust version (1.86 for 0.8) comes from the Criterion changelog as shown in search results. The 3 × IQR severe fence, the way Criterion picks batch sizes (growing batches), and the three reading-list items were not checked against fresh sources. Not confirmed: why the plain integer loop matches the four-accumulator loop at large sizes (I think the compiler vectorizes it, but I did not read the machine code), and the exact cause of the 4.4% drift on the unchanged one_acc/1000 benchmark.

Part III. The machine: memory and the CPU

After this Part, you will be able to look at a loop and say, before running it, which rung of the memory ladder it will sit on, how many cache lines it touches, and whether the CPU can guess what it wants next.

Part I taught you to measure. Part II gave you a tool. Now we open the machine, because every surprising number so far (the 8x gap in a sum, the 4% wobble at 1,000 numbers, the trick that helped at one size and not at another) has its cause here.

The plain programs in this Part were compiled with rustc 1.75 and -C opt-level=3, and run on the 1-core Xeon VM described at the start. Your numbers will differ. The shapes should not.

Chapter 8. Memory is not a box. It is a ladder.

In this chapter: You will learn why the same line of code can take 1.7 nanoseconds or 137 nanoseconds, depending only on where its data lives. You will build a small tool that finds the cache sizes of your own machine, by measuring, and you will measure both latency and bandwidth.

You need first: Part I.

The problem first

Take two loops. Both add up numbers. Both do the same math. One finishes in 3 milliseconds. The other takes 16 milliseconds. Same machine, same compiler, same count of additions.

What is different is how far the data had to travel before the CPU could use it.

Most of us learn that memory is one big box. You ask for an address, you get a value, and all addresses cost the same. This is a good lie for writing correct programs. It is a bad lie for writing fast ones. Memory is a ladder, and every rung down costs much more time.

The model (the "what")

A picture first: the desk, the shelf, and the library

Think of a person studying at a desk. The books on the desk are right there: grab and read. The books on the shelf in the room take a few seconds. The books in the library across town take an hour. A smart student keeps the books they need now on the desk.

Your CPU is the same. It has a few very fast, very small places to keep data close, and one huge, slow place far away.

Where does the analogy break? A student picks one book at a time. A CPU never picks one value at a time. It brings a whole chunk at once. We meet that chunk in Chapter 9.

The real ladder

A cache is a small, fast memory that keeps copies of recently used data, so the CPU does not need to go to the slow memory again.

 fastest, smallest                                   slowest, biggest
 ┌───────────┐  ┌───────────┐  ┌───────────┐  ┌───────────┐  ┌───────────────┐
 │ Registers │→ │  L1 cache │→ │  L2 cache │→ │  L3 cache │→ │  Main memory  │
 │ (inside   │  │ tens of   │  │ ~ MiB     │  │ many MiB, │  │  (RAM)        │
 │  the CPU) │  │ KiB       │  │           │  │ shared    │  │  GiB          │
 └───────────┘  └───────────┘  └───────────┘  └───────────┘  └───────────────┘
   ~0 ns          ~1-2 ns        ~4-7 ns        ~15-50 ns       ~100+ ns

Look at the bottom row of numbers. They are real times measured on the machine used here. Each step down is slower, and the jump to main memory is the biggest.

Two words that people mix up:

• Latency is how long you wait for one piece of data after you ask.
• Bandwidth is how much data flows per second once things are moving.

Latency is "how long for the first drop of water to arrive". Bandwidth is "how wide the pipe is". A pipe can be very wide and very long at the same time.

A third word: the working set is the amount of data your code is actively using at one time. If it fits in L1, the code is fast. If it fits in L2 but not L1, a bit slower. And so on down the ladder. Speed depends on the working set, not only on the instruction count.

Build it (the "how")

Experiment 1: measure latency with pointer chasing

Make an array where every slot holds the index of the next slot to visit, arranged as one big loop in random order. Follow the chain for millions of steps. Each step needs the answer from the step before, so the CPU cannot guess ahead. The time per step is the latency of whichever rung holds the data.

Random order matters. If the order were 0, 1, 2, ..., the CPU would notice the pattern and fetch ahead. That feature is called the prefetcher, and Chapter 12 explains it. Random order defeats it, so we see the true latency.

use std::hint::black_box;
use std::time::Instant;

fn next(state: &mut u64) -> u64 {
    let mut x = *state;
    x ^= x << 13; x ^= x >> 7; x ^= x << 17;
    *state = x;
    x
}

// One big loop that visits every slot exactly once, in random order (Sattolo's algorithm).
fn build_cycle(slots: usize) -> Vec<usize> {
    let mut next_slot: Vec<usize> = (0..slots).collect();
    let mut rng = 0x9E3779B97F4A7C15u64;
    for i in (1..slots).rev() {
        let j = (next(&mut rng) as usize) % i; // j in 0..i, never i itself
        next_slot.swap(i, j);
    }
    next_slot
}

fn chase(cycle: &[usize], steps: usize) -> usize {
    let mut at = 0usize;
    for _ in 0..steps { at = cycle[at]; } // the next address depends on this load
    at
}

fn main() {
    println!("{:>12} {:>10}", "bytes", "ns/step");
    let mut size = 4 * 1024usize;
    while size <= 256 * 1024 * 1024 {
        let slots = size / std::mem::size_of::<usize>();
        let cycle = build_cycle(slots);
        let steps = 20_000_000usize;
        black_box(chase(&cycle, slots.min(steps))); // warm up: map the pages
        let mut best = f64::MAX;
        for _ in 0..5 {
            let t = Instant::now();
            black_box(chase(black_box(&cycle), steps));
            best = best.min(t.elapsed().as_nanos() as f64 / steps as f64);
        }
        println!("{:>12} {:>10.2}", size, best);
        size *= 2;
    }
}

Why Sattolo's algorithm and not a plain shuffle? A plain shuffle can create several small loops. Then the chase could get stuck going around a tiny loop that fits in L1 and we would measure the wrong rung. Sattolo's algorithm always makes one loop through all slots.

Result:

       bytes    ns/step
        4096       1.73
        8192       1.71
       16384       1.74
       32768       1.72      <- still L1
       65536       2.85      <- the first step up
      131072       4.22
      262144       4.76
      524288       5.69
     1048576       6.95      <- L2 range
     2097152      15.11      <- the second step up
     4194304      23.60
     8388608      31.54
    16777216      46.23
    33554432     108.84      <- the big step: main memory
    67108864     125.15
   134217728     133.40
   268435456     137.46

It is not a smooth curve. It is a staircase. Each flat part is one rung. Each jump is the moment the data stopped fitting.

Now compare with what the machine says about itself (lscpu | grep -E 'L1d|L2|L3'): L1d 48 KiB, L2 2 MiB, L3 260 MiB.

• L1: flat at about 1.7 ns up to 32 KiB, and it rises at 64 KiB. That matches a 48 KiB L1.
• L2: the second jump comes right at 2 MiB. That matches the 2 MiB L2.
• L3: here the report and the measurement disagree. The report says 260 MiB. But times reach main-memory levels at about 32 MiB. I could not confirm why. Two likely reasons: in a cloud VM, the L3 is shared with other users, so we only get a slice; and at large sizes the CPU also pays to translate addresses (Chapter 10). Both may play a part.

The lesson: what a machine reports and what you measure can disagree, and the measurement tells you how your program will behave.

Experiment 2: measure bandwidth with a sequential sum

Now the other side: how fast can data stream when the access pattern is easy? Sum a big array in order, at growing sizes, and compute gigabytes per second.

use std::hint::black_box;
use std::time::Instant;

fn main() {
    println!("{:>12} {:>10}", "bytes", "GB/s");
    let mut size = 16 * 1024usize;
    while size <= 256 * 1024 * 1024 {
        let n = size / 8;
        let v: Vec<u64> = (0..n as u64).collect();
        let reps = (512 * 1024 * 1024 / size).max(2); // about 512 MiB read in total
        let mut best = 0.0f64;
        for _ in 0..4 {
            let t = Instant::now();
            let mut s = 0u64;
            for _ in 0..reps { for x in black_box(&v) { s = s.wrapping_add(*x); } }
            black_box(s);
            best = best.max((size * reps) as f64 / t.elapsed().as_secs_f64() / 1e9);
        }
        println!("{:>12} {:>10.1}", size, best);
        size *= 4;
    }
}

       bytes       GB/s
       16384       70.2
       65536       66.2
      262144       66.6
     1048576       66.5
     4194304       29.2
    16777216       28.1
    67108864       28.6
   268435456        9.9

Same staircase, upside down. Bandwidth is about 66 GB/s while the data sits in L1 or L2 (up to 1 MiB here), drops to about 28 GB/s from 4 MiB to 64 MiB (the L3 range on this VM), and drops to about 10 GB/s at 256 MiB, which is main memory.

Compare the two experiments at 256 MiB. Latency was 137 ns per dependent access. Yet a sequential sum moves data at 10 GB/s, which is about 0.8 ns per 8-byte number. That is a 170x difference. The same memory, the same machine. The difference is the pattern: when the CPU knows what comes next, it can fetch many lines at once, and the long latency is hidden. Chapter 12 explains how.

Why it is this way (the "why")

Why does the ladder exist? Because of a trade-off you can never escape. Memory can be big, fast, or cheap: pick two. Fast memory (like L1) takes a lot of chip area and power per byte. Big memory (like RAM) must be dense and cheap. So designers build a ladder, and each rung gives the CPU the feeling of a big fast memory, as long as the program has good locality.

The philosophy to carry: the cache is a bet. The hardware bets that the future looks like the recent past. When the bet wins, your program flies. When it loses, you wait.

Three questions work for almost any performance problem:

1. How big is my working set right now? Which rung does it fit on?
2. How much of each cache line I carry do I actually use? (Chapter 9.)
3. Can the hardware guess what I will want next? (Chapter 12.)

And the harder question: what would make this model wrong? The staircase assumes a simple "keep the recent stuff" store. Real caches have more rules (Chapter 9 shows one that bites), and a VM adds its own noise. A model is a tool. Know where it stops.

The idea also shows up outside the CPU. A web cache, a database buffer pool, and a CDN are the same bet, one rung up. Once you see the ladder, you will see it everywhere.

Common mistakes

• Trusting the instruction count. "It's O(n), so it's fast." Big-O does not see the ladder.
• Benchmarking only a tiny input. If it fits in L1, you measured the best case.
• Believing the reported cache size without measuring. Shared machines disagree with their own reports.
• Mixing latency and bandwidth. A dependent chain measures latency. A streaming sum measures bandwidth. A real program is usually in between.
• Letting the chase loop turn into small cycles. Use a single-cycle shuffle.

Say it simply

Memory is a ladder, not a box. The top rungs are tiny and fast, and the bottom rung is huge and slow. Latency is the wait for one item, and bandwidth is how fast data can stream. You can see the ladder yourself by timing a chain of random reads as the data grows, which gives a staircase of latencies. A streaming sum gives the upside-down staircase of bandwidths.

Check yourself

Exercise 8.1 (Warm-up): Predict, then check. Your CPU has a 32 KiB L1 and a 1 MiB L2. Sketch the staircase you expect from the pointer-chasing test: where are the jumps? Then run it and compare. Where were you wrong?

Exercise 8.2 (Warm-up): Explain. In 5 sentences, explain to a friend the difference between latency and bandwidth, with an analogy that is not water pipes.

Exercise 8.3 (Warm-up): Convert. The sequential sum moved 10 GB/s at 256 MiB. How many nanoseconds is that per 8-byte number? How does this compare with the 137 ns per dependent access?

Exercise 8.4 (Core): Find your own ladder. Run both experiments on your machine. Mark where each jump happens. Compare against lscpu (or sysctl hw.cachesize on macOS). Write down one place where the report and the measurement disagree, and give your best guess why. Done when: a table of your own numbers and a short written comparison.

Exercise 8.5 (Core): Break the single cycle. Replace Sattolo's algorithm with a plain shuffle (use j in 0..=i). Run it at 1 MiB and at 256 MiB. What happens, and why? How could you detect that the chase fell into a short loop?

Exercise 8.6 (Stretch): Two threads on one chip. Run the chase on two threads at the same time, each with its own 8 MiB array. Does the latency per step change compared with one thread? What does this say about the L3?

Exercise 8.7 (Stretch): Design and defend. You are building an interpreter whose hot data is a table of 50,000 entries of 40 bytes each. Where does it sit on the ladder? What would you change if the table grew to 5 million entries?

What a strong answer includes: the working set size (2 MB for the first, 200 MB for the second), the rung each lands on, and a design response such as a smaller entry size, splitting hot and cold fields, or a cache-friendlier structure.

Chapter 9. Cache lines, the write path, and locality

In this chapter: You will learn the single most important fact about memory speed: data moves in 64-byte chunks. You will measure it, see what happens when you ignore it (a 16x slowdown from walking a matrix the wrong way), and learn why a perfectly "random" access can still fight itself inside the cache.

You need first: Chapter 8.

The problem first

Here are two ways to add up every number in a 4096 by 4096 matrix of u32 values. Both read every number once. Both do the same additions.

On this machine, one takes 9.4 ms and the other takes 152.8 ms. The second is 16.2 times slower.

The only difference: which direction you walk.

The model (the "what")

The cache line

Memory does not move one byte at a time. It moves in fixed-size chunks called cache lines. On almost every modern x86-64 chip, a cache line is 64 bytes. (Some Arm chips use 128 bytes in places. Always check your own machine.)

When your code reads one byte, the CPU brings the whole 64-byte line that contains it. The other 63 bytes come along for free.

• If your next read is inside the same line, it is nearly free. You already have it.
• If your next read is in a different line, you pay again.

Think of a library that lets you borrow only whole boxes of 64 books. If you needed one book, you still carry the box. So you had better need the other 63 books too.

Where does a line start? Lines are aligned: a line always starts at an address that is a multiple of 64. Alignment just means "the address is a multiple of some number". So an 8-byte number at address 120 sits in the line that begins at 64 (bytes 64 to 127), and bytes 120 to 127 are the end of that line. A number that starts at address 124 and is 8 bytes long would straddle two lines (bytes 124 to 131), which costs two line fetches.

 address:   0                 64                128               192
            ├──────────────────┼──────────────────┼─────────────────┤
            │     line 0       │      line 1      │     line 2      │
            └──────────────────┴──────────────────┴─────────────────┘
                                          ▲▲▲▲
                                an 8-byte value starting at 124
                                touches line 1 AND line 2

Two kinds of "nearby"

Fast programs get help from two habits. Both have names you will hear in talks:

• Temporal locality: if you used something just now, you will probably use it again soon. So the cache keeps it.
• Spatial locality: if you used something at an address, you will probably use the addresses next to it soon. So the cache brings the whole line.

Locality means "the data you use is close together, in time or in space".

How a cache finds a line: sets and ways

A cache is not one big pile. It is organized so that finding a line is fast. Here is the plan:

• The cache is split into many sets.
• Each address belongs to exactly one set, decided by some bits of the address.
• Each set holds a small number of lines, called its ways. (A "12-way" cache holds 12 lines per set.)
• A line can live in any of the ways of its own set, and nowhere else.

This is called a set-associative cache. A picture, for a tiny cache with 4 sets and 2 ways:

            way 0        way 1
  set 0   [ line A ]   [ line E ]
  set 1   [ line B ]   [ line F ]
  set 2   [ line C ]   [ empty  ]
  set 3   [ line D ]   [ line G ]

Which set does an address use? Take the address, throw away the lowest 6 bits (those pick the byte inside the 64-byte line), and use the next few bits as the set number. For a 48 KiB, 12-way L1 with 64-byte lines, there are 48 KiB / (64 B × 12) = 64 sets, so 6 bits pick the set: address bits 6 to 11. That means addresses exactly 4096 bytes apart land in the same set.

If many of your hot lines land in the same set, they fight for those few ways. A line gets thrown out even while the rest of the cache is empty. This is a conflict miss. A miss is when the data you want is not in the cache and must be fetched from further down.

The write path

So far we only read. What happens on a write? The CPU can only change data that sits in its cache. So when you write to a line that is not in L1, the CPU must first fetch that line (this is called write-allocate), then change it. The changed line is marked dirty. A dirty line must be written back to the level below when it is thrown out, which costs bandwidth later.

This has a surprising cost: writing 1 byte to cold memory causes a 64-byte read, and later a 64-byte write. A loop that only writes still reads. I did not measure this in this chapter. Exercise 9.6 asks you to. The idea comes from standard computer-architecture textbooks and from Ulrich Drepper's long paper on memory (reading list).

Build it (the "how")

Experiment 1: find the cache line size by striding

Make a 64 MiB array of u32. Add 1 to every stride-th element, and measure the time for one pass. When the stride is small, many reads share a line. When the stride gets large, every access touches a new line.

let n = 16 * 1024 * 1024;           // 16M u32 = 64 MiB
let mut v = vec![1u32; n];
for &stride in &[1usize, 2, 4, 8, 16, 32, 64, 128, 256] {
    // time one pass of: v[i] += 1 for i in (0..n).step_by(stride)
}

  stride  bytes apart    touched  ms per pass
       1            4   16777216        14.69
       2            8    8388608        12.22
       4           16    4194304         9.96
       8           32    2097152         2.92
      16           64    1048576         2.74
      32          128     524288         2.94
      64          256     262144         1.53
     128          512     131072         0.77
     256         1024      65536         0.37

What to notice, from the bottom up:

• Strides 64, 128, 256 (256 bytes or more apart): each doubling of the stride halves the time. Every access touches a brand-new line, so the time is proportional to the number of accesses. That is the signature of "one line per access".
• Strides 8, 16, 32 (32 to 128 bytes apart): the time is almost flat at about 2.8 ms, even though we touch half as many elements each time. Why? Because the number of lines fetched did not change much. With a 32-byte stride, two accesses share one 64-byte line. At 64 bytes, every access is a new line. The flat part is the machine hauling in the same lines.
• Strides 1, 2, 4: much slower (14.7 ms at stride 1) even though the number of lines fetched is the same. Here the time is the cost of the instructions: 16 million loads, adds, and stores, not memory. These strides are limited by the instruction count, not the cache. This is a reminder that a loop can be limited by different things at different sizes (Chapter 7).

One result surprised me. With a 64-byte stride we touch one line per access, and with a 128-byte stride we touch every other line. I expected the time to halve from 2.74 ms to about 1.4 ms. It stayed at 2.94 ms. It only halved at 256 bytes. I did not confirm the reason. A likely cause is a hardware feature that fetches the neighbor line along with the requested one (many Intel chips do something like this, often called an adjacent-line prefetch), so the machine effectively moves 128-byte pairs. If that is true, "the unit that matters is 64 bytes" is a good rule, and "sometimes 128" is the fine print. Exercise 9.5 asks you to test it.

Experiment 2: walk a matrix two ways

A matrix in Rust is stored row by row: element (r, c) lives at index r * n + c. This is called row-major order. So elements in the same row are neighbors in memory, and elements in the same column are n * 4 bytes apart.

let n = 4096usize;                       // 4096 x 4096 u32 = 64 MiB
let m: Vec<u32> = (0..(n * n) as u32).collect();

// Way 1: row by row. Inner loop moves along memory.
for r in 0..n { for c in 0..n { s += m[r * n + c] as u64; } }

// Way 2: column by column. Inner loop jumps 16,384 bytes each step.
for c in 0..n { for r in 0..n { s += m[r * n + c] as u64; } }

row by row       :     9.42 ms
column by column :   152.79 ms  (16.2x slower)

Row by row uses every byte of every line: 16 numbers per line, all useful. Column by column uses one number per line (the other 15 in the line are not used until much later, and by then the line is gone). And that is not the only problem. A jump of 4096 × 4 = 16,384 bytes is a multiple of 4096, so every step lands in the same cache set (that is the conflict miss from above). It also lands in a new memory page every time, which we study in Chapter 10. I did not separate these three causes in this run. A matrix that is exactly 4096 wide is the worst case. Exercise 9.4 asks you to see how much a width of 4097 helps.

Experiment 3: watch the cache fight itself

Now let's see the set conflict directly. Visit k cache lines in a random loop (a pointer chase, as in Chapter 8). In one test the lines are exactly 4096 bytes apart, so they all fall in the same L1 set. In the other, they are 4160 bytes apart (4096 plus one line), so they spread across different sets.

 lines    gap 4096 (ns)    gap 4160 (ns)
     4             1.77             1.78
     8             1.77             1.77
    10             1.76             1.76
    12             2.42             1.76
    14             5.66             1.77
    16             5.67             1.76
    24             5.65             1.80
    32             5.19             1.77
    64             5.67             1.77

In the second column, everything is L1-speed (1.77 ns) all the way to 64 lines. The cache has room: 64 lines is only 4 KiB. In the first column, the time jumps as soon as we go past about 12 lines. Only 12 lines! That is a tiny working set (768 bytes), yet it behaves like data that does not fit in L1.

The reason is the L1's 12 ways per set (from lscpu: 48 KiB, and my calculation of 64 sets). Thirteen lines that all map to one set cannot all stay. Each new one evicts another. The time (5.7 ns) is about the L2 latency from Chapter 8: the lines keep falling out of L1 and coming back from L2. (The 12-way number is my reading of a 48 KiB L1 plus the jump at 12 to 14 lines. I did not look up the chip's manual.)

So: a working set can fail to fit, not because it is big, but because of where its addresses fall. This is why power-of-two sizes are dangerous. Arrays or matrix rows whose size is a large power of two put neighbors in the same set. This is one reason performance code sometimes pads rows (makes each row a little longer) on purpose.

Why it is this way (the "why")

Why 64 bytes? Because it is a trade-off. A bigger line brings more neighbors for free (good for spatial locality) but wastes bandwidth when you only needed a little, and makes the cache hold fewer distinct lines. A smaller line wastes less, but needs more fetches and more bookkeeping for the same data. Chip designers tried many sizes. 64 bytes has been the sweet spot on x86 for a long time.

Why sets and ways instead of "any line anywhere"? Because of speed and cost. A cache where any line can go anywhere (fully associative) would need to compare the address against every line at once. That takes a lot of hardware and power. A cache where each line has exactly one possible place (direct-mapped) is fast and cheap, but two hot lines that share a place keep throwing each other out. Set-associative is the compromise: a few places per address.

The philosophy: every clever hardware idea is a bet on a pattern. Lines bet on spatial locality. Sets and ways bet that addresses spread out evenly. When your data breaks the bet (a stride of exactly 4096, one useful number per line), the hardware gives you its worst case.

This gives you a rule of thumb for any loop: count the cache lines touched, not the elements. Two loops with the same number of elements can touch 16 times as many lines.

What would make this wrong? Hardware is not the same everywhere. Some chips use a hashed set index (so a stride of 4096 does not always collide), some have different line sizes, and virtual machines hide details. Our results hold on this machine. Always re-measure.

Common mistakes

• Walking a 2D array against its storage order. Check which index changes fastest in memory.
• Counting elements, not lines. One useful field per line is a bandwidth leak.
• Using sizes that are large powers of two for strides, row lengths, or buffer sizes in hot loops.
• Ignoring the write cost. Writes to cold memory read the line first.
• Assuming the line is 64 bytes everywhere. Check.
• Mixing up "does not fit" with "is big". A working set can fail to fit because of where it lives.

Say it simply

Memory moves in 64-byte cache lines, so reading one byte brings its 63 neighbors for free, and a program is fast when it uses all of them. A cache is made of sets, and each address can live in only one set, so lots of hot lines that share a set push each other out even when the cache is mostly empty. Writing to cold memory first reads the line. Walking a matrix against its storage order can be 16 times slower, with the same number of additions.

Check yourself

Exercise 9.1 (Warm-up): Count the lines. A struct is 24 bytes and you store 1000 of them in an array that starts at a 64-byte-aligned address. How many cache lines does the array cover? How many structs straddle two lines? Draw the first three lines on paper.

Exercise 9.2 (Warm-up): Which set? An L1 cache has 64 sets and 64-byte lines. Which set does address 0x12345 belong to? Which address, 4096 bytes later, is in the same set? Show the bit math.

Exercise 9.3 (Warm-up): Predict. You sum a Vec<u8> of 100 million bytes in order. How many cache lines are fetched? If the data comes at 10 GB/s, about how long does it take?

Exercise 9.4 (Core): Fix the matrix. Run the row-vs-column test. Then change the width to 4097 (and index with r * 4097 + c) and run the column walk again. How much faster is it? What does this tell you about conflict misses versus plain locality? Done when: a table with widths 4096 and 4097 for both walk orders, and 4 sentences of explanation.

Exercise 9.5 (Core): Test the neighbor-line guess. In the stride experiment, add strides of 48, 80, and 96 elements, and re-run. Try the stride test with the data being touched in a random order of lines instead of a fixed stride. If the "adjacent line" idea is right, what should change? Hint: use the pointer-chase idea so the order is random.

Exercise 9.6 (Core): Measure the write cost. Write two loops over a 256 MiB array: one that only writes (v[i] = 1) and one that reads and writes (v[i] += 1). Compare the times. Then compare with the sum loop from Chapter 8. Do the writes cost more than reads? (Beware that the compiler might turn the write-only loop into a memset. How can you check?)

Exercise 9.7 (Stretch): Find the ways. Using the set-conflict experiment, find the associativity of your own L1 and L2 by changing the gap (for example 4096, 32768, and 262144 bytes) and the number of lines. What numbers do you get? Do they match your CPU's manual?

Exercise 9.8 (Stretch): Design and defend. You write a game where entities are structs, and each frame you update only position. The struct has 12 fields and is 96 bytes. Argue for or against changing the layout. (We return to this in Chapter 11.)

What a strong answer includes: lines touched per entity (96 bytes straddles two lines), the share of bytes used per line, and how the answer changes with the number of entities and with how often the other fields are read.

Chapter 10. Pages, address translation, and the TLB

In this chapter: You will learn that the addresses your program uses are not the real addresses, and that translating them has its own cache. You will measure it: the same number of cache lines can take 1.8 ns or 131 ns per access, depending only on how many different memory pages they touch.

You need first: Chapters 8 and 9.

The problem first

In Chapter 9, we put the lines in a pointer chase and found jumps at the cache sizes. But a puzzle was left over. In Chapter 8, the time at 32 MiB was already as slow as main memory, even though the L3 should be much bigger. We guessed "address translation". Now we test the guess.

The model (the "what")

Virtual memory

Your program does not see real memory addresses. It sees virtual addresses. The operating system and the CPU keep a map from virtual addresses to physical addresses (real locations in RAM). This gives each program its own private address space, and lets the system move things around.

Virtual memory is divided into pages, usually 4096 bytes (4 KiB). The map works one page at a time. (You can check with getconf PAGESIZE. It printed 4096 here.)

An address is split in two parts:

 virtual address:  [ page number | offset inside the page ]
                     (upper bits)   (lowest 12 bits for a 4 KiB page)
                          │
                          ▼  look up in the page table
 physical address: [ frame number | same offset ]

The map is stored in page tables, which are themselves in memory. On x86-64 they form a tree four levels deep. To translate one address, the CPU may have to walk four levels, each one a memory read. That is called a page walk. If each walk step missed the cache, a single load would cost five memory trips.

The TLB

To avoid this, the CPU keeps a small cache of recent translations. It is called the translation lookaside buffer (TLB). A TLB entry says "virtual page X is at physical frame Y".

• A TLB hit: the translation is already there. Almost free.
• A TLB miss: the CPU must do a page walk. Costly.

The TLB is small, often in two levels. A typical first-level TLB holds on the order of 64 entries, and the second level on the order of a thousand or two. One entry covers one page (4 KiB). So a first-level TLB with 64 entries covers only 64 × 4 KiB = 256 KiB of memory at a time. The second level might cover a few megabytes. (These sizes vary by chip. I did not look up the chip behind this VM. We measure instead.)

This is another rung of the ladder, but a different kind: instead of caching data, the TLB caches the map.

Huge pages

If you use bigger pages, each TLB entry covers more memory. On Linux, x86-64 supports 2 MiB (and 1 GiB) pages, called huge pages. A 64-entry TLB with 2 MiB pages covers 128 MiB instead of 256 KiB. The cost: memory is handed out in bigger pieces, which can waste space, and the setup is more involved. Linux can use huge pages automatically in some modes (transparent huge pages). On this VM the setting was always [madvise] never, which means "only if the program asks".

Build it (the "how")

We want to separate the TLB from the data cache. The trick: do two pointer-chase tests with the same number of cache lines, but arranged differently.

• Packed: the lines are side by side in memory. 64 lines fit in 4 KiB, so very few pages are touched.
• Spread: one line per 4 KiB page, and the line offset inside each page changes from page to page (so the lines don't all pile into one cache set). Now every line is on a different page.

Both tests have the same number of lines to fetch. Only the number of pages differs.

// `spread`: line i lives in page i, at an offset that changes with i.
// `packed`: the same lines, side by side.
let words_per_page = 4096 / 8;
let line_words = 8; // 64 bytes
let pos = |i: usize| -> usize {
    if spread { i * words_per_page + (i % 64) * line_words }
    else      { i * line_words }
};
// each line's first word holds the position of the next line in a random loop

   lines    packed ns    spread ns
      16         1.76         1.77
      32         1.78         1.77
      64         1.77         1.77
     128         1.77         4.25
     256         1.76         4.26
     512         1.78         4.29
    1024         5.63         8.19
    2048         5.70        10.66
    4096         5.68        18.55
    8192         6.29        22.05
   16384         7.55        32.41
   32768        19.37        42.45
   65536        35.53        55.13
  131072        35.93       131.63

Read it column by column.

Packed is a plain cache staircase, like Chapter 8: 1.8 ns while the lines fit in L1 (up to 512 lines, 32 KiB), then about 5.7 ns (L2), then up again near 32,768 lines (2 MiB, the L2 size), then about 36 ns.

Spread is slower in the same places the packed one is fast. Look at 128 lines. In both tests we fetch the same 128 lines: 8 KiB of data, which easily fits in L1. Packed takes 1.77 ns. Spread takes 4.25 ns. The data cache is not the difference, because both fit. The difference is that spread touches 128 different pages, and 128 is more than the first-level TLB can hold (it was fine at 64 pages, 1.77 ns, and not fine at 128). The extra 2.5 ns per access is the cost of a first-level TLB miss that is served by the second-level TLB. This is consistent with a first-level TLB of about 64 entries.

The next step up in the spread column starts at 1024 pages (8.2 ns), and keeps rising. That is where the second-level TLB starts to run out, and the CPU has to do real page walks. The data cache cannot explain this: the spread test still only touches one line per page, so 1,024 lines is just 64 KiB of data.

At the end, 131,072 lines: packed takes 35.9 ns, spread takes 131.6 ns. Both fetch the same 131,072 lines (8 MiB of actual data). The extra ~96 ns per access is the cost of translation: page walks, and the page-table entries themselves falling out of the caches. Remember that we measured in a VM. A VM has two layers of address translation (guest and host), which makes a TLB miss even more costly than on bare metal. So the numbers here are probably worse than on real hardware.

And look back at Chapter 8's puzzle. The chase there used 4 KiB pages too, so at 32 MiB (8,192 pages) it was touching many pages, and part of its 108 ns was page walks. A big part of "the cost of main memory" in that chase was not the memory itself. I haven't separated the two for that exact table, but this experiment shows the size of the effect.

I did not run a huge-page version. The setting here is madvise, so a program has to ask with the madvise system call. Exercise 10.5 asks you to try it. It is a good example of an experiment where the expected answer ("much faster") might not appear on your machine, and finding out why is the lesson.

Why it is this way (the "why")

Why do we need virtual memory at all, if translation is so costly? Because the benefits are huge. Every program gets its own clean address space, programs cannot read each other's memory, memory can be given out in scattered pieces, and the system can move pages to disk. These are some of the most important ideas in operating systems. Translation is the price, and the TLB is how we pay less of it.

Why is the TLB so small? A TLB lookup happens on every memory access, so it must be extremely fast, and fast storage is small (the same trade-off as Chapter 8). It works because of locality again: programs usually stay on a few pages for a while. The TLB is another bet on locality, this time of pages, not lines.

This produces a new way to count: count the pages touched, as well as the lines. A loop that touches one line on each of 100,000 pages is slow even if all the lines are in cache. This is the pattern of:

• a hash table with large entries, accessed randomly,
• a big linked structure whose nodes were allocated at different times,
• a compiler's AST or symbol table that grew over time,
• a database index with huge fan-out.

The honest counter-argument: for many programs, the TLB is not the bottleneck. Our spread test is a worst case on purpose. The point is to know when it matters (many pages, random access, big working set) and to have a way to test it.

What would make this model wrong? Hardware that caches page-walk steps, prefetches translations, or has very large TLBs hides the effect. And huge pages can change everything. As always: measure on your machine.

Common mistakes

• Blaming the cache for what the TLB is doing. A cache-friendly layout can still be page-unfriendly.
• Treating page size as fixed. Huge pages change the answer.
• Benchmarking in a VM and assuming the same numbers on bare metal. TLB misses are costlier in a VM.
• Counting only data size. A big sparse structure costs more than a dense one of the same byte count.

Say it simply

Programs use virtual addresses, and the CPU must translate each one into a physical address using a map made of 4 KiB pages. The TLB is a small cache of those translations, so touching more pages than it can hold makes every access slower, even when the data itself fits in the cache. In our test, the same 128 cache lines took 1.8 ns when packed and 4.3 ns when spread across 128 pages, and a large spread cost 131 ns against 36 ns packed. Count pages touched, not just lines.

Check yourself

Exercise 10.1 (Warm-up): Do the math. A TLB has 64 entries and pages are 4 KiB. How much memory can it cover? How much if the pages are 2 MiB?

Exercise 10.2 (Warm-up): Split an address. Split the virtual address 0x7f12_3456_789A into the page number and the offset, for 4 KiB pages. What changes for 2 MiB pages?

Exercise 10.3 (Core): Run the TLB test. Build and run the packed-versus-spread test. Mark where the spread column departs from the packed column. How many pages is that? Does it match what you know about your CPU's TLB? Done when: your own two-column table and 5 sentences about what you found.

Exercise 10.4 (Core): Page count by structure. For a Vec<Node> of 1 million nodes of 48 bytes each, versus a Vec<Box<Node>> where each box was allocated at a random time, estimate the number of 4 KiB pages touched by a full traversal in each case. Then measure the traversal time of both.

Exercise 10.5 (Stretch): Try huge pages. Allocate 512 MiB with mmap (use the libc crate), call madvise with MADV_HUGEPAGE, and repeat the spread test. Check grep -i huge /proc/meminfo while it runs. Did it help? If not, find out why. Hint: you may need to align the allocation to 2 MiB.

Exercise 10.6 (Stretch): Design and defend. A server keeps 200 million small records in a hash table with random access. A teammate says "enable huge pages" and another says "shrink the records". Argue which comes first, and what you would measure before and after.

What a strong answer includes: pages touched per lookup, TLB reach (entries times page size), the cost of a miss in a VM, memory waste from huge pages, and the idea of testing both changes in a controlled experiment.

Chapter 11. Data layout: AoS, SoA, and hot/cold splits

In this chapter: You will learn how the shape of your data in memory decides how many cache lines a loop must fetch. You will measure a 5.6x difference from a layout change alone, learn what Rust does to your struct fields, and see why a Vec<Box<T>> can be 3 to 19 times slower than a Vec<T>.

You need first: Chapters 8 to 10.

The problem first

Say you have a few million particles. Each has position x, y, z, a mass, and four other numbers. That is 8 numbers of 8 bytes: 64 bytes, exactly one cache line.

You want to add up all the masses.

The loop does one useful read per particle. But the CPU fetches a full line (64 bytes) to read 8 bytes. 87.5% of what comes in is wasted.

The model (the "what")

There are two common ways to lay out many records.

Array of Structs (AoS): one array, each element a whole record.

 AoS: one line per particle, we only want MASS
 line 0: [ x  y  z  MASS  o  o  o  o ]
 line 1: [ x  y  z  MASS  o  o  o  o ]
 line 2: [ x  y  z  MASS  o  o  o  o ]
          ^^^^^^ ^^^^ ^^^^^^^^^^^^
          unused used  unused         -> we carry 64 bytes to use 8

Struct of Arrays (SoA): one array per field.

 SoA: all masses side by side
 line 0: [ MASS MASS MASS MASS MASS MASS MASS MASS ]
          -> every byte we carry is a byte we use

Neither is "better". It depends on which fields each loop reads. If a loop uses all the fields of one record, AoS is good (one line gives everything). If it uses one or two fields across many records, SoA is good.

A middle way is the hot/cold split: keep the fields that are read often ("hot") together in one array, and the rarely-used ones ("cold") in another.

What Rust does to your struct

Rust is allowed to reorder the fields of a struct to save space. C is not. The reason is alignment: each field must start at an address that is a multiple of its own size, so the compiler adds empty padding bytes between fields when needed. Look at this struct with a u8, then a u64, then a u8:

 repr(C), fields in the order written:        Rust default (reordered):
 [a][pad pad pad pad pad pad pad]             [b b b b b b b b][a][c][pad ×6]
 [b b b b b b b b]                            = 16 bytes
 [c][pad pad pad pad pad pad pad]
 = 24 bytes

I measured this: size_of is 16 for the Rust default, 24 for repr(C), and 10 for repr(C, packed) (which removes padding but makes some reads misaligned and slow). Another small fact, from the same run: Option<Box<u64>> is 8 bytes (the null pointer stands for None), but Option<u64> is 16 bytes.

The lesson: bytes per record is a performance number. Fewer bytes per record means more records per line.

Build it (the "how")

Experiment 1: AoS versus SoA

Four million particles of 64 bytes, and we sum the mass field.

#[derive(Clone, Copy)]
#[repr(C)]
struct Particle {
    x: f64, y: f64, z: f64, mass: f64,
    other: [f64; 4], // fields we do not need in this loop
}

fn sum_mass_aos(ps: &[Particle]) -> f64 {
    let mut s = 0.0;
    for p in ps { s += p.mass; }
    s
}

fn sum_mass_soa(masses: &[f64]) -> f64 {
    let mut s = 0.0;
    for m in masses { s += *m; }
    s
}

The SoA loop is about 5.6 times faster, with the same additions. The only change: every line we pull in now holds eight masses.

But SoA moved 8 times less data and was only 5.6 times faster. Why not 8? My guess: after the layout fix, the loop stops waiting on memory and starts waiting on itself. In s += *m, each addition needs the result of the previous one. That chain has its own speed limit (Chapter 13). Test the guess: split the sum over four separate totals.

The guess held. Against the original AoS loop, we are now about 13 times faster, with the same math. (The compiler does not make this split for you on floats, because adding in a different order can change the last digits. Chapter 13 explains.)

Experiment 2: the hot/cold split

Two million items of 16 bytes: a 4-byte kind, a 4-byte value, and 8 more bytes. A loop that counts items with kind == 3 only reads kind.

4 times less data, 2.5 times faster. Less than 4x again, because at small sizes the loop is no longer only limited by memory. The split paid off, but it has a cost you must count: now the kind and the rest of the item live in different places, and code that needs both has to look in two arrays.

Experiment 3: Vec<T> versus Vec<Box<T>>

This one matters a lot for interpreters and compilers, where trees and graphs are built from boxes.

We have 2 million items. We sum the value field in three layouts:

Think about what each one does:

• Vec<Item>: a straight walk through contiguous memory. The prefetcher (Chapter 12) loves it.
• Vec<Box<Item>> in order: the vector holds pointers, and each pointer leads to a separate heap allocation. Because they were allocated one after another, the allocator mostly placed them in order, so the walk is still fairly smooth. But each box also has allocator overhead, so each item is spread over more memory. Cost: 3.1x.
• Shuffled: the same boxes, but visited in a random order, like a linked structure that has been edited for a long time. Every access is a random jump. Cost: 18.6x compared with the plain vector.

(I did not measure the allocator overhead or the exact spacing of the boxes. The 3x is the measured result. The explanation is my reading of it.)

The data is identical. Only the placement changed. A lesson for later chapters: the AST or the symbol table you wrote with Box everywhere may be paying this cost. We will fix it with arenas and index-based trees in Chapters 23 and 33.

Why it is this way (the "why")

Why do languages make Vec<Box<T>> so easy to write? Because it matches how we think. An object is a thing with an identity. Pointers make it easy to share and change things. This is the object-oriented picture, and it is convenient for humans.

Memory does not care about our convenience. Memory wants the data for the next step to be next to the data for this step. This is the data-oriented picture: organize data by how it is used, not by what it is called. SoA and hot/cold splits are two examples.

The trade-off is real. A data-oriented layout is harder to read and change. A new field means touching several arrays. Do not do it everywhere. Do it where a profile (Part IV) says a loop is bound by memory and uses a small share of each record.

A useful question for any data structure: "What is the access pattern?" Then ask:

1. How many bytes per record does the hot loop actually read?
2. How many bytes does it drag in? (Line size, padding, pointers.)
3. How many records does it visit in a row, and in what order?

What would make SoA wrong? If a loop reads all the fields of each record, SoA makes you fetch from several arrays at once, which uses more cache lines and more prefetcher streams. Then AoS is better. And if the data is small enough to sit in L1, layout hardly matters. The right answer depends on the workload, which is the lesson of Chapter 3 again.

Common mistakes

• Using SoA everywhere. It helps loops that read a few fields. It hurts loops that read all fields.
• Forgetting padding. Check size_of for hot structs. Reordering fields (or letting Rust do it) can save bytes.
• Using repr(C) without need. It stops Rust from reordering fields.
• Using packed to save space. Misaligned reads can be slower. Measure.
• Box everywhere in hot structures. Each box is a pointer to chase.
• Optimizing layout before profiling. The loop may not be the hot one.

Say it simply

How you lay out your data decides how many cache lines a loop must fetch. If a loop reads one field out of eight, an array of structs wastes most of every line, and a struct of arrays does not: we got a 5.6x speedup, and a split-and-unroll took it to 13x. A hot/cold split keeps the often-used fields together. Rust reorders fields to reduce padding, and repr(C) stops that. Boxes scatter your data: a vector of boxes was 3x slower in order and 19x slower in random order.

Check yourself

Exercise 11.1 (Warm-up): Size it. Compute the size and padding of struct A { a: u8, b: u32, c: u16, d: u64 } with repr(C). Then find the smallest possible size by reordering. Check with size_of.

Exercise 11.2 (Warm-up): Lines per record. A record is 40 bytes. How many records fit in a 64-byte line? On average, how many lines does one record touch? How about 32 bytes, or 48?

Exercise 11.3 (Core): Reproduce AoS vs SoA. Run the test. Then change the loop to read x, y, z, and mass all together. Which layout wins now? At what number of fields read does the winner change? Done when: a table of time against number of fields read, for both layouts.

Exercise 11.4 (Core): Hot and cold split. Take a struct with 3 fields you read every time and 5 fields you read once in a while. Write one benchmark where AoS wins and one where the split wins. Explain what made the difference in each.

Exercise 11.5 (Core): The box tax. Reproduce Experiment 3. Then build a version with indices into one big Vec<Item> instead of boxes, and visit in the random order. Where does its time land?

Exercise 11.6 (Stretch): A mixed layout. Try an "AoSoA" layout: groups of 8 particles, with all masses of the group together, all x values together, and so on. When might it beat both AoS and SoA?

Exercise 11.7 (Stretch): Design and defend. You are building an interpreter. Each Value has a type tag, a number, and a pointer. Your loop checks the tag of millions of values and only sometimes needs the rest. Would you store values as AoS or SoA? What would change your mind? Write a half-page defence that names a trade-off you accept.

What a strong answer includes: the working set size, the share of bytes used per line, how often each field is read, the code simplicity cost, and how the answer changes if the loop is not the hot one.

Chapter 12. Access patterns and the prefetcher

In this chapter: You will learn how the CPU hides memory latency by guessing, and when the guess fails. You will measure a 100x difference between a dependent and an independent random access, and see a software prefetch that did not help.

You need first: Chapters 8 to 11.

The problem first

In Chapter 8, one dependent access to main memory cost 137 ns. A sequential sum over the same size of memory moved 8 bytes in about 0.8 ns. How can the same memory be 170 times faster in one test than the other?

Because the CPU does not wait for one load at a time. It overlaps them.

The model (the "what")

Two separate tricks hide the latency of memory.

Trick 1: the hardware prefetcher. The CPU watches the addresses your program touches. If it sees a pattern (for example, one line after another, or every third line), it starts fetching lines before you ask. When you do ask, they have already arrived. Prefetching means "fetching data before it is needed".

 You read:     line 10, line 11, line 12, ...
 Prefetcher:   "I see a pattern!"  →  fetches 13, 14, 15, 16 ahead of time
 You read:     line 13  →  already in cache.

Trick 2: memory-level parallelism (MLP). A modern CPU can have many loads in flight at the same time (often ten or more per core). It does this by out-of-order execution: the CPU does not stop on a load that is waiting. It looks ahead in your code, finds the next loads that don't depend on it, and starts them too. Memory-level parallelism is the number of memory requests in flight at once.

The two tricks need different things:

• The prefetcher needs a predictable pattern.
• MLP needs independent loads: the address of the next load must not depend on the result of the previous one.

A dependent access (a pointer chase) has neither: the address is unknown until the last load finishes, and there is no pattern to see. That is why it shows the raw latency.

A rule of thumb from queueing theory ties these together (it is called Little's law): throughput = parallelism ÷ latency. If one load takes 100 ns, and you can have 10 in flight, you can complete about one load every 10 ns. Memory-level parallelism divides the latency.

Build it (the "how")

We make 8 million accesses into a 256 MiB array of u64, in five different ways, and compute the time per access.

8000000 accesses each, 256 MiB of data
sequential                :    1.41 ns/access
stride 136 bytes          :    6.29 ns/access
random, independent       :   12.03 ns/access
random, dependent (chase) :  116.37 ns/access  (table is only 30 MiB)
random + prefetch 16 ahead:   11.67 ns/access

(In the first three tests, we read an index from a list, then load data[index]. The index list itself is read in order. The chase uses a table of 8 million 4-byte entries, so only 30 MiB, which is smaller than the 256 MiB of the others. The comparison is rough, but the gap is large enough that the point stands.)

Go through the table.

Sequential: 1.41 ns. The prefetcher sees the simple pattern and streams lines ahead. Memory is not the bottleneck at all.

Stride of 136 bytes: 6.29 ns. A fixed stride is still a pattern, and the prefetcher can follow many strides. But we touch a new line (sometimes two) on every access, so we fetch about 4 to 5 times more lines than in the sequential case. Fine, but not free.

Random, independent: 12.03 ns. No pattern, so no prefetcher help. But the loads don't depend on each other, so the CPU runs many at once. Each load still takes about 100 ns, but with roughly ten in flight, we complete one every 12 ns. This is MLP in action.

Random, dependent: 116.37 ns. Same randomness, but each address depends on the last load. No overlap. We pay the full latency every time. This is 9.7 times slower than the independent case, from only one change: whether the next address needs the last result.

Random with a software prefetch: 11.67 ns. I added an instruction to ask for the element 16 steps ahead (_mm_prefetch). It made no real difference: 11.67 against 12.03 ns. That surprised me a little. The reason is probably that the out-of-order CPU was already overlapping the loads, as MLP above, so there was no latency left to hide. A prefetch helps when the CPU cannot look far enough ahead by itself. Here it could. (I think this is the reason, and I did not confirm it by counting events. Chapter 19 shows how.)

The point of the table: the same memory, the same amount of data, and a 100x range in time per access (1.41 up to 116 ns), decided only by the pattern and the dependencies.

Why it is this way (the "why")

Why do chips spend so much hardware on prediction and overlap? Because memory has been the slowest part for decades. CPU speed grew much faster than memory speed. This gap is sometimes called the memory wall. Chip designers could not make memory faster, so they made the CPU less sensitive to its slowness, by guessing and overlapping.

This leads to the central idea: modern performance is about hiding latency, not removing it. You cannot make a DRAM access take less than about 100 ns. You can arrange that you never wait for one.

What does that tell you about code?

1. Prefer sequential and strided access. The prefetcher is on your side.
2. Prefer independent loads. If you have many lookups to do, issue them all, then use the results. A hash table lookup done 100 times in a batch can overlap. The same lookups done one after another, each needing the last result, cannot.
3. Break dependency chains. A linked list or a deep tree is a chain by nature. A flat array, or an index-based tree stored in an array, can be easier on the hardware.
4. Do not assume a software prefetch helps. It is a wager: you spend instructions and cache space to guess the future. If the CPU was already doing it, you lose a little.

There is a limit on the whole model. The number of loads in flight is limited (the CPU has a fixed number of slots for outstanding cache misses). If a loop issues loads faster than memory can serve, the slots fill up and it becomes bandwidth-bound. Our independent-random test at 12 ns is probably near this limit. Chapter 19 draws this limit as the roofline.

What would make it wrong? The prefetcher is a black box that changes between chips. A pattern that works on one machine may confuse another. Software prefetch behavior also differs. This is why we measure, and why Chapter 35 looks inside the hardware counters.

Common mistakes

• Writing a dependent chain when the work is independent. For example, following a pointer to find the next pointer when you could first collect all the addresses.
• Assuming random access is always slow. Random and independent can be 10x faster than random and dependent.
• Adding software prefetch without measuring. It often does nothing and sometimes hurts.
• Testing access patterns on tiny data. Everything is in L1 and the patterns look the same.
• Ignoring the index list. In a gather, the index list itself must be read too.

Say it simply

The CPU hides memory latency in two ways: the prefetcher spots patterns and fetches ahead, and out-of-order execution runs many independent loads at once. A pointer chase, where each address depends on the last load, defeats both, and paid the full 116 ns per access. The same random accesses made independent took 12 ns. A manual prefetch did nothing here because the CPU was already overlapping the loads. You cannot make memory faster, but you can arrange never to wait for it.

Check yourself

Exercise 12.1 (Warm-up): Little's law. A memory access takes 100 ns. If the CPU can keep 10 accesses in flight, what is the best throughput in accesses per second? What if it can keep only 2?

Exercise 12.2 (Warm-up): Dependent or independent? For each, say which it is: (a) summing an array, (b) walking a singly linked list, (c) looking up 1000 keys in a hash map one at a time, (d) binary search on a sorted array, (e) following parent links in a tree to the root.

Exercise 12.3 (Core): Reproduce the table. Run the five tests. Then change the data size from 256 MiB to 4 MiB. Which rows change the most? Which barely change? Explain.

Exercise 12.4 (Core): Batch your lookups. Take 8 million random lookups in a big array. Write a version where each lookup's address depends on the previous result, and a version where they are independent. Then write a middle version that processes 8 independent chains at once (interleaved). How fast is it? Hint: interleaving several independent chains is how you speed up many tree or hash lookups.

Exercise 12.5 (Core): Try the prefetch distance. Repeat the software-prefetch test with distances 1, 4, 16, 64, and 256. Make a table. Is there a best distance? Does it ever help?

Exercise 12.6 (Stretch): Find the stride limit. Run a strided sum with strides from 1 to 4096 bytes. Where does the prefetcher stop helping? What does the answer say about page boundaries (Chapter 10)?

Exercise 12.7 (Stretch): Design and defend. You have a binary search tree with 10 million nodes. Lookups are slow. List three changes that reduce latency per lookup, and three that raise lookups per second without reducing latency. Which would you try first?

What a strong answer includes: a flat or B-tree style layout for latency, batching and interleaving for throughput, the idea that these are different goals, and a measurement plan.

Chapter 13. Pipelines, dependency chains, and branch prediction

In this chapter: You will learn how a CPU runs many instructions at once, why a chain of dependent additions is slow, and what a mispredicted branch really costs. You will measure a branch that is 8 times slower on random data than on sorted data, and an addition loop that gets 7 times faster with more independent totals.

You need first: Chapters 8 to 12.

The problem first

In Chapter 11, the SoA loop was held back by "waiting for itself". In Chapter 7, the multi-accumulator trick helped at one size and not at another. Both used the same hidden idea: a CPU is not a machine that runs one instruction after another. It runs many at once. Here is how, and when it breaks.

The model (the "what")

The pipeline

A single instruction goes through several steps: fetch it, decode it, execute it, write the result. A simple CPU does all steps for one instruction and then starts the next. A pipelined CPU works like an assembly line: while one instruction is being executed, the next is being decoded, and the one after is being fetched. Each stage works on a different instruction at the same time.

 time →     1     2     3     4     5     6
 instr 1   fetch decode exec  write
 instr 2         fetch decode exec  write
 instr 3               fetch decode exec  write

Modern CPUs go much further:

• Superscalar: several instructions are executed in the same cycle, on separate execution units (little calculators inside the core). A core may do several integer operations, loads, and floating-point operations every cycle.
• Out-of-order: the CPU does not follow your program order strictly. It looks at a window of upcoming instructions, and runs whichever have their inputs ready. It then retires them (makes them official) in the original order, so the result looks as if they ran in order.

Two words, latency and throughput, are used again here, for a single instruction:

• Instruction latency: how many cycles from when an instruction starts to when its result can be used.
• Instruction throughput: how many instructions of that kind can be started per cycle.

A floating-point add might have a latency of a few cycles but a throughput of two per cycle. That means: one add takes a few cycles to finish, but the CPU can have many in flight.

Dependency chains

An instruction can only run when its inputs are ready. If instruction B needs the result of instruction A, B must wait for A's latency. A sequence where each needs the last is a dependency chain.

 s += a[0];   ← needs s
 s += a[1];   ← needs the s from the line above
 s += a[2];   ← needs the s from the line above

This chain runs at the speed of the latency, no matter how many execution units the CPU has. Splitting the work into independent chains lets the CPU run them side by side, at the speed of the throughput:

 s0 += a[0];   s1 += a[1];   s2 += a[2];   s3 += a[3];    ← four chains, independent
 s0 += a[4];   s1 += a[5];   ...

Branches and the predictor

A branch is an if, a loop condition, or any place where the next instruction depends on a test. The CPU does not want to wait for the test to finish, because the pipeline would sit empty. So it predicts which way the branch will go, and keeps working speculatively on that guess. Speculative execution means running instructions before you know that you need them.

• If the guess is right, nothing is lost.
• If the guess is wrong (a misprediction), everything done after that branch must be thrown away, and the pipeline restarts from the correct path. This costs the time to refill the pipeline.

The part of the CPU that guesses is the branch predictor. It learns from history: "this branch went left the last ten times, so it will probably go left again." It is very good on patterns (always taken, alternating, loops). It is useless on random outcomes, where it can only be right about half the time.

Build it (the "how")

Experiment 1: the branch that depends on the data

We scan a million random bytes and collect those that are at least 128 (about half of them). The test is a plain if. We use a Vec::push inside the if so the compiler cannot turn the branch into branch-free code.

#[inline(never)]
fn collect_big(data: &[u8], out: &mut Vec<u8>) {
    out.clear();
    for &x in data { if x >= 128 { out.push(x); } }
}

// Branch-free: always write, and move the write position by 0 or 1.
#[inline(never)]
fn collect_big_branchless(data: &[u8], out: &mut [u8]) -> usize {
    let mut n = 0usize;
    for &x in data {
        out[n] = x;
        n += (x >= 128) as usize;
    }
    n
}

1000000 bytes, about half pass the test (x >= 128)
branchy,    random order :  4.700 ns/item
branchy,    sorted order :  0.571 ns/item
branchless, random order :  0.521 ns/item
branchless, sorted order :  0.519 ns/item

Look at the first two lines. Same code, same bytes, only in different order. Random: 4.70 ns per item. Sorted: 0.57 ns. That is 8.2 times slower. In the sorted data, the branch goes "no, no, no, ..., yes, yes, yes". The predictor learns it instantly. In the random data, the branch is a coin flip.

We can estimate the cost of a single misprediction. About half the items are mispredicted in the random case, so the extra time per item, 4.70 − 0.57 = 4.13 ns, is half of a misprediction's cost: about 8.3 ns per misprediction. At the core clock measured in Chapter 37 (about 3.3 GHz, not the nominal 2.1), that is about 27 cycles. (I first guessed 17 cycles from the nominal clock, which was wrong. The 8.3 ns is the measured part.)

Now the branch-free version. It is 0.52 ns per item for both random and sorted. The data pattern no longer matters, because there is no branch to predict. It does extra work (a write for every item), but that work is cheap compared with a misprediction.

Note the last two lines against the second line: sorted-branchy (0.571) is nearly the same as branchless (0.519). When the branch is predictable, the branch costs almost nothing. A branch is not slow. A mispredicted branch is slow.

Experiment 2: how many chains does the CPU want?

We sum 1,024 f64 numbers (8 KiB, which lives in L1, so memory is not the limit) with 1, 2, 4, 8, and 16 separate running totals.

fn sum_n<const K: usize>(m: &[f64]) -> f64 {
    let mut acc = [0.0f64; K];
    for ch in m.chunks_exact(K) {
        for i in 0..K { acc[i] += ch[i]; }
    }
    acc.iter().sum()
}

sum of 1024 f64 in L1: ns per element
plain loop (1 chain) :  0.653
1  accumulator       :  0.635
2  accumulators      :  0.293
4  accumulators      :  0.161
8  accumulators      :  0.116
16 accumulators      :  0.092

Things to see:

• The plain loop and the 1-accumulator version are the same: a single dependency chain. The compiler is not allowed to reorder floating-point additions, because the order can change the last digits of the answer.
• 2, 4, 8 accumulators: each step roughly halves the time at first (0.635 to 0.293 to 0.161), then returns shrink (0.116, then 0.092). By 16, we are 6.9 times faster than the plain loop, with the same additions.
• The returns shrink because we run out of something else: execution units, or the rate at which the CPU can issue instructions, or the loads. You cannot get more than the hardware's throughput.

Two honest notes. First, the 1-chain cost of 0.635 ns is the latency of one addition. Chapter 37 measures the latency: about 2.25 cycles for a dependent addsd at a measured clock of about 3.3 GHz, so 0.635 ns is close to one add latency. On many older chips the effect is bigger, because the add latency is longer. Second, at 8 and 16 accumulators, the compiler may have turned the array of totals into SIMD instructions (one instruction that adds several numbers at once; Chapter 28), which would explain part of the speed-up beyond pure overlap. I did not read the machine code to check.

Why it is this way (the "why")

Why does the CPU predict and run ahead at all? Because there is a gap, again, between what is possible and what is certain. A CPU could wait to be sure. But waiting wastes the hardware, and a long pipeline with many units would sit idle most of the time. So designers made a bet: guess, run ahead, and clean up if wrong. The bet pays off enough of the time that all high-performance CPUs do it.

This is the same philosophy as the cache (Chapter 8): hardware bets on a pattern. Caches bet on locality. Prefetchers bet on strides. Branch predictors bet on history. MLP bets on independence. In every case, your program does well if it fits the bet, and badly if it breaks it. This is a good way to remember what all of Part III is about: write code the hardware can predict.

Practical consequences:

1. Break dependency chains when you have independent work. Split a sum, a hash, a checksum, or a decoder into several interleaved streams.
2. Make branches predictable. Sort or group the data so that decisions come in runs. Move rare cases out of the hot loop.
3. Consider branch-free code when the branch is unpredictable and the work in both arms is cheap. Do not use it when the branch is predictable: you do extra work for nothing. Measure both.
4. Look for the limit. Is the loop limited by latency (a chain), by throughput (units), or by branches? Different problems, different fixes.

What would make this wrong? Branch predictors on modern chips are very good, and can learn surprisingly long patterns. Your "random" data might have hidden structure that the predictor finds. And a compiler may turn your branch into a conditional move or SIMD on its own, which removes the problem (our test used push on purpose to stop it). The takeaway is not "always avoid branches". It is "know when the branch is a coin flip."

This is directly relevant for the systems you build. An interpreter's dispatch loop (a match on the opcode) is one big, hard-to-predict branch. A parser's "what kind of token is next" is a data-dependent branch. A compiler's passes over an AST are full of matches on node kinds. Part VII returns to all three.

Common mistakes

• Treating every if as slow. Only the unpredictable ones are.
• Making code branch-free by default. If the branch is predictable, you pay for nothing.
• Leaving a long dependency chain (a running sum, a hash, a state machine) when the work could be split.
• Splitting a chain without checking the result. Floating-point splits change the answer slightly. Know if that matters.
• Testing a branch on sorted or patterned data and believing it is cheap on real data.

Say it simply

A CPU is an assembly line that runs many instructions at once, out of order, and guesses which way each branch will go so it can keep going. A chain where each step needs the last one runs at the speed of one step's latency, while independent chains run side by side: splitting one sum into 16 made it 7 times faster. A wrongly guessed branch throws away work and costs about 8 ns here, so the same loop was 8 times slower on random data than on sorted data. Write code the hardware can predict.

Check yourself

Exercise 13.1 (Warm-up): Chain or not? For each, say whether the loop is one dependency chain, and why: (a) s += a[i] for floats, (b) s += a[i] for integers (think about what the compiler may do), (c) x = x * 3 + 1 repeated, (d) out[i] = a[i] * 2.

Exercise 13.2 (Warm-up): The cost of a miss. A loop has 1 branch per item. It is mispredicted 10% of the time, and a misprediction costs 8 ns. What is the extra time per item? How does this compare with a loop body of 1 ns?

Exercise 13.3 (Core): Reproduce the branch test. Run both experiments. Then vary the share of items that pass the test: make 1%, 10%, 50%, 90%, and 99% of the items pass, in random order. Plot the branchy time against the share. Where is it worst? Why is it not worst at exactly 50%... or is it? Done when: a table and a plot, plus 4 sentences on the shape.

Exercise 13.4 (Core): Find your chain limit. Run the accumulator test for 1, 2, 4, 8, 16, 32 accumulators. Where does the improvement stop? Now do the same with integer addition. Is there a difference? Look at the machine code (--emit asm) for the 16-accumulator float version: is it SIMD?

Exercise 13.5 (Core): Predictable in disguise. Make the "random" data repeat a pattern of length 8 (for example 3 big, 5 small, over and over). Does the branchy loop get fast? What about a pattern of length 1000? What does this tell you about the predictor's memory?

Exercise 13.6 (Stretch): Branchless binary search. Write a binary search with a branch inside the loop, and a version that uses arithmetic instead (move the index by step * (a[mid] < key) as usize). Compare on random keys in a big array. Which wins? Does the answer change when the array fits in L1?

Exercise 13.7 (Stretch): Design and defend. A tokenizer reads text and, for each character, decides if it is a letter, a digit, whitespace, or punctuation. A teammate wants to replace the if/else chain with a 256-entry lookup table. Argue for or against. What would you measure?

What a strong answer includes: the unpredictability of the character classes in real text (not random, but irregular), the size of the table (256 bytes fits in one handful of lines), the data dependency on the table load, and testing on real text files, not random bytes.

Part III wrap-up

What you can now do:

• Measure the latency and bandwidth of each rung of the memory ladder on your own machine, and compare with what the machine reports.
• Explain cache lines, sets and ways, and the write path, and use them to predict why a loop is slow.
• Explain virtual memory, the TLB, and huge pages, and show that pages touched matter as much as lines.
• Choose between AoS, SoA, and a hot/cold split for a loop, and know what Box does to locality.
• Explain why prefetching and independent loads hide latency, and why a dependent chain does not.
• Explain pipelines, dependency chains, and branch prediction, and write code that suits them.

Mini project: The hardware profile of my machine (4 to 6 hours). Build one small Rust program (or a few) that produces a one-page report about your machine:

1. A latency staircase from pointer chasing, with each rung's size and latency.
2. A bandwidth staircase from a sequential sum.
3. An estimate of the cache line size, from a stride test.
4. A TLB test (packed vs. spread) that shows where the first-level TLB runs out.
5. The cost of one branch misprediction, from the sorted-vs-random test.
6. The number of independent chains the CPU needs to reach full throughput on additions.

Compare every number with lscpu and the manual for your CPU. Write down where they disagree, and your best guess why.

Done when: a one-page report with a table of 6 results, each with the program that made it, and a short list of "what this report does not show".

Write-up prompt: Half a page. Which measurement surprised you most, and what would you change in your next program because of it?

Teach it back: In 5 sentences, explain to a friend why walking a matrix by columns can be 16 times slower than by rows, even though the number of additions is the same.

Reading list for Part III:

• Ulrich Drepper, What Every Programmer Should Know About Memory (2007). Long, and the clearest deep explanation of caches, cache lines, sets and ways, and the write path. Read the CPU caches and the virtual memory sections first.
• John L. Hennessy and David A. Patterson, Computer Architecture: A Quantitative Approach. The chapters on the memory hierarchy and instruction-level parallelism explain the theory of locality, pipelines, and branch prediction.
• Agner Fog, Optimizing software in C++ and his instruction tables and microarchitecture manuals. Free, and the best place to find the real latency and throughput of instructions for specific CPUs.
• Your CPU maker's optimization manual (for example, Intel's 64 and IA-32 Architectures Optimization Reference Manual). The exact cache sizes, TLB sizes, and latencies for your chip live here. Check your chip, not this chapter.

Verification notes for Part III: All programs were compiled with rustc 1.75 (-C opt-level=3) and run on the 1-core Xeon VM; every table is real output (the Chapter 8 latency table and the Chapter 11 AoS/SoA tables are from the earlier sample chapter, same machine and settings). Page size (4096) and the transparent huge page setting (always [madvise] never) were read from the machine. Not confirmed, and marked in the text: why the neighbor-line effect appears in the stride test, the L1 associativity (my reading of the data), the TLB sizes (read from the shape of the data, not from the manual), the cause of the dependent-chase gap in Chapter 8 beyond what the TLB test suggests, why the software prefetch did not help, how much of the 16.2x matrix gap comes from locality versus set conflicts versus pages, whether the 8 and 16 accumulator loops used SIMD, and the actual clock speed of the VM. The reading-list items come from my own knowledge and were not freshly checked in this session. Not run: huge-page experiment, write-path experiment, two-thread L3 experiment (each is an exercise).

Part IV. Profiling: finding where the time goes

After this Part, you will be able to take a slow program you have never seen, and, in an afternoon, tell your team where the time goes, how you know, and how sure you are.

Part III told you what the machine likes. But a big program has thousands of loops. You cannot rewrite them all. You need to find the few that matter. That job is called profiling: a profile is a record of where a program spends its time (or its memory, or its cache misses), broken down by function or by line.

In this Part we use one running example, from start to finish, with five different tools. We will see where the tools agree, and, more important, where they disagree and why.

Honest note about the tools in this sandbox. I ran every tool in this Part on the 1-core cloud VM. One thing did not work: the hardware performance counters (the CPU's built-in event counters for cycles, instructions, cache misses). The VM does not pass them through, so perf stat printed <not supported> for them. Software-based tools all worked. I will tell you at each place what was run and what was not.

Chapter 14. Choose the evidence before the tool

In this chapter: You will learn the six kinds of evidence a profiler can give, which question each one answers, and you will meet the program we profile for the rest of the Part. You will also write down a guess before measuring, so that you can be surprised.

You need first: Parts I to III.

The problem first

A new engineer gets a ticket: "The word counter is slow. Make it faster." They open the code. The slow part is obviously the hash map. Everyone knows hash maps are slow. They spend two days replacing it with a faster one.

The program gets 3% faster.

What went wrong? They picked a tool (their eyes) and a theory ("hash maps are slow") before they had any evidence. The map was about a quarter of the time. The big cost was somewhere they never looked.

The model (the "what")

A profiler is any tool that tells you where a program spends something. But "where" can mean very different things, and each kind of evidence has strengths and blind spots. Here are the six kinds we use in this guidebook:

No single kind of evidence is enough. A good profile report uses at least two, and checks that they agree.

A word about sampling, because we use it the most. A sampling profiler interrupts the program at a fixed rate, say 1,999 times per second, looks at what the program is doing right then (which function is running, and the chain of callers above it, called the stack), and writes it down. After 1,800 samples, it counts: "this function appeared in 60% of them." The idea is a poll: you do not watch every second of the program, you take a random sample of moments, and the share of the samples is an estimate of the share of the time.

Two kinds of share, and you must keep them straight:

• Self time of a function: the share of samples where that function's own code was running (not its callees).
• Inclusive time (also called total or cumulative): the share of samples where that function was anywhere on the stack. This includes everything it called.

A function with a big inclusive time and a small self time is a manager: it does little itself, but it calls the things that take time. A function with a big self time is a worker: the cost is in its own code.

Build it (the "how")

The running example: a word counter

Here is the program. It makes 5 million words of fake text (so we can run it anywhere, with the same result every time), splits it into lowercase words, counts each word in a hash map, and prints the 5 most common ones. It is a stand-in for many real programs: a tokenizer, a map, and a sort.

use std::collections::HashMap;

// Make a deterministic pseudo-text: words from a fixed vocabulary, mixed case, with punctuation.
fn make_text(words: usize) -> String {
    let vocab = [
        "The", "quick", "brown", "fox", "jumps", "over", "lazy", "dog", "Rust", "compiler",
        "parser", "interpreter", "cache", "memory", "profile", "flame", "graph", "thread",
        "Vector", "array", "Struct", "enum", "trait", "borrow", "lifetime", "Iterator",
    ];
    let mut s = 0x2545F4914F6CDD1Du64;
    let mut out = String::with_capacity(words * 8);
    for i in 0..words {
        s ^= s << 13; s ^= s >> 7; s ^= s << 17;
        let w = vocab[(s % vocab.len() as u64) as usize];
        out.push_str(w);
        out.push(if i % 11 == 10 { '.' } else { ' ' });
        if i % 11 == 10 { out.push(' '); }
    }
    out
}

fn tokenize(text: &str) -> Vec<String> {
    let mut tokens = Vec::new();
    for raw in text.split_whitespace() {
        let cleaned: String = raw.chars().filter(|c| c.is_alphanumeric()).collect();
        if !cleaned.is_empty() {
            tokens.push(cleaned.to_lowercase());
        }
    }
    tokens
}

fn count(tokens: &[String]) -> HashMap<String, usize> {
    let mut m: HashMap<String, usize> = HashMap::new();
    for t in tokens {
        *m.entry(t.clone()).or_insert(0) += 1;
    }
    m
}

fn top(m: &HashMap<String, usize>, k: usize) -> Vec<(String, usize)> {
    let mut v: Vec<(String, usize)> = m.iter().map(|(a, b)| (a.clone(), *b)).collect();
    v.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)));
    v.truncate(k);
    v
}

fn main() {
    let words: usize = std::env::args().nth(1).and_then(|a| a.parse().ok()).unwrap_or(5_000_000);
    let text = make_text(words);
    let tokens = tokenize(&text);
    let counts = count(&tokens);
    for (w, c) in top(&counts, 5) {
        println!("{:<12} {}", w, c);
    }
}

We build it with debug information turned on, so profilers can name functions and lines. This does not slow the program: debug info is just extra data in the file, kept apart from the machine code.

# Cargo.toml
[profile.release]
debug = true          # keep symbols and line info so profilers can name functions

cargo build --release

Step 1: write your guess down first

Before measuring, here is a guess. Write one of your own too.

My hypothesis: the hash map in count takes most of the time, because hashing a string and comparing strings is slow.

Step 2: wall-clock timing

Run three times, using the shell's time (this is evidence of the first kind):

1.098 s wall, 0.674 user, 0.160 sys
0.812 s wall, 0.687 user, 0.124 sys
0.819 s wall, 0.722 user, 0.096 sys

Remember Chapter 2. The first run was slower (1.098 s) because the machine was not warm. The next two agree at about 0.82 s. And there is something new: look at sys. user is time spent running our code, and sys is time spent in the operating-system kernel on our behalf (for example, handling page faults, as we will see). About 0.1 s of 0.8 s is not in our code at all.

So we now have a baseline: the 5-million-word run takes about 0.82 s. That is 164 ns per word. Whatever we find, we will compare with this.

But we know nothing about where. The rest of this Part is about that.

Why it is this way (the "why")

Why not just read the code and guess? Because intuition about performance is bad, and it gets worse as programs get complicated. The reasons are the same as Part III: modern machines do things (caching, prefetching, speculating, overlapping) that are invisible in the source code. Two lines that look equal in the code can differ by 100x at runtime. Code that looks very slow (a loop in a loop) can be fast, and code that looks innocent (a .to_lowercase()) can hide an allocation.

Profiling is a way of replacing opinions with evidence. And "evidence" has a precise meaning here: a number that could have turned out differently. If you write down a guess and the profile can prove it wrong, the profile is evidence. If you only look at the profile after deciding what you will see, you will see what you decided.

There is one more idea: a profile tells you where, and almost never why. "60% of the time is in tokenize" is a where. "Because each word makes three heap allocations" is a why. Getting from one to the other needs a second kind of evidence (counts, allocation tracking, a cache simulator) and some thinking. The structure of the next chapters follows that path: find where (sampling), confirm it (instrumentation), find why (counting and simulation).

What would make this approach wrong? Sampling profiles of short programs are noisy. Programs whose time is spent waiting (on the network, on locks, on the disk) look different under a CPU-time profiler than under a wall-clock profiler. And profiling changes the program a little (the observer effect). Always ask: did I change what I was measuring when I measured it?

Common mistakes

• Optimizing before profiling. The most common mistake of all.
• Profiling a debug build. The hot spots in a debug build are not the hot spots in the release build.
• Profiling without symbols. You get addresses, not names.
• Trusting one tool. Cross-check with a second kind of evidence.
• Mixing up self time and inclusive time.
• Profiling a program that is too short. Fewer than a few hundred samples means a noisy answer.

Say it simply

A profile says where a program spends its time. There are six kinds of evidence (timing, sampling, instrumentation, event counts, simulation, allocation tracking), each good at one question and blind to others. Sampling works like a poll: it asks "what are you doing right now?" many times a second, and the share of answers estimates the share of time. Self time is a function's own work. Inclusive time includes what it calls. Write a guess down first, so the profile can surprise you.

Check yourself

Exercise 14.1 (Warm-up): Pick the evidence. For each question, name the best kind of evidence and why: (a) "Which function takes the most time?" (b) "How many times is parse_token called?" (c) "Does my change make the whole program faster?" (d) "How many bytes does this function allocate?" (e) "Why is this loop slow: is it cache misses?"

Exercise 14.2 (Warm-up): Self or inclusive? A function run calls a and b and does almost nothing else. a takes 70% of the time and b takes 30%. What are the self and inclusive times of run, a, and b?

Exercise 14.3 (Core): Make your own guess. Type in the word counter, build it with debug info, and time it three times. Before profiling, write down (a) your guess for the share of time in make_text, tokenize, count, and top, and (b) the single line you think is the most expensive. Keep this page for the next chapters. Done when: a page with your timings, your guesses, and a number for the baseline.

Exercise 14.4 (Core): Debug versus release. Time the program in a debug build (cargo build, no --release). How many times slower is it? Does it still look like the same program, in terms of what you would guess is slow? (Do not profile it yet. Just time it.)

Exercise 14.5 (Stretch): Design and defend. Your team lead says: "Our service is slow. Let's profile it in production for a week and then decide." Write half a page: what would you ask for first, what could go wrong with profiling production, and what is the smallest first step you would take?

What a strong answer includes: a clear performance question and a target, the observer effect and overhead, the choice between sampling and instrumentation, the risk of private data in profiles, and a cheap first measurement (a baseline) before any large profiling.

Chapter 15. perf stat and perf record

In this chapter: You will learn the two most important commands of the Linux profiler perf: one that counts events and one that samples. You will see what happens when counters are missing, and learn how to estimate how much to trust a sampling profile.

You need first: Chapter 14.

The problem first

The Linux kernel comes with a profiler that can see more than any tool you can write yourself: every function in your program, in the C library, and inside the kernel itself. It is called perf. It looks hard at first, because it has dozens of sub-commands. But 90% of the time you need only two.

The model (the "what")

perf stat counts. You give it a program. It runs the program, and at the end it prints totals: how many CPU-seconds, how many page faults, how many context switches, and (on hardware that supports it) cycles, instructions, branch misses, and cache misses. It does not tell you where. It tells you how much.

perf record samples. It runs the program, interrupts it at a fixed rate, and saves what it saw into a file (perf.data). Then perf report reads that file and prints the results. This tells you where.

Two kinds of events can drive these tools:

• Software events, counted by the kernel: task-clock (CPU time used), page-faults, context-switches, cpu-migrations. These work everywhere.
• Hardware events, counted by the CPU's own performance monitoring unit (PMU): cycles, instructions, branch-misses, cache-misses, and many more. These are the ones that tell you why a loop is slow. But they need the CPU to expose its counters to your program. On a bare-metal Linux machine, they usually work. In many virtual machines, they do not.

Some terms for what a sampling profile contains:

• A sample is one snapshot: the instruction the CPU was running, and (if you ask for it) the whole stack of callers.
• Frame pointers are a convention where each function keeps a link to its caller, so that a profiler can walk the stack quickly. Rust usually leaves them out of release builds, for speed. To get good stacks cheaply, build with -C force-frame-pointers=yes. (The other way is to ask perf to read the stack with DWARF debug information, which works without frame pointers but is slower and makes much bigger files.)
• Skid is a small error in where a hardware-triggered sample lands. The CPU takes a moment to react, so the sample may blame the instruction after the real one.

Permissions

perf uses a kernel setting, perf_event_paranoid. At 2 or higher, ordinary users can only profile their own programs in user space. At 1 they can see kernel code too, and at 0 or -1 even more. As root (as I was in this sandbox) most things work. On your own machine you may need sudo sysctl kernel.perf_event_paranoid=1.

Build it (the "how")

perf stat: the totals

perf stat -e task-clock,page-faults,context-switches,cpu-migrations ./target/release/wf

 Performance counter stats for './target/release/wf':

            825.37 msec task-clock                       #    0.996 CPUs utilized
             76485      page-faults                      #   92.668 K/sec
                34      context-switches                 #   41.194 /sec
                 0      cpu-migrations                   #    0.000 /sec

       0.828369888 seconds time elapsed

       0.714114000 seconds user
       0.116346000 seconds sys

Read it:

• 825 ms of task-clock matches the 0.82 s wall time from Chapter 14, and "0.996 CPUs utilized" says the program used one core almost 100% of the time. It was never waiting for anything. It was computing (or at least, the CPU was busy for it).
• 34 context-switches and 0 migrations: the program was almost never interrupted or moved. Good, the machine was quiet.
• 76,485 page faults. This is the surprise. A page fault happens when your program touches a page of memory (Chapter 10) that the kernel has not yet given it. The kernel must stop, find a free page, zero it, and map it. Each costs on the order of microseconds. We took 76,485 of them. At 4 KiB per page, that is about 300 MiB of memory touched for the first time. The program asks the kernel for about 300 MiB, for a job whose answer is five lines. And that matches the sys time of 0.116 s, which is about 14% of the run. We now have a why clue for free: this program uses a lot of memory.

And now the part that did not work. I also asked for hardware counters:

perf stat -e task-clock,cycles,instructions true

   <not supported>      cycles
   <not supported>      instructions

This VM does not expose the PMU. On a real machine, you would also see lines like "2.31 insn per cycle" (IPC, instructions per cycle: how much of the CPU's width the program uses) and a branch-miss rate. These are exactly the numbers that would tell us whether the loops are stalled on memory or on branches. I cannot show them here. I will say what I would expect on real hardware, and I will mark it as a guess. (Chapter 19 explains how to use these counters, and Chapter 20 shows a software substitute.)

perf record: where is the time?

RUSTFLAGS="-C force-frame-pointers=yes" cargo build --release
perf record -e cpu-clock -F 1999 --call-graph fp -o wf.data ./target/release/wf
perf report -i wf.data --no-children --stdio -g none

The flags:

• -e cpu-clock: sample by a software timer, because hardware cycles is not available here. (On real hardware, the default event, cycles, is usually better: samples then follow CPU work and not wall time.)
• -F 1999: 1,999 samples per second. I chose an odd number on purpose, so that we never line up exactly with a periodic thing in the program that happens every millisecond.
• --call-graph fp: record the stack by following frame pointers.
• --no-children: show self time (without it, perf report shows inclusive time in an extra column).

Result: 1,804 samples. The top of the table, by self time:

    11.81%  wf  wf                 [.] wf::tokenize
     8.81%  wf  libc.so.6          [.] malloc
     6.76%  wf  wf                 [.] alloc::str::<impl str>::to_lowercase
     6.49%  wf  libc.so.6          [.] _int_free
     6.43%  wf  wf                 [.] <String as FromIterator<char>>::from_iter
     5.88%  wf  libc.so.6          [.] _int_malloc
     5.76%  wf  wf                 [.] hashbrown::rustc_entry
     5.21%  wf  wf                 [.] core::hash::BuildHasher::hash_one
     4.27%  wf  [kernel.kallsyms]  [k] do_user_addr_fault

(I shortened a few long names.) The [.] marks code in user space, and [k] marks code in the kernel. Look at what is on this list:

• malloc, _int_malloc, _int_free: the memory allocator. Together with cfree (3.4% in an earlier profile of the same program), this is a big block. Our hash-map guess did not show up as the leader.
• do_user_addr_fault: the kernel handling page faults. That is the 76,485 faults from perf stat, seen again from the other side. Two tools agree.
• The string code (to_lowercase, from_iter) and the hash code (hash_one, rustc_entry) are each about 5% to 7%.

No single function owns the profile. The time is spread over many small pieces, which is common. It also means you cannot find the answer by looking for "the hot function". You need to add things up, by phase and by theme. We do that with flamegraphs in the next chapter.

A trap: inlining hides functions

My very first perf record, before I added #[inline(never)] to the four phase functions, showed this as the top line:

    16.30%  wf  wf   [.] wf::main

wf::main is the function that does almost nothing. It calls the other four. But the compiler had inlined them: it copied their code into main, so the profiler, which only sees addresses and the symbols attached to them, said "this is main". Nearly 16% of the time appeared to be in a function that does nothing, and the names of make_text, tokenize, and count vanished from the profile.

I fixed that by adding #[inline(never)] to the four phase functions, as we did in the final version of the program. That changes the program a little: a function call that was free is now a real call. For functions that run once and take hundreds of milliseconds, the change is far too small to matter. It would be a bad idea for a tiny function in a hot loop.

The lesson: a profile can only name what exists in the machine code. If your code seems to vanish, it was probably inlined. Debug info records the original line numbers, so line-level views (perf annotate) can still see through the inlining.

Why it is this way (the "why")

Why do sampling profilers work at all, given that they only look at the program a couple of thousand times a second? Because of statistics. If you look at a random moment of the program's life and see it inside tokenize, then the chance of that happening is exactly the share of time spent in tokenize. Repeat 1,800 times, and the share of your samples estimates the share of time. This is the same idea as a poll before an election.

And just like a poll, there is a margin of error. If the true share is p and you take n samples, the standard error of your estimate is about

standard error = sqrt( p × (1 − p) / n )

For our run, p is about 0.6 (as the next chapter will show for tokenize) and n is 1,804. That gives sqrt(0.6 × 0.4 / 1804) = about 0.0115, or 1.2 percentage points. A rough 95% range is about twice that: plus or minus 2.3 points. So "tokenize takes 60.6% of the time" really means "between about 58% and 63%". For a function that shows 1% of the samples (18 samples), the error is about 0.23 points, which is nearly a quarter of its own size: a small function's share is far less certain than a large one's. (This formula assumes the samples are independent random draws. Real samples are not perfectly random, so treat it as a rough guide.)

This gives two practical rules:

1. To see small things, take more samples: run longer, or sample faster. The error shrinks with the square root of n: four times as many samples halve the error.
2. Do not read meaning into differences smaller than the margin. A function at 5.2% and another at 5.8% are, in this profile, the same.

There is a deeper idea too. A sampling profiler trades detail for low overhead. It never touches your code. It adds little to the run time (I did not measure the overhead for this run). In exchange, it cannot give you exact counts. It can tell you where the time goes, not how many times a function was called. This is the right trade for "where?", the wrong one for "how many?". That is why we keep several tools.

What would make a sampling profile wrong? Bias. If something in your program happens at the same rhythm as the sampling timer, you can be fooled. Skid blames the wrong instruction. And a timer-based sample (cpu-clock) may be delivered only when the kernel is able to interrupt, which can slightly shift samples away from the exact moment. Hardware-event sampling and tools with more careful machinery reduce this but never remove it.

Common mistakes

• Not building with debug info and frame pointers. You get flat, nameless results or empty stacks.
• Reading perf report without --no-children and not knowing which column is which. Know whether you are reading self or inclusive time.
• Believing tiny differences. Compute the margin.
• Forgetting the kernel. Page faults, system calls, and scheduling show up as [k] entries.
• Assuming hardware counters exist. Check with perf stat -e cycles true.
• Profiling a run that is too short. A 10 ms run gives only 20 samples.

Say it simply

perf stat counts events for a whole run. perf record samples the program about 2,000 times a second and perf report shows where the samples fell. Our word counter showed about 300 MiB of page faults, a lot of time in the allocator, and no single dominant function. A sampling profile is a poll, so its error is about the square root of p(1−p)/n: with 1,800 samples a 60% share is good to about 1 point, but a 1% share is not. Inlined functions vanish from profiles unless you stop the inlining.

Check yourself

Exercise 15.1 (Warm-up): Margin of error. A profile has 400 samples, and function F has 40 of them (10%). What is the standard error, and a rough 95% range? How many samples would you need to get the range down to plus or minus 1 point?

Exercise 15.2 (Warm-up): Read the stats. A program shows task-clock of 2,000 ms, "0.35 CPUs utilized", and 2,300 context switches. What does it suggest about where the time goes? What would you check next?

Exercise 15.3 (Core): Profile it yourself. Build the word counter with frame pointers, record it at 999 Hz and 1999 Hz, and compare the top five self-time entries. How much do the percentages move between the two runs? Is that about what the margin of error says? Done when: a table of both runs and a note on which differences are bigger than the margin.

Exercise 15.4 (Core): Find the page faults. In your profile, find the [k] entries. What fraction of samples is in the kernel? Use perf stat to get the page-fault count, then multiply by 4 KiB. Does it match the peak memory use you see in /usr/bin/time -v ("Maximum resident set size")?

Exercise 15.5 (Core): Watch inlining. Remove #[inline(never)] from the four functions, build, and profile again. Which names vanish? Now use perf annotate on wf::main to find the lines that belong to the inlined functions.

Exercise 15.6 (Stretch): Compare the sampling event. If you have a machine with working hardware counters, record with -e cycles and with -e cpu-clock. Do the profiles differ? Where, and why?

Exercise 15.7 (Stretch): Design and defend. You must profile a program that runs for 50 ms. List three ways to get a meaningful profile, and what each one costs.

What a strong answer includes: run it in a loop many times, raise the sampling rate, use a simulator or instrumentation for exact counts, and the cost of each (cache warming effects, higher overhead, slower runs).

Chapter 16. Flamegraphs, from folded stacks to a picture

In this chapter: You will learn how a flamegraph is made, step by step, from the raw samples to a picture, by building one from real data. You will learn to read the numbers behind the picture. And you will see how to add up shares by theme ("everything that allocates"), which no single-function table can show you.

You need first: Chapter 15.

The problem first

A table of self-time, like the one in Chapter 15, answers: "which functions' own code takes the most time?" But our biggest question is different: "how much time is spent in tokenize including everything it calls?" And: "how much time is spent in the allocator, no matter who called it?" The table cannot answer, because the allocator's time is split across many callers.

We need to keep the stacks, not just the top function. A flamegraph is a way to see all stacks at once.

The model (the "what")

A flamegraph is a picture of all the sampled stacks, merged. Brendan Gregg invented it (reading list). Here is how it works.

1. Take all the stack samples. A stack looks like main → tokenize → to_lowercase → malloc.

2. Fold them: write each distinct stack as one line, with the count of how many samples had exactly that stack. This is called the folded stack format:

   main;tokenize;to_lowercase;malloc 50
   main;tokenize;to_lowercase 60
   main;count;hash_one 43

   Functions are separated by ;, from the outermost (left) to the innermost (right). The number is the sample count for exactly that stack.

3. Draw: each function becomes a box. A box's width is the number of samples that had it on the stack (inclusive time). A box sits on top of its caller. The x-axis is not time: boxes are sorted alphabetically, so that identical stacks merge. The y-axis is stack depth.

 width = samples where this function was on the stack
 ┌──────────────────────────────────────────────────────────────┐
 │                           main                               │   ← depth 0
 ├────────────────────────────────────┬──────────────┬──────────┤
 │             tokenize               │    count     │  top     │   ← depth 1
 ├──────────────────────┬─────────────┼──────┬───────┴──────────┤
 │      to_lowercase    │  from_iter  │ hash │   entry          │   ← depth 2
 ├──────────┬───────────┴─────────────┘      │                  │
 │  malloc  │ ...                            │                  │   ← depth 3
 └──────────┘                                └──────────────────┘

How to read it: look for wide boxes, especially wide boxes at the top (these are functions doing work themselves, without handing it off). A wide box low in the picture is a manager (main). A wide box near the top is a worker. The picture answers "who is expensive?" and "who called it?" at a glance.

What the colors mean: usually nothing. They are random shades of warm colors, to make neighbors easy to tell apart.

Build it (the "how")

The tools: perf script writes the samples as text. A Rust tool called inferno (cargo install inferno) turns them into folded stacks and into a picture. The pipeline is:

perf script -i wf.data | inferno-collapse-perf > wf.folded
inferno-flamegraph < wf.folded > wf-flamegraph.svg

This produced a file of 140 distinct folded stacks, with a total weight of 0.902 s (the weights in this file are in nanoseconds, one sample is about 0.5 ms at 1,999 Hz; the sum, 0.90 s, is a little above the 0.82 s unprofiled run, and I did not check why). The picture, as an SVG file, is attached to this guidebook (wf-flamegraph.svg). Open it in a browser. You can click a box to zoom in. But the text version, the folded file, holds the same facts, and it is the thing you can compute with. Here are the heaviest folded stacks, with the runtime prefix (_start, main, lang_start, ...) removed, and the weight turned into milliseconds:

  106.6 ms  wf::tokenize
   60.0 ms  wf::tokenize;alloc::str::<impl str>::to_lowercase
   55.0 ms  wf::tokenize;<String as FromIterator<char>>::from_iter
   50.0 ms  wf::tokenize;to_lowercase;malloc;_int_malloc
   49.0 ms  wf::count;hashbrown::rustc_entry
   43.0 ms  wf::count;hashbrown::rustc_entry;core::hash::BuildHasher::hash_one
   32.5 ms  wf::tokenize;to_lowercase;malloc
   31.5 ms  wf::tokenize;from_iter;RawVec::reserve::do_reserve_and_handle;finish_grow ...

Each line is one exact stack. For example, the first line says: "106.6 ms were spent with tokenize as the innermost function": that is tokenize's own work (self time). The fourth says that 50 ms were spent in _int_malloc, called by malloc, called by to_lowercase, called by tokenize.

Now we add up, using plain text tools on the folded file. This is where the folded format shines. The inclusive time of a function is the sum of every line whose stack contains it.

awk '/wf::tokenize/ {s+=$NF} END {print s}' wf.folded     # and so on

Result, as a share of the total weight:

Read this slowly, because it is the heart of the profile:

• My hypothesis was wrong. I guessed that the hash map (count) was the main cost. It is 24.5%, a quarter. The real leader is tokenize at 60.6%, which is just splitting text and lowercasing it. Anyone who spent two days replacing the hash map would have found a 3% speed-up in the best case. (By Amdahl's law from Chapter 1, even a map that took zero time would give at most 1 / (1 − 0.245) = 1.32x.)
• A theme cuts across the functions. One third (32.5%) of the whole run has the allocator on the stack. That is malloc and free, called from tokenize, from count, and from elsewhere. In a function-by-function table, no single entry would show it. Only the folded stacks let us add it up.
• Page faults are 14.3%. The kernel's work to give the program fresh memory. It is another sign that the program uses far more memory than it needs.
• About 11.6% is in stacks that go through none of the four phase functions. I did not break that down. Likely candidates are the cleanup at the end of main (freeing the 5 million tokens) and the program's startup. That is a hole in my profile, and it is the kind of thing I would chase next if I needed to.

The margin of error from Chapter 15 applies: with 1,804 samples, the 60.6% for tokenize is good to about plus or minus 2.3 points.

Reading the picture, in words

If you open the SVG, you will see this shape. A wide base (main). Above it, three boxes: a very wide one for tokenize (about three fifths of the width), a medium one for count (a quarter), a thin sliver for make_text. On top of tokenize there are towers: to_lowercase with malloc on top of it, from_iter with reserve and finish_grow on top of it. These towers all end in the allocator. The allocator is the "ground floor" of the cost: tokenizing is expensive mostly because of the memory it asks for, not because of text work.

Why it is this way (the "why")

Why does the folded format work so well? Because a tree of costs can be rebuilt from its paths. Every question you might ask about inclusive and self time is a sum over lines of the file. A flamegraph is just a picture of the sums. Once you see this, you do not depend on the picture: you can make your own tables, filter by any word, and compare two runs.

That last idea is powerful. A differential flamegraph takes the folded files of two runs (before and after a change) and colors the boxes by how much they grew or shrank. The tool for it is inferno-diff-folded. The question it answers is not "what is slow?" but "what changed?", which is often the more useful one.

There is also a philosophical point about where to look first. A table of self-time directs your eyes to the leaves of the tree, the functions where the CPU actually was. A flamegraph directs your eyes to the structure: which whole subtree is big. Real fixes usually come from the structure. Making malloc faster is a small win. Calling malloc fewer times is a big one. You can only see that if you see who calls it. This is why many performance engineers start with a flamegraph, even though the numbers could be read from text.

What would make this wrong?

• The x-axis is not time. Two boxes side by side were not necessarily next to each other in time. A flamegraph hides when things happen. If your program has phases (first parse, then analyze), a flamegraph merges them. Chapter 17 shows a timeline view for that.
• Missing frames (no frame pointers, or code without debug info) give incomplete stacks and boxes labeled [unknown].
• Very short, very frequent functions may be so thin you cannot see them, yet add up.
• Inclusive time can double-count recursion, if a function appears on a stack many times. Most tools handle this, and you should check how yours does.

Common mistakes

• Reading the x-axis as time.
• Reading only the widest box and ignoring the structure under it.
• Comparing flamegraphs with different sample counts without normalizing.
• Ignoring kernel frames like page faults.
• Making decisions from a single flamegraph of a short run.
• Forgetting the margin of error when comparing two boxes of similar width.

Say it simply

A flamegraph merges all the sampled stacks into one picture: a box's width is the share of samples with that function on the stack, and its position is its place in the call chain. The text behind it, the folded stack file, holds one line per distinct stack, and inclusive time is the sum of the lines that contain a function. For our word counter, the map I suspected was 24.5% of the time, tokenizing was 60.6%, and the allocator was on the stack in a third of all samples. Flamegraphs show structure, but they hide time order.

Check yourself

Exercise 16.1 (Warm-up): Fold by hand. These five samples were taken: a;b;c, a;b;c, a;b;d, a;e, a;e. Write the folded lines. What is the inclusive share of b? Of c? What is the self share of a?

Exercise 16.2 (Warm-up): Read the boxes. In a flamegraph, box X is wide and sits directly under a wide box Y, and there is nothing above Y. Which one is doing the work itself?

Exercise 16.3 (Core): Make your own flamegraph. Install inferno, run the pipeline on your own profile of the word counter, and open the SVG. Find the malloc towers. Then compute the inclusive shares from the folded file with awk and compare with the table above. Done when: an SVG, a table of shares, and a sentence for each place your numbers differ from the table.

Exercise 16.4 (Core): Write the folder. Write a small Rust program that reads perf script output (or a simpler text format you invent) and produces folded stacks, then computes inclusive and self time for every function. Check it against inferno-collapse-perf.

Exercise 16.5 (Core): Theme sums. Using the folded file, compute: (a) the share of stacks with hash_one on them; (b) the share with memcmp; (c) the share with memmove or memcpy. Which "theme" is bigger than you expected?

Exercise 16.6 (Stretch): Differential flamegraph. Make a change to tokenize (for example, avoid one allocation), profile again, and use inferno-diff-folded to compare. Which boxes shrank? Did anything grow?

Exercise 16.7 (Stretch): Design and defend. A flamegraph of your server shows a wide epoll_wait box on top, taking 70% of the width. Your colleague says "that's the bottleneck". Explain what is probably going on, what a CPU-time flamegraph cannot show, and what other kind of profile you would take.

What a strong answer includes: waiting versus computing, the idea of off-CPU profiling, and the difference between "time on the stack" and "time the CPU was working".

Chapter 17. Samply and timeline profiling

In this chapter: You will learn what a timeline profile shows that a flamegraph cannot, and how to record one with samply. I will be honest about what I ran in this sandbox (the recording) and what I did not (the graphical viewer).

You need first: Chapters 15 and 16.

The problem first

Chapter 16 ended with a warning: a flamegraph merges time. Our word counter has four clear phases that run one after another: make the text, tokenize, count, report. In a flamegraph, they are four boxes side by side, in alphabetical order, and you cannot tell which came first or how they overlap.

For a one-thread program with simple phases, that is fine. For a program with several threads, a thread pool, a startup phase, a long steady state, or a pause every few seconds, when things happen is the whole story. You need a timeline.

The model (the "what")

Samply is a sampling profiler for Rust (and any native program) that records stacks like perf does, but packs the result into a format that a web viewer can open: the Firefox Profiler. In the viewer you can see:

• a call tree (like our folded stacks, but clickable),
• a flame graph,
• an inverted call tree (start from the functions with the most self time and click down to their callers),
• and the stack chart / timeline: the time on the x-axis, with a row per thread, and the call stack shown over time.

The timeline view answers "what was thread 3 doing between second 10 and second 12?" That is a different question from "where does the program spend its time overall?"

Samply uses the same kernel facility as perf on Linux, so it has the same requirement: permission to open performance events. It samples at a fixed rate. The default is 1,000 Hz (one sample per millisecond). It also works on macOS, where perf does not exist, which is a big reason many people use it.

Build it (the "how")

Install.

cargo install samply --locked

This was the slowest install of the whole project. Samply 0.13.1 pulls in a web server and many other crates, and on this 1-core VM the build took well over ten minutes (my first attempt was cut off by the sandbox, and the second finished). On a normal laptop it takes a minute or two. I mention it so you are not surprised.

Permission. The first time I ran it, samply refused, because perf_event_paranoid was 2, and said what to do. Even though I was root, I had to lower it:

echo 1 | sudo tee /proc/sys/kernel/perf_event_paranoid

Record. Samply normally records and then opens a browser. In a sandbox with no browser, I used the --save-only option, which writes the profile to a file and stops:

samply record --save-only -o wf.samply.json.gz ./target/release/wf

Samply ran the program, and the program printed its normal output. Then I opened the saved file with a few lines of Python to see what was in it:

interval ms: 1.0 | product: wf
thread 'samply'   samples=    0  span=    0.0 ms
thread 'wf'       samples=  863  span=  867.7 ms

What this tells us:

• A 1 ms sampling interval, as promised.
• 863 samples over 867.7 ms: almost exactly one sample per millisecond, with none missing. The program was running the whole time.
• There are two "threads" in the file. One is wf, our program, with all 863 samples. The other is samply, the profiler's own helper, with none. Our program has one thread, so a timeline would have one row.

What I did not do. I did not open the viewer. This sandbox has no browser, so I cannot tell you what the picture looked like, and I will not describe it as if I had seen it. On your own machine, you would run samply record ./target/release/wf (or samply load wf.samply.json.gz for a saved file), and a browser tab would open on the profile. Exercise 17.3 walks you through what to look for.

What you would see, from what we know. From the flamegraph and the instrumentation, the timeline of a single thread would show four blocks in order: a short make_text block (a few percent), a long tokenize block (about 60%), a count block (about a quarter), and nothing for top. If it does not look like that, the profile and the other tools disagree, and that is a result worth chasing. (This paragraph is a prediction, not an observation.)

Why it is this way (the "why")

Why do we need so many views of the same data? Because a profile is a very large table of samples, and every view is a different way of grouping it. A flame graph groups by call path and throws away time. A timeline groups by time and keeps the path. A table of self time groups by function and throws away the path. Each loses something to make something else easy to see. The skill is knowing which question you are asking and picking the grouping that fits.

Another reason to like samply is ease of use, which is a real performance feature of a tool. The easier a tool is, the more often it gets used. A tool that takes 15 steps to set up gets used only in emergencies. A tool that is one command gets used on Tuesday afternoon, when the problem is small and the fix is cheap. People who profile often build better intuition, which is worth more than any single profile.

There is also a philosophical point in the choice between tools that sample hardware events and tools that sample on a timer. Hardware sampling (events like cycles) follows the work the CPU does. Timer sampling follows wall time. For a CPU-bound single thread, they agree. For a program that sleeps or waits, they differ a lot. "Where does the CPU spend its time?" and "where does the program spend its time?" are two different questions. Know which one you asked.

What would make this view wrong? A timeline made from sampling at 1 ms cannot show anything shorter than about a millisecond. A 200 µs stall that happens 100 times will look like noise, or be invisible. For that, you need tracing (recording every event with a timestamp), which is a different kind of tool with a much higher cost.

Common mistakes

• Using a flamegraph for a question about time order. Use a timeline.
• Forgetting that sampling cannot see short events.
• Leaving out debug info. The viewer then shows addresses instead of names.
• Profiling with a different build than you run.
• Not checking permissions first. A permission error costs nothing to fix, once you know about it.

Say it simply

A timeline profile keeps the time order that a flamegraph throws away, which matters when a program has phases or many threads. Samply records like perf but saves a file that the Firefox Profiler can show as a call tree, a flame graph, and a timeline. In this sandbox, samply recorded 863 samples over 868 ms at 1 ms spacing, but I could not open the viewer, so I only show what the file contains. Pick the view that matches the question.

Check yourself

Exercise 17.1 (Warm-up): Which view? For each question, say flame graph, timeline, or table: (a) "What is the single most expensive function?" (b) "Does the program stall every 5 seconds?" (c) "Which thread is idle while the others work?" (d) "Which call path leads to the most allocations?"

Exercise 17.2 (Warm-up): Sampling rate. A stall in a program lasts 300 µs and happens 50 times in a 10 s run. With a 1 ms sampling interval, about how many samples would land inside stalls? Would you see it?

Exercise 17.3 (Core): Open the viewer. Install samply on your machine, record the word counter, and open the profile. Find: (a) the four phases on the timeline, in order, (b) the inverted call tree with malloc at or near the top, (c) the flame graph. Write down one thing you can see in the timeline that you could not see in the flamegraph from Chapter 16.

Exercise 17.4 (Core): A phase that hides. Change main so it runs tokenize and count ten times in a loop, and profile it. How does the timeline look compared with the flamegraph? Do both views agree on the shares?

Exercise 17.5 (Stretch): Two threads. Split the counting into two threads, each handling half the tokens, then merge. Profile with samply. Which thread finishes first? Is there a gap where one thread waits for the other? (You will need this skill in Part VI.)

Exercise 17.6 (Stretch): Design and defend. You want to find out why a game drops a frame once every few seconds. Which tool kinds from Chapter 14 would you use, in which order, and what would each one rule in or out?

What a strong answer includes: a timeline to find when the drop happens, event counters or allocation tracking to look for a periodic cause (garbage collection or a big allocation), instrumentation of the frame loop with exact timestamps, and the point that a sampling rate of 1 ms may miss short spikes.

Chapter 18. Instrumentation without fooling yourself

In this chapter: You will learn when to measure by adding code rather than sampling, how the hotpath crate does it with two attributes, and how to measure allocation per function. You will meet a case where two tools gave different answers for the same function, and learn what to do about it.

You need first: Chapters 14 to 17.

The problem first

Sampling is great for finding hot spots you did not suspect. But it has weak spots: it cannot give exact call counts, and you cannot ask it "how many bytes did this function allocate?" It cannot measure an operation that is not CPU time, such as the time between two events.

When you want exact answers about regions you already know about, you add code that measures them. This is instrumentation.

The model (the "what")

Instrumentation means inserting measurement code into the program, either by hand or with a macro. The simplest version is two clock reads:

let t = std::time::Instant::now();
let tokens = tokenize(&text);
eprintln!("tokenize: {:?}", t.elapsed());

This works, and it is how every one of us starts. Its problems appear when the program grows: you have to edit many places, remove the lines afterwards, and keep the measurements consistent (count, total, percentiles).

The hotpath crate does the bookkeeping. It provides:

• #[hotpath::main] on main: starts a background collector and prints a report at the end.
• #[hotpath::measure] on any function: records the start and end time of every call.
• A way to turn everything off at compile time with a Cargo feature, so that normal builds pay nothing.
• Optional allocation tracking: how many bytes, and how many allocations, each function made.

The cost of instrumentation is per call. The project's documentation says #[hotpath::measure] adds around 40 ns per call (I read this, I did not measure it). That is nothing for a function called once and taking 500 ms. It is huge, relatively, for a function called 100 million times and taking 5 ns. So instrument the large pieces, not the tiny ones. For tiny, hot functions, use sampling.

Build it (the "how")

Add the crate with a feature gate

cargo add hotpath --optional

Cargo added hotpath v0.28.2. Then in Cargo.toml:

[features]
hotpath = ["dep:hotpath", "hotpath/hotpath"]

Here is a trap that cost me a few minutes, so I will share it. My first version of this line was hotpath = ["dep:hotpath"]. The program built and ran, but printed no report at all. No error, no warning. The reason: the hotpath crate has its own feature named hotpath, and without it, the whole library compiles to nothing (that is how it gets zero cost). Your feature must switch on the crate's feature too, which is the "hotpath/hotpath" part. A silent no-op is the worst kind of bug in a measuring tool. If your measurement tool prints nothing, do not believe "nothing happened": check that it was switched on. In Part I, we said the same about a benchmark with no black_box.

Then mark the functions:

#[inline(never)]
#[cfg_attr(feature = "hotpath", hotpath::measure)]
fn tokenize(text: &str) -> Vec<String> { /* ... */ }

// the same for make_text, count, and top

#[cfg_attr(feature = "hotpath", hotpath::main)]
fn main() { /* ... */ }

cfg_attr(feature = "hotpath", ...) means "apply this attribute only when the feature is on". When it is off, the code is exactly the original.

Run it:

cargo run --release --features=hotpath

The report

[hotpath] 877.92ms | timing, threads

timing - Execution duration of functions.
+---------------+-------+-----------+-----------+-----------+---------+
| Function      | Calls | Avg       | P95       | Total     | % Total |
+---------------+-------+-----------+-----------+-----------+---------+
| wf::main      | 1     | 877.84 ms | 878.18 ms | 877.84 ms | 100.00% |
| wf::tokenize  | 1     | 529.09 ms | 529.27 ms | 529.09 ms | 60.27%  |
| wf::count     | 1     | 209.26 ms | 209.32 ms | 209.26 ms | 23.84%  |
| wf::make_text | 1     | 62.61 ms  | 62.62 ms  | 62.61 ms  | 7.13%   |
| wf::top       | 1     | 13.05 µs  | 13.05 µs  | 13.05 µs  | 0.00%   |
+---------------+-------+-----------+-----------+-----------+---------+

(I removed the separator lines between rows. The numbers are as printed.)

Exact times, and the calls column: each function was called once. A sampling profiler could not have told us that. These are inclusive times: wf::main includes everything.

Allocation tracking

cargo run --release --features="hotpath,hotpath/hotpath-alloc"

This adds a table of bytes allocated by each function (not counting what its callees allocate):

alloc-bytes - Exclusive allocation bytes by each function (excluding nested calls).
Total: 515.7 MB
| wf::tokenize  | 1 | 451.3 MB | ... | 451.3 MB | 87.52% |
| wf::make_text | 1 | 38.1 MB  | ... | 38.1 MB  | 7.40%  |
| wf::count     | 1 | 26.2 MB  | ... | 26.2 MB  | 5.09%  |
| wf::main      | 1 | 1.3 KB   | ... | 1.3 KB   | 0.00%  |
| wf::top       | 1 | 975 B    | ... | 975 B    | 0.00%  |

This is a why. The program allocates 515.7 MB of memory in total, to process 5 million words. 87.5% of it, 451 MB, comes from tokenize. That is about 90 bytes allocated per token (451.3 MB / 5 million). And the largest peak memory use was about 300 MB (the report's "Max RSS" line said 303.7 MB), which matches the page faults from Chapter 15.

Put the three tools together now, because this is how a profile report is made:

The four rows tell one story: tokenizing is slow mostly because it allocates a lot. And that suggests a plan (Part V): allocate less.

Where the tools disagree

Not everything lined up. Look at make_text:

Both say "small". But the second is twice the first, and it moves between runs. I do not have a confirmed reason. A guess: make_text builds a 38 MB string, so its time includes a lot of first-touch page faults, which are kernel work. My folded stacks might have attributed some of that kernel time to a stack that does not pass through wf::make_text, which would make the sampling number too low. A different guess: the instrumented run waits for something extra at its start. I did not test either. What I will say is: when two tools disagree about a small share, the honest answer is the range, not a favorite. And note the instrumented run with allocation tracking was slower (1.03 s against 0.88 s): tracking every allocation is not free. So we do not trust absolute times from that run, only the byte counts.

Why it is this way (the "why")

Why have both sampling and instrumentation? Because they make opposite trades.

• Sampling looks at everything but only occasionally. It finds things you did not think of. It is statistical and approximate. It costs little.
• Instrumentation looks at only what you marked but at every moment. It is exact. But you must know what to mark, and it costs per call.

You can think of it as a police officer on patrol (sampling: sees the whole town, a bit at a time) against a security camera at one door (instrumentation: sees everything at that door, and nothing elsewhere). A good investigation uses both. The patrol tells you which door to put the camera on.

There is also an old idea in physics that applies here: the observer effect. To measure something, you must touch it, and touching changes it. A timer call takes about as long as a few dozen instructions. If the function you are measuring is that short, you are mostly measuring the timer. We saw the same thing in Chapter 4 (the empty closure) and in Chapter 1 (121 ns for a deleted loop). So, as with every measuring tool in this guidebook, test the instrument on something you know. If I mark an empty function and the report says 40 ns per call, that is the overhead, and I must subtract it, or avoid measuring things that small.

The philosophy is "measure one level deeper" (Ousterhout, reading list for Part I): when you find a slow piece, do not guess why. Instrument the pieces under it. The allocation table was exactly this: we had a slow function, and we measured one level deeper, what it allocates, and got a reason.

What would make instrumentation wrong? Measuring inside a loop that is very hot, so that the instrument becomes the cost. Measuring something that gets inlined (the macro may prevent inlining, changing the program). Forgetting that thread-related and async code needs special care (hotpath has separate features for these). And using the numbers from a run with extra tracking turned on as if they were normal timings.

Common mistakes

• A feature that silently does nothing. Verify that your tool printed something.
• Instrumenting tiny functions called millions of times. The overhead is the result.
• Using numbers from an instrumented run as production timings.
• Forgetting the call count. Total time alone hides "called once, slow" versus "called a million times, fast".
• Choosing one tool's number when two tools disagree. Report the range and say why you think they differ.

Say it simply

Instrumentation adds code that measures what you point it at: exact times and counts, but only for the pieces you marked and with a small cost per call. The hotpath crate does the bookkeeping with two attributes and a Cargo feature, and can also count bytes allocated per function. For our word counter it showed 515.7 MB allocated, 87.5% of it in tokenize: a reason, not just a location. When two tools disagree on a small share, report the range. And check that a tool that prints nothing was really switched on.

Check yourself

Exercise 18.1 (Warm-up): Overhead budget. An instrument adds 40 ns per call. A function takes 20 ns and is called 100 million times. By how much does the instrument change the run time? What if the function takes 5 µs and is called 1,000 times?

Exercise 18.2 (Warm-up): Which tool? Choose sampling or instrumentation: (a) "Where is the time going in a program I have never seen?" (b) "How many times is this parser function called per request?" (c) "What is the p99 time of this one function?"

Exercise 18.3 (Core): Measure the instrument. Add the crate to a copy of the program. Mark an empty function (fn nothing() {}) and call it 1 million times. Compare the total time with and without the feature. What is the overhead per call on your machine? Done when: a number in nanoseconds, and a sentence saying how it compares with the documentation's figure.

Exercise 18.4 (Core): Reproduce the allocation table. Run the allocation-tracking build on your machine. Do your byte totals match 515.7 MB? Change the input to 10 million words. Do the bytes double?

Exercise 18.5 (Core): The silent failure. Remove the "hotpath/hotpath" part of the feature and rebuild. Confirm the report disappears. Write two sentences on why a measuring tool that fails silently is dangerous.

Exercise 18.6 (Stretch): Do it by hand. Write your own mini measure! macro that records the count and the total time of each labeled region in a global table and prints it at exit. Test it on the word counter. How does its overhead compare with hotpath?

Exercise 18.7 (Stretch): Design and defend. Two profilers disagree: one says a function takes 3% of the run, the other says 9%. Write a plan with at least three experiments to find out which is right, or why both are.

What a strong answer includes: checking for inlining, testing overhead on a known workload, comparing user versus kernel time, running more samples, and looking at what each tool counts (CPU time against wall time, self against inclusive).

Chapter 19. Top-down analysis and the roofline model

In this chapter: You will learn the two big models professionals use to say what is limiting a program: the top-down method (what the CPU pipeline is waiting for) and the roofline (compute-bound or memory-bound). I will show what I could not run (top-down needs hardware counters). And I will build a roofline from scratch, from my own measurements, on this machine.

You need first: Chapters 8 to 13 and 14 to 18.

The problem first

By now we know where the time goes, and some of the why. But there is a deeper kind of question: what is the limit? If a loop is slow, is it slow because the CPU has too little work to overlap, because it waits for memory, because the branches are unpredictable, or because it is simply doing a lot of arithmetic? The fix for each one is different. A wrong guess wastes a week.

Two models answer it. One looks inside the CPU pipeline. The other looks at the balance between arithmetic and data.

The model (the "what")

Part A: the top-down method

Chapter 13 described a CPU as an assembly line with a fixed width: each cycle it has a number of slots (say, 4 or 6) in which it could start a useful instruction. A perfect program fills every slot every cycle. A real one loses slots. The top-down method (Ahmad Yasin, ISPASS 2014; reading list) asks, for every lost slot: why was it lost? It sorts every slot of every cycle into exactly one of four buckets:

                   all pipeline slots
        ┌───────────────┬─────────────────────────────┐
        │               │                             │
     RETIRING      NOT RETIRING (wasted)
   (useful work)   ┌─────────────┬──────────┬────────────────┐
                   │             │          │                │
              BAD SPECULATION  FRONTEND   BACKEND
              (guessed wrong:  BOUND      BOUND
               work thrown     (can't get (can't finish:
               away)           instructions waiting for data
                               fast enough) or for a free unit)

• Retiring: slots that did useful work that was kept. Higher is better. (But 100% retiring on a bad algorithm is still slow: it only says the CPU is busy, not that the work is needed.)
• Bad speculation: slots wasted on work that was thrown away after a branch misprediction (Chapter 13).
• Frontend bound: the CPU's "fetch and decode" part could not supply instructions fast enough. Often caused by a big, branchy code footprint that does not fit in the instruction cache.
• Backend bound: instructions were ready, but the "execute" part was stuck. This one splits again:
  • Memory bound: waiting for data from the caches or main memory (Chapters 8 to 12).
  • Core bound: waiting for a free execution unit, or for the result of a long dependency chain (Chapter 13).

The method is top-down because you start with these four big buckets, find the biggest wasted one, and drill down into just that one with more detailed counters. You do not drown in 500 counters. You follow a tree.

On real hardware with the counters exposed, Linux perf can compute the first level for you:

perf stat --topdown ./program        # or:  perf stat -M TopdownL1 ./program

and its output is a line per bucket: retiring, bad speculation, frontend bound, backend bound, as percentages. (The Linux kernel change that added this to perf stat printed an example with four percentages in this order.) I could not run this here, because the VM does not expose the counters:

   <not supported>      cycles
   <not supported>      instructions

So I cannot tell you, from a measurement, what the word counter's top-down breakdown is. A guess, based on everything else we saw (heavy allocation, hash-map lookups of random strings, many small copies): the backend, specifically memory, would be the biggest wasted bucket. Treat that as a hypothesis to test on real hardware. Exercise 19.4 does that.

Part B: the roofline model

The roofline model (Williams, Waterman, and Patterson, CACM 2009; reading list) takes a different, simpler view. It says: every loop has two limits.

1. A compute limit: the machine can do at most P floating-point operations per second (flop/s). This is the peak compute rate.
2. A memory limit: the machine can move at most B bytes per second to and from main memory. This is the peak bandwidth.

Now take a loop and define its arithmetic intensity I: the number of floating-point operations it does per byte it moves from memory. (flop/byte.) Then the best speed the loop can reach is:

 attainable flop/s  =  min( P ,  B × I )

If the loop does little work per byte (low I), it is limited by B × I: memory-bound. If it does a lot of work per byte (high I), it hits the flat ceiling P: compute-bound. Drawn on a log-log plot, the line B × I rises like a slanted roof and then meets the flat ceiling P. The picture looks like a roof, which gives the model its name:

 flop/s
   ▲                         ________________  ← compute roof  P
   │                      ╱
   │                   ╱
   │                ╱   ← slanted roof  B × I   (bandwidth limit)
   │             ╱
   │          ╱
   └───────────────────────────────────►  intensity  I  (flop/byte)
                  ▲
               the "knee": where the loop switches from memory-bound to compute-bound

The point of the model: it tells you which fix to try. A loop on the slanted part gains nothing from faster arithmetic (vectorization, more accumulators). It needs less data movement (smaller types, better layout, cache blocking). A loop on the flat part gains nothing from better memory access. It needs faster arithmetic (SIMD, FMA instructions, more independent chains).

Build it (the "how")

I did not have hardware counters, so I measured the roofline directly, with a small kernel whose arithmetic intensity I can set. For every number loaded from memory, the kernel does K multiply-add steps (each is 2 flops), plus one add into a running total. So the flops per element are 2K + 1, and the bytes per element are 8 (one f64). Turn K up, and the intensity goes up.

// For every number we load, do K multiply-adds, then add the result to a running total.
// flops per element = 2*K + 1 ; bytes per element = 8 (one f64 read).
#[inline(never)]
fn kernel<const K: usize>(x: &[f64], a: f64, b: f64) -> f64 {
    let mut s = [0.0f64; 32];
    for ch in x.chunks_exact(32) {
        let mut v = [0.0f64; 32];
        v.copy_from_slice(ch);
        for _ in 0..K {
            for i in 0..32 { v[i] = v[i] * a + b; }   // 32 independent chains
        }
        for i in 0..32 { s[i] += v[i]; }
    }
    s.iter().sum()
}

I ran it on two array sizes: 16 KiB (fits in L1, so the data is always close: this finds the compute roof) and 256 MiB (main memory: this finds the memory roof). And I built it two ways: the default rustc build, and with -C target-cpu=native, which lets the compiler use every instruction this CPU has (on this machine: AVX2, AVX-512, and FMA, according to /proc/cpuinfo).

A story about getting it wrong first. My first version of the kernel used only four independent chains. At large K, its speed fell (from 16 to 4 GFLOP/s) instead of reaching a flat ceiling. The reason: with only four chains, the loop was limited by the latency of the multiply-add chain (Chapter 13), not by the arithmetic units. Four chains were not enough work to overlap. I was measuring a latency limit and calling it the compute roof. With 32 chains, the speed rose and flattened, as a roof should. The lesson: to find a roof, you must give the machine enough independent work. A roof that is too low is a bug in your experiment, not a fact about your CPU.

Results (32 chains). Intensity I is flop per byte. Speeds are GFLOP/s (billions of floating-point operations per second).

And the data rate behind the "memory" columns, in GB/s:

Now read the roofline out of the numbers.

The memory-bound slope (the roof's slanted part). Look at the memory columns at low intensity. At K = 1 (0.38 flop/byte), the default build gets 3.1 GFLOP/s, which is 8.2 GB/s of data. At K = 2, 4.5 GFLOP/s. At K = 4, 6.9. Doubling the arithmetic per byte nearly doubles the speed, because the program is waiting for data, and the extra arithmetic hides inside the waiting. This is the slanted roof: speed grows with intensity. The data rate, around 8 GB/s at the lowest intensity here, is in the same range as the sequential-read bandwidth we measured in Chapter 8 for 256 MiB (9.9 GB/s).

The compute roof (the flat part). For large K, both L1 and memory columns converge on the same number: about 10.6 to 11 GFLOP/s for the default build. When there is a lot of arithmetic per byte, it does not matter where the data lives. The ceiling is the arithmetic units, and that is P.

The knee. For the default build and memory-sized data, the curve reaches the ceiling at about K = 16 (about 4 flop/byte). That is the knee. A loop with an intensity below it is memory-bound on this machine. A loop above it is compute-bound. (The corner is not perfectly sharp in my data: at K = 4 to 8 the loop is both partly limited by memory and partly by arithmetic.)

The L1 line starts above the ceiling. In the L1 column, K = 1 gives 15.8 GFLOP/s, higher than the final roof of 10.6. That is because at tiny K the loop does mostly adds and loads, and (it seems) the machine can do those adds faster than it can do multiply-adds. The "roof" depends on the mix of operations. A roofline uses one number for P, which is a simplification. I did not investigate the exact cause.

The build flags change the roof, not just the loop. The native build's roof (the large-K columns) is 23 to 25 GFLOP/s, against 10.6 for the default build: about 2.2 times higher. Same source code, same CPU. The difference: the default Rust target is a baseline x86-64 CPU (instructions from around 2003, with 2 doubles per SIMD instruction and no fused multiply-add). The native build lets the compiler use AVX-512 and FMA. In the L1 column, the native build reaches 40 GFLOP/s at K = 8, almost four times the default build's roof, before dropping to about 24 for larger K. I do not know why it drops. A guess: heavy 512-bit instructions can make the CPU lower its clock, or the kernel runs out of registers. I did not test it.

The native build has a cost you must know: a binary compiled with -C target-cpu=native may crash with "illegal instruction" on an older CPU. It is for programs that run on the machine they were built on, or for builds that target a known CPU. For software you ship to others, you pick a lower baseline (or build several versions and choose at run time, Chapter 28).

Correction, added after Chapter 30. The "compute roof" I measured above (about 10.6 GFLOP/s for the default build and about 24 for the native build) is not the peak of this machine. In Chapter 30, a tuned matrix-multiplication library reaches about 131 GFLOP/s in f32 on the same single core. So the roofs in this chapter were the roofs of my kernel, which was limited by something other than the arithmetic units (I did not find out what: the kernel did one multiply-add per number and may not have kept the vector units busy). The shape of the roofline (a slanted memory part and a flat compute part, and the knee between them), and the lessons about independent chains and about build flags, still stand. The numbers for the roof do not. Use a strong reference, such as a tuned library, to find the real roof. A roof that is too low is a bug in your experiment, and mine was one.

Why it is this way (the "why")

Why do these two models exist, when we have a profiler? Because a profile tells you where, and these models tell you what limits you there. They are explanations, not measurements. They turn "this loop takes 40 ms" into "this loop is memory-bound at 80% of the bandwidth the machine can give, so rewriting the arithmetic is pointless, and the best you can do is reduce the bytes". That is far more useful. It also gives you something rare in performance work: a stopping rule. If you are at 90% of the roof, you are done. Nobody can make that loop much faster on this machine. If you are at 10% of the roof, there is a big win waiting, and you now know which direction to look in.

The philosophy behind both: performance is a conversation between a program and a machine, and each side has limits. The program has a demand (so many flops, so many bytes, so many branches). The machine has a capacity for each. The slowest match-up wins. The top-down method looks at the match-ups inside the core. The roofline looks at the match-up between arithmetic and bandwidth. A third model, for parallel programs, appears in Part VI.

It is also worth noticing what these models leave out, because that is where they stop being true:

• The roofline has one number for peak compute, but real peaks depend on the instruction mix (we saw it in the L1 column), on SIMD width, and on the clock.
• It has one memory bandwidth, but there are several levels (L1, L2, L3, memory), each with its own roof. A good roofline plot has several slanted lines.
• It counts only floating-point work. Many programs (parsers, interpreters, compilers, our word counter) do almost no floating-point arithmetic. For those, the analogous question is "instructions per byte" or "operations per cache line", and the top-down view is more useful.
• Top-down analysis depends on hardware counters, which are specific to each CPU generation, and which can be inaccurate. It is a guide, not a proof.

Common mistakes

• Taking a roof from a badly built experiment. If the speed falls instead of flattening, you are probably latency-bound. Add independent work.
• Using the roofline for a program with almost no floating-point work. Count something else.
• Treating "retiring is high" as "the program is good". It may be doing useless work efficiently.
• Optimizing arithmetic on a memory-bound loop (or the reverse).
• Benchmarking with default build flags and assuming it is the machine's limit. Our native build was 2.2 times higher.
• Shipping a target-cpu=native binary to machines you do not control.

Say it simply

The top-down method sorts every lost CPU slot into one of four buckets (bad speculation, frontend bound, backend bound, or useful work) and drills into the biggest waste. It needs hardware counters, which this VM did not give me. The roofline model says a loop's speed is the lower of a compute ceiling and the memory bandwidth times its arithmetic intensity. I measured two limits for my own kernel: about 10.6 GFLOP/s for the default build and about 24 for the native build (the real peak of this core is higher, see the correction above), with the loop switching from memory-bound to compute-bound at roughly 4 flop per byte. Knowing the limit tells you which fix to try, and when to stop.

Check yourself

Exercise 19.1 (Warm-up): Memory- or compute-bound? A machine has a peak of 20 GFLOP/s and a bandwidth of 10 GB/s. Where is the knee, in flop/byte? A loop has intensity 0.5. What is its best possible speed? A loop has intensity 8. What is its best speed?

Exercise 19.2 (Warm-up): Intensity by hand. For y[i] = a * x[i] + y[i] with f64 values (each x[i] and y[i] is read, and y[i] is written), count the flops and the bytes per element. What is the intensity? Is it likely memory-bound or compute-bound on the machine in this chapter?

Exercise 19.3 (Core): Build your roofline. Run the roofline experiment on your own machine, in both builds. Draw the two roofs on a log-log plot (or a table). Where are your knees? How do your numbers compare with this machine's 10.6 and 24 GFLOP/s? Done when: a plot or table, your peak compute rate, your memory bandwidth, and one paragraph on how they differ from the tables above.

Exercise 19.4 (Core): Top-down on real hardware. If you have a machine with working counters, run perf stat -M TopdownL1 (or --topdown) on the word counter. Which bucket is biggest? Did the guess in this chapter (backend/memory bound) hold? What does it say about whether to fix allocation or hashing first?

Exercise 19.5 (Core): Break the roof on purpose. Re-run the kernel with only 4 chains, then 8, 16, and 32. Plot the large-K speed against the number of chains. At what number does it stop rising? Connect this to Chapter 13.

Exercise 19.6 (Stretch): Find the build effect. Compile the kernel with -C target-feature=+avx2,+fma instead of native. Where does the roof land? Then with -C target-cpu=native -C target-feature=-avx512f (if your CPU has AVX-512). Which instruction set gave how much?

Exercise 19.7 (Stretch): Design and defend. Your matrix multiplication reaches 30% of the machine's compute roof, and a teammate says "use a faster algorithm". Another says "block it for the cache". Use the roofline to say what you would measure to decide between them.

What a strong answer includes: the arithmetic intensity of the naive and blocked versions, whether the loop sits on the slanted or the flat part, the data volume moved at each cache level, and the idea that if you are on the flat part, blocking helps little. (Chapter 30 does this.)

Chapter 20. Cachegrind and Callgrind

In this chapter: You will learn how to profile a program by simulating it. You will get exact instruction counts and a cache simulation, which the real hardware here would not give us (no counters). And you will see the most important lesson of the Part: instructions are not time.

You need first: Chapters 8 to 19.

The problem first

Part IV has relied on sampling, which is statistical: run it twice and you get slightly different numbers. We also lost the hardware counters. What if we want something exact and repeatable: the same numbers every time, on any machine, even a VM with no counters?

There is a way: run the program not on the real CPU, but on a software simulation of one.

The model (the "what")

Valgrind is a framework that runs your program inside a virtual machine. As the program runs, Valgrind translates its machine code on the fly into instrumented code (this is called dynamic binary instrumentation) and a tool plugs in to count whatever it likes. Two tools matter for us:

• Cachegrind counts, for every instruction and every memory access: how many instructions ran, and, using a simulated cache hierarchy, how many accesses hit or miss in the first-level and last-level caches. It reports these per function and per source line.
• Callgrind does the same and also records who called whom, and the inclusive cost of each function including its callees (like a flamegraph, but in instructions).

Because the simulation is software, the counts are deterministic: the same program on the same input gives (almost) the same numbers, every time. The price: the program runs about 20 to 50 times slower. So you run it on a small input.

The numbers you get are events, in three groups:

• Ir: instructions executed ("instruction reads").
• Dr / Dw: data reads and data writes.
• I1mr, D1mr, D1mw, ILmr, DLmr, DLmw: misses in the first-level instruction or data cache (I1, D1) and in the last-level cache (LL), for reads (r) and writes (w).

An important limit: Cachegrind's cache is a simple model (by default it copies the sizes of your real machine's caches). It has no hardware prefetcher, no TLB, and no out-of-order overlap. So its "misses" are a cleaner, simpler picture than the real hardware. Think of it as a very good approximation for relative questions ("which function misses most?") and a poor one for absolute time.

Build it (the "how")

Run on 200,000 words (instead of 5 million), because of the slowdown:

valgrind --tool=cachegrind --cache-sim=yes ./target/release/wf 200000

Valgrind prints a summary:

I refs:        318,103,054
I1  misses:          2,084
LLi misses:          2,014

D refs:        106,898,142  (64,534,937 rd   + 42,363,205 wr)
D1  misses:        574,963  (   376,084 rd   +    198,879 wr)
LLd misses:        198,114  (     1,777 rd   +    196,337 wr)
D1  miss rate:         0.5%
LL misses:         200,128

What it tells us:

• 318 million instructions for 200,000 words: about 1,590 instructions per word. That is a lot, for a job whose essence is "split, lowercase, count". (This includes building the fake text.) A simple tokenizer should need on the order of 50 to 100 instructions per word. We are at about 15 to 30 times that. (Those "50 to 100" are my rough expectation, not a measurement.)
• Data reads and writes: 107 million, about a third of the instruction count: fine.
• The D1 miss rate is only 0.5%. The simulated L1 data cache hits 99.5% of the time. For a program we already know is slow because of memory behavior, that looks wrong. The reason: 200,000 words is a small input. The working set (about 8 MiB of tokens and text) is small, and the simulator does not model page faults at all. The cache misses are not the problem here, at this size. At 5 million words, the program touches 300 MiB, and the real hardware sees page faults, TLB misses, and cache misses that this small simulation does not. A simulation answers only the question you ask it. We asked "how many instructions, and how well does a small input fit in cache?" and not "how does a 300 MiB working set behave?"

Callgrind: the inclusive costs by function

valgrind --tool=callgrind ./target/release/wf 200000
callgrind_annotate --inclusive=yes callgrind.out.<pid>

With the four phase functions marked #[inline(never)], the inclusive cost in instructions:

So malloc plus free is about 34% of all instructions. And tokenize is the biggest phase, as before.

Now compare instructions with time, from the earlier chapters:

The two views mostly agree: tokenize first, count second, the allocator a third of everything. Good. Two independent methods, one story, which is what we hoped for. But look at count: 30.8% of the instructions but only 24.5% of the time. And tokenize is the opposite: 57.2% of the instructions and 60.6% of the time. In plain words, count's instructions ran faster, on average, than tokenize's. A guess at why: the hash and compare code is tight, with good use of the cache, while tokenize pays more for page faults when it grabs fresh memory and fills a 120 MB vector of strings. (This is a hypothesis. Callgrind does not model page faults, so it cannot see this, and the real-hardware counters that could settle it are not available here.)

This is the great lesson of this chapter: instructions are not time. The CPU can do several instructions per cycle on good code, and fewer than one on code that waits for memory. Two functions with the same instruction count can differ by 5x in time. An instruction profile is exact, but it is a profile of work, not of waiting. A time profile (sampling) is approximate, but it includes the waiting. You need both to see the whole picture.

When is each one best?

The first row deserves a note. In Part II we found that a benchmark on this VM can wobble by 5% between runs, which hides small improvements. An instruction count has almost no noise: two runs of the same binary gave 318,103,054 (Cachegrind) and 318,101,668 (Callgrind), which differ by 0.0004%. (The tools instrument differently, so they are not identical, but a single tool run twice is nearly exact.) That makes it a good check for small regressions in a noisy environment, as long as you remember it measures work, not time. Chapter 38 returns to this idea.

Why it is this way (the "why")

Why simulate? Because a simulation can see everything and is not subject to noise. A real CPU is a black box with noisy, limited counters. A software model has a counter for every event we care about, and those counters are exactly repeatable. The cost is that the model is only as true as its design. A simple model of the cache answers questions about the cache in the model.

This is a recurring theme in science: models trade realism for control. A wind tunnel is not the sky, but you can repeat the experiment a thousand times and change one thing at a time. Cachegrind is a wind tunnel for your program's memory behavior. The question to ask before trusting a result is: what does the model leave out, and could that be what matters here? For Cachegrind, the omissions are the prefetcher, the TLB, page faults, and out-of-order overlap, which are exactly the things Part III showed to be big. So Cachegrind is good for finding wasted work (instructions, accesses that miss in a simple cache) and weak for latency hiding.

Another idea: exactness is a different kind of knowledge from accuracy. Callgrind's count of instructions is exact: it counts every one. But it is an exact count of the wrong thing if what you care about is time. A sampling profile is approximate about the right thing. Neither is "better". An experienced engineer uses an exact count to know what the program does, and a sampled profile to know what it costs.

What would make this wrong? Valgrind changes the program's behavior (it is much slower, and its memory layout differs from native), so threads and timing-dependent code behave differently under it. Valgrind may not support the newest instructions (a program built with target-cpu=native and AVX-512 may not run, or may be translated imperfectly). And a small input may not show the problem of a big one.

Common mistakes

• Running a big input. It will take forever. Use a small, representative one.
• Trusting simulated cache misses as real ones. They are model misses.
• Reading instruction share as time share.
• Forgetting debug info. You get no source lines.
• Using it on multi-threaded timing questions. Valgrind serializes threads.
• Treating a low simulated miss rate as "memory is fine". The model may be missing the real cause (page faults, TLB).

Say it simply

Cachegrind and Callgrind run your program inside a software model of a CPU and count everything: instructions, memory accesses, and simulated cache misses. The counts are exact and repeatable, so they work on noisy machines and VMs with no counters. For the word counter, the allocator was a third of all instructions, and tokenize was 57% of them, close to what sampling said about time. But count had more of the instructions than of the time, which shows that instructions are not time. The model leaves out the prefetcher, the TLB, and page faults.

Check yourself

Exercise 20.1 (Warm-up): Per word. The run had 318,103,054 instructions for 200,000 words. Compute the instructions per word. If you reduce malloc and free instructions to zero, what is the best speed-up, by Amdahl's law, from instructions alone?

Exercise 20.2 (Warm-up): Instruction or time? A function has 30% of the instructions and 10% of the time. Another has 10% of the instructions and 30% of the time. Describe in one sentence what each is probably doing.

Exercise 20.3 (Core): Run Cachegrind. Run Cachegrind and Callgrind on the word counter at 200,000 words. Use cg_annotate to find the line with the most instructions. Does it match the sampling profile? Then try 50,000 and 800,000 words: does the instruction count per word stay the same? Does the D1 miss rate change? Done when: a table of instructions per word and miss rate for three input sizes.

Exercise 20.4 (Core): A noise-free check. Make a tiny change that saves some work in tokenize (for example, call to_lowercase only if the word has an uppercase letter). Compare instruction counts before and after, using Callgrind. Then compare wall time with Criterion (Part II). Which tool can see the change more clearly? By how much did each report?

Exercise 20.5 (Core): Cache model. Run Cachegrind with a smaller simulated cache (--D1=8192,2,64 means 8 KiB, 2-way, 64-byte lines) on the matrix walk from Chapter 9 (row against column). Do the simulated miss counts reproduce the 16x gap? Which part of the gap does the model capture, and which not?

Exercise 20.6 (Stretch): Callgrind graph. Open a Callgrind output in KCachegrind (or callgrind_annotate --tree=caller) and find all callers of malloc. Which caller makes the most calls? How would you reduce them?

Exercise 20.7 (Stretch): Design and defend. Your CI has noisy machines, and you want to block pull requests that make the code more than 3% slower. Argue for or against using Callgrind instruction counts as the gate. What kinds of slowdowns would it miss?

What a strong answer includes: determinism and low noise as strengths, and cache effects, branch mispredictions, memory layout, and allocation latency as things instruction counts cannot see. A balanced approach: instruction counts as a fast first check, real timing on a quiet machine as a second.

Part IV wrap-up

What you can now do:

• Name the six kinds of profiling evidence and pick the right one for a question.
• Use perf stat to count events and perf record to sample, and estimate the margin of error of a sampling profile.
• Make a flamegraph from folded stacks, read it, and compute inclusive time and theme sums yourself.
• Record a profile with samply, and know what a timeline shows that a flamegraph does not.
• Instrument a program with hotpath for exact timing and allocation counts, and check that your instrument is actually switched on.
• Explain the top-down method and the roofline model, and measure a roofline on your own machine.
• Run Cachegrind and Callgrind, and explain why instructions are not time.

What our word counter told us (and what we do next). Five tools, one story:

• The run takes about 0.82 s for 5 million words (164 ns per word).
• tokenize is about 60% of the time and 87.5% of all allocation (451 MB of 515.7 MB, about 90 bytes per token).
• count is about a quarter of the time.
• The allocator (malloc and free) is on the stack in about a third of the samples and takes about a third of the instructions.
• The kernel handles 76,485 page faults (about 300 MiB of fresh memory), about 14% of the samples.
• The hash map, our first suspect, was never the main problem.

The conclusion: this program is slow because it asks the allocator for far too much memory, far too often. The fix is not a smarter algorithm. It is allocating less. That is Part V.

Mini project: The profile report (4 to 6 hours). Pick a program of 100 to 500 lines that you wrote (a parser, an interpreter step, a small simulation), or use the word counter with a change you choose. Produce a one-page profile report that includes:

1. The performance question and a baseline (Part I), measured with the right workload.
2. Your written hypothesis, before profiling.
3. A sampling profile (perf or samply) with a flamegraph and a note on the margin of error.
4. At least one other kind of evidence (instrumentation, counters, allocation tracking, or Callgrind) that explains why the hot spot is hot.
5. One place where two tools disagreed, with your best explanation.
6. A short ranked list of what to change, each with the most it could save by Amdahl's law.