Performance Engineering

A processor has a clock inside it, ticking at a fixed rate. One tick is one cycle, and it is the smallest slice of time the machine can tell apart. Work gets counted in cycles because that is the unit the hardware itself counts in, and because it does not change when somebody runs the same program on a slightly faster chip.

The machine used in this course ticks 3,200,000,000 times a second, which is written 3.2 GHz. So one cycle lasts about a third of a nanosecond, and a nanosecond is a thousand-millionth of a second. The ladder in Step 2 will convert cycles into nanoseconds for you, and into something easier to feel.

They multiply two grids of numbers, which is the sort of job that sits underneath weather forecasts, graphics and machine learning. To multiply two grids you take a row from the first and a column from the second, multiply them together pair by pair, and add up the results. That single number goes into one cell of the answer grid, and then you do it again for the next cell.

The grids here are 64 across and 64 down. That makes 4,096 cells in the answer, each one needing 64 multiplications, so 262,144 multiplications in total. Both programs do all of them and both reach the same total, which the widget checks and reports.

A bit is one switch, on or off, written 0 or 1. Eight bits side by side make a byte, and memory is one enormous row of bytes, each with its own number, called its address. The numbers in this course take 8 bytes each, which is the usual size for a number that can have a decimal point in it. In the code on this page that kind of number is written double. Bytes get counted in thousands and millions often enough to have short names: a KB is about a thousand bytes and an MB about a million.

An array is a run of values of the same kind, stored one after another with no gaps. Because there are no gaps, finding one is arithmetic rather than searching: item 0 sits at the start, item 1 sits 8 bytes further along, item 2 sits 16 bytes further along. That counting number is called an index, and it is why arrays are the shape almost all fast code is built out of.

Two reasons, and neither of them is laziness on the part of the designers. The first is distance. Electricity travels quickly but not instantly, and in one cycle a signal crosses only a few centimetres. A store big enough to hold a whole program cannot fit close enough to the core for its answer to arrive in the same cycle it was asked for.

The second is that finding something takes longer in a bigger pile. A store with more slots needs more machinery to work out which slot you meant, and that machinery is itself circuits that take time. So a designer who wants fast has to want small and the way out of that trap is to have several sizes at once and keep the things you are using now in the small one.

Carefully, because a modern core will happily have a dozen fetches in the air at the same time. If you ask for a thousand numbers whose addresses you already know, the waits overlap and you measure the overlap rather than the wait.

The trick used here is to follow a trail. Each address is stored at the address before it, so the machine cannot possibly ask for the next one until the last one has arrived. Nothing can overlap, so the total time divided by the number of steps is one honest wait. An address kept in memory as a value, so that it can be read and then followed, is called a pointer, and this trick has a name to match: pointer chasing. It is how these numbers get measured on real hardware too.

A nanosecond is a thousand-millionth of a second. Nobody has any feel for it, which is the problem with these numbers: 4 cycles and 200 cycles both round to nothing at all in human terms, so the difference between them does not land.

Stretching the clock fixes that. Pretend one cycle takes one second instead of a third of a nanosecond, and keep every ratio exactly as it was. Now an L1 hit is four seconds, a walk to main memory is a few minutes, and going to disk is most of a working week. Those are the same ratios a program lives with, and now you can feel them.

Because most of the waiting is in the asking, not in the sending. Getting the first byte out of main memory takes a couple of hundred cycles, and the next 63 bytes arrive almost free behind it. Fetching one byte at a time would pay that couple of hundred cycles sixty-four times over for the same data.

There is a bet inside this. The machine is wagering that a program which wanted byte 1,000 will shortly want 1,001 and 1,008 as well. That is true of nearly all real code, because arrays are read in order and the pieces of a record sit together. When the bet is wrong the machine fetches 64 bytes to use 8 of them, and Steps 4 and 5 are entirely about programs that lose this bet over and over.

Because then finding it would mean looking everywhere. A cache has to answer "have you got line 4,271" in a cycle or two, and it does that by looking in one place. Taking part of the address as the set number means there is exactly one set to search, and searching a set of 8 means comparing 8 labels at once, which is a piece of circuitry you can afford.

The price is what you just saw. Addresses a certain distance apart share a set, so they can knock each other out while the rest of the cache sits idle. This is called a conflict miss, and it is why a program can slow down for no visible reason when somebody changes an array size from 1,000 to 1,024.

