EC-10.4 Measuring Performance Honestly

What this is and why it exists

Performance is the subject where confident wrong answers are most common. Every part of the machine has a plausible story about why it is the bottleneck, and plausible is not the same as measured.

The equation in this topic is what settles it.

It is worth learning even for someone who will never design a processor. The same reasoning applies to any code, at any level, on any machine.

The vocabulary

• Cycle — one tick of the processor clock.
• Cycles per instruction — the average number of cycles each instruction takes.
• Pipeline — an arrangement in which several instructions are in progress at once.
• Hazard — a situation in which an instruction cannot proceed because of another.
• Misprediction — a wrong guess about which way a conditional went, costing the pipeline's work.
• Cache hit — finding requested data already close to the processor.
• Working set — the memory a program actively uses over a period.
• Amdahl's law — the limit on speedup from improving only part of a task.

The mental model

Start with the equation, because everything else is a term in it. Run time is the number of instructions, times the average cycles each takes, times the length of a cycle.

Three terms, and any change worth making has to be judged on the product. A compiler that reduces the instruction count but causes more cache misses may lose. A design that shortens the cycle by lengthening the pipeline may lose to mispredictions. Talking about one term alone is how confident wrong answers get made.

Clock rate is the term that stopped moving, and the reason is physical. Power rises faster than frequency, and beyond a point the heat cannot be removed from the package at any acceptable cost.

That wall is why the industry went sideways instead of faster, and it is the direct cause of the multicore topic that follows. It is worth stating plainly because a reader who grew up after it can otherwise assume the change was a preference.

Pipelining attacks the second term. Several instructions are in progress at once, each at a different stage, so one instruction can finish every cycle even though each takes several.

It fails in three ways, collectively called hazards. An instruction may need a result the previous one has not produced yet. Two instructions may want the same hardware. Or the machine may not know which instruction comes next.

The third is the expensive one. After a conditional jump, the machine does not yet know which way execution goes, so it guesses and starts work on the guess. A correct guess costs nothing. A wrong one throws away everything started since, which on a deep pipeline is a great deal of work.

There is a practical consequence for a programmer. Unpredictable conditionals inside a hot loop are far more expensive than predictable ones, even though the source looks identical.

Caches attack the memory gap, and they work for one reason only. Programs reuse what they recently touched, and touch things near what they recently touched. A cache holds recent data close to the processor and is therefore fast most of the time.

Performance falls off a cliff when the working set stops fitting. The transition is not gradual. A loop over an array slightly smaller than the cache can be many times faster than the same loop over a slightly larger one. Nothing in the source hints at it.

Amdahl's law is the sanity check on all of it. If a part takes a tenth of the total time, making that part infinitely fast improves the whole by about a ninth. Not by a tenth of anything larger, and certainly not by a factor of ten.

The rule is why profiling comes before optimising, every time, without exception. Optimising the part you assumed was slow is the most common wasted effort in software. The equation and Amdahl's law together are the argument that stops it.

Benchmarks are last because they are where all of this gets misused. A benchmark measures one workload, on one configuration, under conditions someone chose. When a vendor publishes one, the vendor chose both.

A benchmark result is useful when the workload resembles yours and the conditions are stated fully enough to repeat. Otherwise it is a number with an origin you cannot check, which is exactly what the measurement module warned about in a different setting.

What you should now be able to explain or do

• Write run time as instructions, cycles per instruction and cycle length, and judge a change on the product.
• Explain why clock rates stopped rising and what the industry did instead.
• Name the three kinds of pipeline hazard and say which is most expensive.
• Explain why an unpredictable conditional in a hot loop costs more than a predictable one.
• Describe why performance collapses when the working set exceeds the cache.
• Apply Amdahl's law to decide whether an optimisation is worth doing.

Check yourself