ContentsThe library

What Makes Code Fast

The Fastest Possible Version of a Tenth of Your Program Buys You Eleven Per Cent

Last timeThe Cost You Did Not Write

One fraction sets the ceiling on every optimisation before you start it. Computing it first tells you which change is worth making and when to stop making them.

The share you can touch

Every change you could make affects some part of the run time and leaves the

rest alone. The part it leaves alone sets a limit on what it can achieve, and

the limit is usually the thing nobody computed.

FIG 1The best the change can do
the overall speedup you end up with
share of the run time the change can affect
how much faster that part becomes
The term on the left of the sum is the time the change cannot touch, which stays exactly as it was. Let k go to infinity and the second term vanishes, leaving a ceiling of one over one minus p. That ceiling is a property of p alone, so it can be computed before any work is done.

Three words in the definition of p do the work. It is a share of the time,

measured, not a share of the lines of code and not a share of the operations.

It is the share this particular change can affect, which is narrower than the

share of time the function takes. And it comes from measurement rather than

from reading, because every lesson in this course has been an example of the

source being a poor guide to where the time goes.

FIG 2Ceilings for a range of shares
share, per centceiling if that part becceiling if it becomes tw
a tenth of the time10.001.111.05
a fifth20.001.251.11
under a third30.001.431.18
half50.002.001.33
most of it70.003.331.54
nearly all of it90.0010.001.82
The first marked cell is the number worth memorising: making a tenth of the run time take no time at all buys eleven per cent. The second is the realistic case, since changes usually make something twice as fast rather than free, and a third of the time doubled in speed buys eighteen per cent. Most optimisation proposals live in the top three rows.

The practical use is as a filter applied before the work. Somebody proposes

rewriting a component in a faster language, or widening a loop, or replacing a

data structure. Ask what share of measured time that component holds. If the

answer is six per cent, the proposal is capped at six per cent, and it does not

matter how good the rewrite is.

The lesson stops here

5 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the planThe contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

The rest of this course

  1. 01Two Loops Doing Exactly the Same Arithmetic, One of Them Fifty Times Slower
  2. 02A Hundred Additions in the Time of Four, Unless Each One Waits for the Lastopening only
  3. 03Sorting the Array First Makes the Loop Six Times Faster Without Changing What It Computesopening only
  4. 04Compute Both Answers and Throw One Away, Which Is Faster Than Deciding Which to Computeopening only
  5. 05One Number Tells You Which Half of the Toolbox to Openopening only
  6. 06The Same Add, Eight Numbers at a Time, If You Can Convince the Compiler It Is Safeopening only
  7. 07Most of the Time Is Going Somewhere That Does Not Appear Anywhere in Your Sourceopening only
  8. 08The Fastest Possible Version of a Tenth of Your Program Buys You Eleven Per Centyou are here

Read alongside