The hardware decides, and its rule here is least recently used: of the lines in that set, the one nobody has touched for longest goes. The reasoning is that a line you have not wanted for a while is the one you are least likely to want next.

You cannot override it and there is no instruction to pin a line in place, so the only control you have over what stays in the cache is the order your program asks for things. That sounds like almost no control at all. It turns out to be enough for the whole of Step 4 and most of Step 11.

By arithmetic, every time, and the arithmetic is worth knowing because it explains everything in this step. For a grid N across, the cell at row i and column j sits at item number i × N + j. Multiply that by 8 bytes and add the address the grid starts at. You have the address.

Now look at what happens when you add one to each index. Adding one to j moves the address forward by 8 bytes, the very next number. Adding one to i moves it forward by N × 8 bytes, which for a grid 384 across is 3,072 bytes, or 48 whole cache lines. The index on the inside of the loop is the one that changes most often, so the index on the inside decides whether your program strolls through memory or leaps about in it.

The machine watches which lines it has been fetching. When two misses in a row are for lines that sit next to each other, it guesses that a walk is going on and starts fetching the next few lines before anybody asks for them. That piece of hardware is called a prefetcher, and when it guesses right the wait for memory disappears completely, because the line arrives before it is wanted.

It can only guess from a pattern it can see. A straight walk through memory is the easiest pattern there is, so orderly code gets this help for free. A walk that jumps 3,072 bytes each time gets none of it. Two loops with the same number of reads can therefore differ by more than the miss counts alone would suggest, because one of them is being helped and the other is not.

A compiler is the program that turns the code a person writes into the instructions a machine runs, and a good one rearranges a great deal on the way through. Some compilers really will swap two loops around for exactly the reason in this step and the option is usually called loop interchange.

They only do it when they can prove the swap cannot change the answer, and that proof is often out of reach. If the loop writes through a pointer that might, for all the compiler knows, point back into the grid it is reading, then no swap is safe. So the compiler leaves it alone and says nothing. Reading in the right order is your job. It is one of the few pieces of tuning that never stops paying.

Same thing. C calls a record a struct, short for structure; other languages call it a class, a record or an object. The idea is the same everywhere: a fixed set of named fields, laid out one after another in memory in the order they were written down. So the whole bundle has one address, and each field sits at a known distance from it.

The two layouts in this step have names that get used in conversation. An array of records is an array of structs, and the other one is a struct of arrays. If you hear somebody say they moved a hot loop from AoS to SoA, this step is what they did.

A wait is how long one thing takes to arrive: ask for a line, count 200 cycles, get it. Bandwidth is how much can arrive per second when things are queued up back to back. They are different quantities and they run out in different ways, which is why a program can be fixed by one change and untouched by another.

The picture that helps is a road. The wait is how long the journey takes; the bandwidth is how many lorries per hour the road can carry. There is one such road between the caches and main memory, shared by everything, and its name is the bus. When this course says bytes crossed the bus, it means they came all the way from memory rather than out of a cache. Sending fewer lorries is the only fix for a road at capacity, and that is what this step does: it does not make the journey shorter, it stops shipping 56 bytes of nobody's business in every load. Step 9 has a job that runs into the limit of that road head on.

No, and the deciding question is what the loops actually read. One array per field wins when a loop wants one field of everything, which is the shape of most sums, filters and searches. It loses when a loop wants every field of one record, because then the fields it needs are scattered across a dozen different arrays and it pays for a line in each of them.

So the layout follows the loop, not the other way round. Real code often keeps the fields that get read together in one record and pulls out the one or two fields that get swept over on their own. Games do this constantly: position and velocity live in their own arrays because every frame walks all of them, while the name and the artwork stay in a record because nothing sweeps those.

Because an instruction is not done in one step. It gets fetched, decoded, given its values, worked out, and its answer written down, and each of those happens in a different part of the core. Rather than leave four of the five parts idle, the machine keeps all of them busy on different instructions at once. Step 8 goes into that properly.

The consequence is that the machine is always partway through instructions it has not finished. When one of them is a branch, waiting for it would mean emptying every stage and starting again, which costs the same as guessing wrong. Guessing right costs nothing. So a machine that guesses right most of the time beats a machine that never guesses, and every processor you have used guesses.

