Answers · How a program runs
If I make one part of my program twice as fast, how much faster does the whole program get?
In shortLess than twice as fast: only the share of run time you actually touch can improve, so the untouched remainder caps the gain, often at a few per cent.
Less than twice as fast, and the untouched remainder is what decides how much less. If the part you double holds a share of the measured run time, the whole program ends up times faster: about 1.11 when is a fifth, 1.33 when it is a half, and 2 only when is everything. The rest of the program keeps taking exactly as long as it did, and that fixed block of time is the ceiling.
Take a program that runs in 100 seconds, with 20 of those seconds inside the part you propose to touch. That gives and . The other 80 seconds are untouched and stay at 80. The part you doubled falls from 20 seconds to 10, so the new total is seconds. The speedup is , which is eleven per cent, not a hundred. Nothing in the arithmetic cares how clever the doubling was: the 80 seconds sits outside it.
| share of time, per cent | seconds in the part | new total, seconds | speedup from doubling | ceiling |
|---|---|---|---|---|
| 10 | 10 | 95 | 1.05 | 1.11 |
| 20 | 20 | 90 | 1.11 | 1.25 |
| 30 | 30 | 85 | 1.18 | 1.43 |
| 50 | 50 | 75 | 1.33 | 2.00 |
| 70 | 70 | 65 | 1.54 | 3.33 |
| 90 | 90 | 55 | 1.82 | 10.0 |
The natural guess is that halving the work inside a part halves the run time, so half the code at twice the speed gives twice the program. It gives 1.33. Half the program's time, 50 seconds out of 100, drops to 25, and the total becomes 75, because the other 50 seconds did not move. Even making that entire half take no time at all gives exactly 2, since 50 seconds is the floor the run time can reach. A factor of two on part of a program is a ceiling, not a promise, and it is usually the wrong factor to quote.
The share is time, not code
There is a second way the estimate goes wrong, and it is quieter. The in the formula is the fraction of measured run time, not the fraction of lines, functions or operations. Individual operations differ in cost by two orders of magnitude, so the function with the most code and the most loops is routinely not the one holding the time. A component that looks like a candidate for a rewrite might hold six per cent of the run, in which case its ceiling is six per cent and the quality of the rewrite is irrelevant. The share has to come from a profile on a real workload before the proposal is worth discussing.
The second fix buys less
Continue the same program past the first change. After the 20 second part is halved, the total is 90 seconds, and the part is now 10 of those 90, which is 11 per cent of the new run time rather than 20. Halve it a second time and the total falls to , so against the 90 you now have the speedup is , about six per cent where the first round bought eleven. The ceiling has moved too: it was when the part held a fifth of the time, and it is once the part holds an eleventh. Succeeding at the first change is what lowered the ceiling on the second.
The arithmetic assumes two things, and both can fail. It assumes the rest of the program is genuinely untouched, so its time is a constant; a faster component that changes how often the rest is called breaks that, and the measured shares have to be taken again rather than predicted. It also assumes the total is fixed, which stops being true when the program does more work as it gets more resources: a fraction that is constant on one fixed job is not constant when the workload grows, which is why the ceiling bites harder on a single job made faster than on a system given more machines and more data.
Change the design rather than the implementation and the shares themselves change, because different work exists; that is the one escape from the ceiling, and it is a different activity from optimisation. Otherwise the stopping rule is arithmetic: compute the ceiling on the largest remaining share before starting, compare it with the time and the risk the change costs, and stop when the ceiling is the smaller number. The largest remaining share after four successful rounds is typically a fifth of a much smaller total, worth at most a quarter, and a note recording that is what stops the next person from proposing the same month of work.
Worth keeping
- Doubling a part that holds a share p of the run time leaves the program 1/((1-p) + p/2) times faster, which is 1.11 at p = 0.2 and 1.33 at p = 0.5.
- Making a part completely free still cannot beat 1/(1-p), so a part holding a tenth of the time is capped at eleven per cent however it is rewritten.
- Every successful change raises the share held by what is left alone, so the ceiling on the next change falls and the work is worth less by construction.
Where this goes next
This question is one step of What Makes Code Fast, a course that works through its subject from the beginning. The page that teaches this part of it is Knowing What Is Left, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- Why does sorting an array make a loop that scans it and counts matches so much faster?Sorting does not make the comparisons cheaper. It makes the test inside the loop predictable, so the processor stops guessing wrong and stops paying for those mistakes.
- Why does 2 + 3 * 4 equal 14 and not 20?The multiplication is done first: three times four makes twelve, and only then is the two added, giving fourteen. Reading left to right would give twenty.
- How many samples does a profiler need before a percentage in the report means anything?It depends on how many samples landed on that line: you need a few hundred samples on the line you care about, because the relative error is roughly one over the square root of that count.
- Why does reading one byte from memory load 64 bytes?Memory hardware moves data in fixed sixty-four-byte blocks, so a one-byte read fetches the whole block; the extra bytes cost almost nothing because reaching the memory row costs most of the time.
- Why can two threads that each work correctly still give the wrong answer?Each thread reads the shared value and writes it back in two separate steps, so the other thread can run in between and one increment silently overwrites the other.
- My change made it 4% faster — how do I know that isn't just noise?You cannot tell from one pair of runs. Run the unchanged program ten times first: only then does a four per cent gap mean anything.