The old cost model, and why it broke
Every rung you have climbed so far measured an algorithm by its flop count — the number of floating-point additions and multiplications it performs. Gaussian elimination is O(n^3), the FFT is O(N log N), Monte Carlo error falls like O(1/sqrt(N)). That instinct — count the arithmetic, and fewer flops means faster — served us faithfully and is still the right first question to ask of any method. This guide is about the moment the instinct stops being the whole truth, because of how real hardware is built.
Here is the uncomfortable fact, stated plainly. On a modern processor a floating-point multiply takes roughly one nanosecond's worth of work — call it one unit of time. Fetching a number that is not already nearby, all the way from main memory (RAM), takes on the order of one hundred such units. The arithmetic unit can chew through numbers far faster than the memory system can deliver them. So a calculation that does a few flops on each number it loads spends most of its life waiting — the multiplier sits idle while the data crawls in. The title is the whole lesson: flops are cheap, memory is slow.
The hierarchy: a pyramid of fast-but-tiny to slow-but-huge
Hardware designers cannot make all memory both fast and large — fast memory is expensive and physically must sit close to the arithmetic unit. So they build a memory hierarchy: a stack of memories, each level bigger and slower than the one above. At the top sit the registers (a few dozen numbers, instant). Below them a small L1 cache, then a larger L2, then a larger-still L3 cache — each a few times slower and several times bigger than the last. At the bottom is main memory: gigabytes, but a hundred-ish units away. (Disk and the network sit even further down, far slower still.) The whole pyramid exists to fake the impossible: memory that feels both fast and enormous.
level size ~cost to reach one number ----------- -------------- -------------------------- registers ~dozens 1 (instant, in the ALU) L1 cache ~32 KB ~4 L2 cache ~256 KB-1 MB ~12 L3 cache ~8-64 MB ~40 main memory ~GBs ~100-300 disk / net ~TBs+ ~100,000+ (don't go here in a loop) numbers are rough orders of magnitude, not exact, and vary by machine
The machinery works automatically. When you ask for a number, the hardware checks the fastest level first; if it is there (a cache hit) you pay almost nothing, and if it is not (a cache miss) the hardware must walk down the pyramid to fetch it, and that is the hundred-unit penalty. Crucially, when it finally goes to memory it does not bring back just your one number — it hauls up a whole contiguous chunk called a cache line (typically 64 bytes, about eight doubles), betting that you will want the neighbours next. Whether that bet pays off is entirely up to how you wrote your loop. A single cache miss, remember, can cost more than the arithmetic on a hundred numbers — so it is the miss, not the flop, that dominates the bill.
Arithmetic intensity: flops per byte, the number that decides everything
If memory traffic is what we pay for, we need a way to measure how frugal a computation is with that traffic. That measure is arithmetic intensity: the number of flops a kernel performs divided by the number of bytes it moves to and from memory. High intensity means you do a lot of useful arithmetic on each number you fetch — the data earns its trip. Low intensity means you touch each number, do almost nothing with it, and throw it away — you are paying full freight for memory and barely using the arithmetic unit at all.
Make it concrete with two kernels on vectors of length n. First, the vector sum z_i = x_i + y_i: you load two numbers, do one addition, store one number — three memory operations for one flop. Its intensity is about 1 flop per 24 bytes, hopelessly low; this kernel will spend almost all its time waiting on memory. Now contrast matrix-matrix multiply, C = A B for n-by-n matrices: it moves about n^2 numbers but performs about n^3 multiply-adds, so its intensity grows like n — every number, once fetched, is reused n times. That single difference is why one of these kernels can run near the chip's peak speed and the other never can, no matter how clever the programmer.
The roofline: are you memory-bound or compute-bound?
Arithmetic intensity gives us a single picture that classifies any kernel: the roofline model. Picture a graph with arithmetic intensity (flops per byte) on the horizontal axis and achievable speed (flops per second) on the vertical axis. The machine imposes two ceilings. One is a flat horizontal line at the chip's peak arithmetic rate — you can never compute faster than that. The other is a slanted line rising from the left, set by the memory bandwidth: at low intensity, your speed is capped by how fast bytes can arrive, and that cap rises in proportion to intensity. Together they look like a roof: a rising slope on the left that bends into a flat ceiling on the right.
Now place your kernel on the graph by its intensity. If it lands on the slanted part — to the left of the bend — it is memory-bound: its speed is dictated by bandwidth, and adding more arithmetic units would do nothing, because the data cannot arrive any faster. If it lands under the flat part — to the right of the bend — it is compute-bound: the memory system can keep up, and you are genuinely limited by raw arithmetic throughput. The vector sum sits far to the left (memory-bound); a well-written matrix multiply sits to the right (compute-bound). The roofline tells you, before you optimize a single line, which kind of problem you actually have — and therefore which fixes can possibly help.
This reframes optimization honestly. For a memory-bound kernel, buying a faster arithmetic unit is wasted money; the only real wins come from moving less data — and that means rearranging the computation so each fetched number is reused while it is still in cache, raising data locality and intensity. The headline trick is blocking (tiling): cut the problem into small blocks that fit in fast cache, do all the work on a block while it is hot, then move on. That is how you slide a kernel rightward along the roofline toward the compute ceiling, and it is the heart of the next guide.
Why this changes how you think — and one honest caveat
Step back and feel the shift. Two algorithms with the same flop count can differ by 10x or more in real running time, purely because one of them touches memory in a friendly, contiguous order and the other jumps around. The classic example you will meet in the next guide: multiplying two matrices the textbook way versus the blocked way performs the identical arithmetic, yet the blocked version can run several times faster on the same machine. The flops did not change at all; only the memory traffic did. Once you have internalized this, you stop asking only 'how many operations?' and start asking 'how does my data move?'
And here is the practical upshot that runs through this whole field: this is a large part of why you should reach for tuned libraries rather than BLAS and LAPACK hand-rolled loops. The experts who wrote those routines spent years blocking, tiling, and tuning the memory traffic for each cache size — work you almost certainly should not redo yourself. 'Flops are cheap, memory is slow' is exactly the principle those libraries are built to exploit, and standing on them is how you get fast and correct code for free.