A counter that only remembers last time gets caught out twice by one odd result: once on the odd result itself, and again on the next normal one, because it has changed its mind. A counter that runs from 0 to 3 does not change its mind that easily. Zero and one mean guess no, two and three mean guess yes, taken pushes it up by one, not taken pushes it down by one, and it sticks at both ends.

So a branch that goes the same way nine times out of ten sits at 3, gets pushed to 2 by the odd result, still guesses yes, and is pushed straight back to 3. One wrong guess instead of two. Real predictors add a record of the last several branches on top of this, so the same if can be predicted differently depending on how the program got there, which is how they reach the accuracies they do.

Often it is not, and that is worth saying plainly. Sorting 24,000 numbers costs far more than the wrong guesses the sorting saves, so as a one-off trick it loses.

It pays when the data was going to be sorted anyway. It pays when the loop runs many times over the same list. The lesson to carry away is not "call sort before your loops". It is that unpredictable data has a price, that the price is measurable, and that arranging work so the machine can see a pattern is a real option alongside doing less work.

From the compiler, mostly. Give it a plain loop that walks an array in order and adds up the numbers, and it will quietly turn the body into wide instructions and run the loop an eighth as many times. The name for that is auto-vectorising. It is one of the largest favours a compiler does you without being asked.

It gives up easily, though. If the loop reads in a pattern it cannot widen, or if the additions depend on each other, or if two pointers might overlap, it writes the plain version and says nothing unless you ask for a report. When you need the wide instructions and the compiler will not produce them, you can write them by name, and those named functions are called intrinsics.

Because the register has to be real silicon and the adder behind it has to be eight adders. Doubling the lanes doubles that area and the power it burns, and the benefit stops arriving once the loop is limited by how fast data can be delivered rather than by how fast it can be added. Common widths today hold four or eight 8-byte numbers and the widest in ordinary machines holds eight.

The other reason is that the numbers have to be next to each other in memory to be picked up together. Eight neighbouring numbers are one 64-byte line, which the memory system already moves as a unit, so eight lanes and one line fit together neatly. Wanting sixty-four numbers at once would mean wanting eight lines at once, and that is a different and harder problem.

Numbers with a decimal point are held to a fixed number of digits, so each addition rounds a little. Add a tiny number to an enormous one and the tiny one can vanish entirely; add up a thousand tiny ones first and they amount to something. So the order of the additions can change the last digits of the answer, and adding eight at a time is a different order.

A compiler will not make that change on its own, because it is not allowed to give you a different answer than the one you asked for. You can tell it that you do not mind, and most projects doing heavy arithmetic do. Whole numbers have no such problem: their addition gives the same answer in any order, so a compiler will widen a loop over whole numbers without asking.

Think about washing clothes. One load takes two hours to wash, dry and fold. That does not mean you can only finish one load every two hours, because as soon as the first load leaves the machine the second can go in. With three stages going at once you finish a load every forty minutes while each individual load still takes two hours.

An adder is built the same way, in stages, and this arrangement is called a pipeline. A new pair of numbers can enter the first stage while the previous pair is in the second. So the answer takes four cycles to come out, and answers come out every cycle once the pipe is full. The catch is the same as with the washing: it only works if you have another load ready to put in.

A running total is one variable that starts at zero and has every number added into it as the loop goes past. It is the ordinary way to add up an array and it is also, without meaning to be, a chain: the total after number 500 cannot exist until the total after number 499 does.

Four running totals means four variables. The first takes numbers 0, 4, 8 and so on, the second takes 1, 5, 9, and so on round the four. Nothing links them, so they proceed side by side, and at the very end you add the four together and get the same answer you would have got from one. Programmers call this unrolling the loop and splitting the accumulator, and it is one of the oldest tricks there is.

It reorders a great deal. This core looks at a window of the next 128 operations and starts any of them whose values are ready, in whatever order they become ready, which is how it keeps several things going at once without being told to. It will happily run your loop counter and your next load early.

What it cannot do is start an add before the number being added into exists. That is not a scheduling choice, it is arithmetic: the value simply is not there yet. Reordering can hide a wait behind other work, and here there is no other work, because every add in the loop is in the same chain. The only way out is to write a program with more than one chain in it, which is why this is your job rather than the hardware's.

