Predict the speed of a piece of code from what the hardware has to do rather than from the number of operations, well enough to say which of two equivalent versions wins and why, and to stop optimising the part that costs nothing

What Makes Code Fast

Operation counts stopped predicting speed decades ago. This course covers what actually governs it: whether the data is nearby, whether the processor guessed right, whether work can be done at the same time, and which limit you are against.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

01Two Loops Doing Exactly the Same Arithmetic, One of Them Fifty Times SlowerBoth versions perform the same multiplications and the same additions in the same quantity. One finishes in a second and the other takes a minute. The count was never the thing.
02A Hundred Additions in the Time of Four, Unless Each One Waits for the Lastopening onlyA processor works on many instructions at once, so independent operations are nearly free. The one thing it cannot overlap is a step that needs the answer from the step before.
03Sorting the Array First Makes the Loop Six Times Faster Without Changing What It Computesopening onlyA processor guesses which way every branch will go and starts the work. When the data makes the guess easy the branch is free. When it does not, each mistake costs twenty operations.
04Compute Both Answers and Throw One Away, Which Is Faster Than Deciding Which to Computeopening onlyAn unpredictable branch can be turned into arithmetic that always runs. You pay for work you discard and you stop paying for mistaken guesses. Here is where the line falls.
05One Number Tells You Which Half of the Toolbox to Openopening onlyDivide the arithmetic your loop performs by the bytes it moves. That single ratio says whether the processor or the memory is your ceiling, and therefore which optimisations can possibly help.
06The Same Add, Eight Numbers at a Time, If You Can Convince the Compiler It Is Safeopening onlyA single instruction can add eight pairs of numbers at once. The hardware has had this for decades and the reason your loop is not using it is almost always one you can remove.
07Most of the Time Is Going Somewhere That Does Not Appear Anywhere in Your Sourceopening onlyAllocation, following pointers, and the bookkeeping the language performs on your behalf routinely account for most of the run time, and none of it is visible in the code you wrote.
08The Fastest Possible Version of a Tenth of Your Program Buys You Eleven Per Centopening onlyOne 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.