Usually because a later part needs the result of an earlier one, which is the same problem as the dependency chain in Step 8, one size up. You cannot start on the second half of a running total until the first half exists, and you cannot hand out slices of a file until you have read enough of it to know where the slices are.

Sometimes it is because two cores would have to take turns. If they both need to add to the same counter, only one of them can be doing it at any moment, and the others queue. Splitting work therefore requires more than cores. The pieces must be arranged so that they do not need each other. That is a design decision made long before anybody counts cycles.

From dividing the job into the part that shares and the part that does not. Suppose one twentieth of the work, 5 per cent, cannot be shared. With an unlimited number of cores the shareable 95 per cent shrinks towards nothing, and the 5 per cent stays exactly as it was. So the whole job can never take less than 5 per cent of its original time, and 5 per cent of the time means twenty times faster at the very best.

That is the whole law: one divided by the unshareable fraction is the ceiling. One per cent gives a ceiling of one hundred, ten per cent gives a ceiling of ten, and half gives a ceiling of two. It is worth doing this division before buying anything, because the answer often says that the cores are not the problem.

Below the L2 caches all the cores share one road to memory, and one 64-byte line at a time travels along it. Here that takes 6 cycles per line, so however many cores are asking, lines arrive at a fixed maximum rate. That shared road is called the bus and the rate is the bandwidth from Step 5.

This limit is invisible while one core is running, because one core cannot ask fast enough to fill the road. Add cores and it appears out of nowhere: the arithmetic still divides perfectly, but the data cannot be delivered any faster, so the extra cores stand in a queue. Programs where this happens are called memory-bound, and the fix is never more cores. The fix is Steps 3 to 5, moving less data.

Stale means out of date. Core 0 has line 40 in its cache and so does core 1. Core 0 writes a new value into its copy. Core 1's copy now shows the old value, and if core 1 were allowed to keep using it, the two cores would be looking at the same address and seeing different numbers.

That would break everything. Almost all shared-memory programming assumes that a value written by one core is the value another core reads, and the hardware guarantees it by marking the other copies invalid the moment a write happens. Getting the line back afterwards means asking the core that owns it, which costs about 70 cycles here. That is much cheaper than main memory, and far dearer than the 4 cycles a hit in your own L1 would have cost.

Unused space put into a layout deliberately, to push the useful parts to addresses you want. Here it means declaring each counter inside a record 64 bytes wide and leaving 56 of them empty, so that no two counters can land in one line however the array is placed.

It looks wasteful and it is: an array of eight padded counters takes 512 bytes to hold 64 bytes of counters. That is a poor trade for something read occasionally, and a very good one for something four cores write to in a tight loop. Which way it goes depends on measurement. This is a case where the widget above answers the question in a few seconds.

Because the record of who owns what has to be kept in hardware, and its size depends on how finely it is kept. Tracking 64-byte lines in a machine with a few gigabytes of memory already means tens of millions of entries. Tracking single bytes would mean sixty-four times as many, all of them consulted within a cycle or two.

So the line is a compromise, chosen because it is the same unit the caches already move and label. Nearly all of the time it is the right choice, and the case in this step is the price of that choice. Hardware is full of decisions like this, and reading them as trades rather than mistakes is most of what it takes to predict how a machine will behave.

The plain version finishes one cell of the answer completely before starting the next. To do that it walks a whole column of B, and by the time it comes back for that column again, for the next row of A, the column has long since been thrown out of the cache. So B gets fetched from memory once per row of A, which for a big grid is a great deal of fetching.

Working in blocks means taking a small square of the answer, say 8 by 8, and doing all the arithmetic that touches it before moving on. The piece of B that square needs is small enough to stay in the cache the whole time, so it is fetched once and used many times. The real name for this is tiling, and it is the standard cure for a program that walks a large grid more than once. These grids are only 64 by 64, which is 32 KB, so they nearly fit in the caches already: expect blocking to buy little here on its own, and try it with the other switches on before deciding what it is worth.

Because you cannot change how a grid is stored by asking. B is in memory row by row, and this loop wants to walk down its columns, so somebody has to write out a second copy in which column j has become row j. That operation is called a transpose. It costs one full pass over B.

Paying a whole extra pass to make later passes quicker is a trade, and the reason it wins here is that the copy is made once and read 64 times. It is the same reasoning as sorting before a loop in Step 6: preparing the data costs something. It pays when the prepared data is used enough times. When it is used once, it does not pay.

For the final speed, no: all six on is all six on. For understanding what each one is worth, very much so. A change that removes waiting for memory makes the arithmetic changes look better than they are on their own, and a change that widens the arithmetic looks worthless while the loop is still waiting on memory.

This is why the advice line in the lab suggests memory first and arithmetic second. Fix what is limiting the program now, measure again, and see what is limiting it next. The waterfall below walks that order for you and shows how much each stage was worth given everything above it.

The mean uses every value and moves when one outlier is large. The median is less sensitive to an occasional interruption. A confidence interval estimates how precisely the experiment has located a population quantity under its sampling assumptions. Statistical separation does not say the change matters. A reliable 0.2 per cent improvement may not pay for more code, memory or risk. Set a minimum useful gain before looking at the result.

Probability for Engineering develops sampling, intervals, power, sequential tests and reproducible simulation from first principles.

A microbenchmark isolates a small operation and helps explain a mechanism. It can also produce a win that disappears when the operation is a tiny part of the real request. A component test includes nearby costs. An end-to-end load test includes queues, I/O and coordination. Use the small test to understand cause and the larger test to decide whether the change helps the user.

Counters differ by processor, and only a limited number can be measured at once. Tools may multiplex them, scaling partial observations. Speculation can count work that did not retire. Virtual machines and power management add more uncertainty. Record the CPU model, event definitions, command, workload and duration. Check whether the tool reports multiplexing or unsupported events.

Profiles can contain process names, memory addresses, paths and timing information. System-wide counter access can reveal activity belonging to other users. Use the least privilege and scope that answers the question, protect captured profiles and follow the machine owner's policy.

Data may come from L1, the last-level cache, DRAM or an accelerator link. Each boundary has its own measured bandwidth and its own byte count, so each produces a different intensity and roof. Integer work, tensor operations and floating-point work also have different compute ceilings. Label both axes and the measured boundary before interpreting a roofline plot.

The median is the middle request. The 99th percentile is the value that 99 per cent of requests finish at or below. In a page that calls many services, the chance that at least one call lands in a tail grows with the fan-out. Record a latency histogram rather than averaging already-averaged values. An exemplar can connect a slow histogram observation to its trace.

-O2 and -O3 enable groups of transformations. The higher bundle may increase code size, instruction-cache pressure or compile time, and a floating-point option may change numerical rules. Compare the exact compiler, flags and target CPU. Keep correctness tests, and measure the deployed binary rather than the intermediate file you meant to ship.

A search tool or coding model can propose tile sizes, layouts or source rewrites. Give it a correctness oracle, representative inputs, a held-out validation workload and a resource budget. Measure all candidates in controlled runs and retain the baseline. A candidate selected on the same noisy samples used to generate it can overfit the benchmark just as PGO can overfit an unrepresentative profile.

Registers and shared memory used by each thread block limit how many blocks can reside together. More resident warps can hide latency, but maximum occupancy does not guarantee maximum throughput. Coalesced memory access, divergence, arithmetic intensity, tensor-unit eligibility and data transfer may dominate. Profile the kernel and the host-device timeline.

Throughput counts all completed work. Goodput counts useful, accepted work. Retries can raise traffic and measured throughput while useful results stay flat. Compression may trade CPU time for fewer network bytes. Batching may raise throughput while an individual request waits longer for a batch to fill. Keep the user-visible outcome and resource budget beside the faster number.

Finishing sooner can reduce energy, but using more cores or an accelerator may raise instantaneous power. Cloud cost can change with instance count, data transfer, storage operations and reserved capacity. Report energy or money per useful result when that is the engineering goal. Also record the hardware and measurement method; power estimates and billing figures are not interchangeable.

A continuous profile shows how CPU or allocation time changes across real builds and workloads. It is sampled evidence, so low-frequency code and short incidents may be absent. AI tools can group stacks or suggest changes, but the same release test applies: inspect the patch, prove output equivalence where possible, run held-out workloads and keep the canary thresholds. Never trade correctness or a security boundary for a benchmark score the user does not experience.