A stack of memories, each a step slower
The previous guide left you with an uncomfortable fact: an arithmetic operation is almost free, while fetching the number it needs from main memory can cost a hundred times more. If the machine simply waited for every number, your processor would spend most of its life idle. The hardware's answer is the memory hierarchy: not one memory, but a stack of them, small-and-fast at the top, huge-and-slow at the bottom. At the very top sit a few dozen registers, the scratch pad the arithmetic unit reads from directly. Below them come caches — small, fast copies of recently used data, usually in three levels named L1, L2, L3. Below those is main memory (DRAM, your gigabytes of RAM), and below that, slowest of all, the disk.
The numbers are worth feeling in your bones, because they drive everything that follows. Reading from a register is essentially instant. An L1 cache hit costs a handful of cycles; L2 a few times more; L3 a few times more again; and a trip all the way out to DRAM costs on the order of a few hundred cycles. In the time one DRAM fetch completes, the arithmetic unit could have done hundreds of multiplies. So the central drama of high-performance computing is not "how many flops does my algorithm do" but "where does each number live when I need it, and how far must it travel."
Cache lines, and the two flavours of locality
Here is the detail that makes everything click. The cache does not fetch one number at a time. It fetches a whole contiguous chunk called a cache line — typically 64 bytes, which is exactly eight double-precision numbers. So the first time you touch one double, you pay the full DRAM price, but its seven immediate neighbours come along for free and now sit in cache. The next time you ask for a value not in cache, that is a cache miss and you pay the long price again; a value already in cache is a cheap cache hit.
This single fact splits good behaviour into two kinds, and together they are the whole content of data locality. Spatial locality means using data that sits near data you just used: walk an array straight through, element 0, 1, 2, 3, and every cache line you pay for is fully spent before you move on — one miss buys eight numbers. Temporal locality means reusing the same data soon after first touching it, while it is still resident in cache, so the second, third, and tenth uses are all free hits. A kernel with strong locality of both kinds rides the fast tiers; a kernel with poor locality keeps falling back to DRAM and stalls.
A tiny picture makes the stakes vivid. A matrix is stored as one long line of numbers — say row by row, so the whole first row sits contiguously, then the whole second row. Sum it row-major (across each row, the way it is stored) and you sweep along cache lines with perfect spatial locality. Sum the very same matrix column by column and each step jumps a whole row's length forward in memory; for a large matrix every single access lands on a fresh cache line, so you suffer a miss on essentially every element. Same flops, same answer — and the column version can run many times slower purely because of how the data was traversed.
Blocking: rearranging the work to reuse data
Spatial locality is mostly about how you store and traverse data. Temporal locality often takes more cunning, because the obvious way of writing a computation can throw cached data away long before it would have been reused. The classic cure is blocking (also called tiling): instead of sweeping across the whole problem in one long pass, you chop it into small tiles that fit inside the cache, finish all the work touching a tile while it is hot, and only then move on. The arithmetic is identical; you have merely changed the order so that data, once fetched, is fully exploited before it is evicted.
Matrix multiplication is the textbook example, and it is worth picturing once carefully. To form the product C = A B of two n-by-n matrices the naive triple loop does about n^3 multiply-adds but reads roughly n^3 numbers from memory too — every entry of B is re-read for every row of A, and a large B simply will not stay in cache between reuses. Blocked multiplication instead carves all three matrices into small b-by-b tiles and multiplies tile by tile. Once a tile of A and a tile of B are loaded, they are reused for b multiply-adds each before being discarded.
for ii in 0, b, 2b, ... # tile row
for jj in 0, b, 2b, ... # tile col
for kk in 0, b, 2b, ... # tile depth
# multiply the b-by-b tiles, all of which fit in cache
for i in ii..ii+b
for j in jj..jj+b
for k in kk..kk+b
C[i,j] += A[i,k] * B[k,j]The payoff is dramatic and measurable. The naive version reads on the order of n^3 numbers from slow memory; the blocked version, with a tile size b chosen so three tiles fit in cache, reads only about n^3 / b. Choose b around 64 and you have cut slow-memory traffic by roughly that factor — the computation that was helplessly waiting on DRAM is now mostly running from cache. This is the single most important transformation in dense linear algebra, and it is exactly what the level-3 BLAS routines do for you under the hood, which the next guide unpacks in full.
Arithmetic intensity: the number that decides your fate
Why does blocking help matrix multiply so enormously, yet do almost nothing for, say, adding two vectors? The answer is captured by one beautiful ratio, the arithmetic intensity of a computation: how many flops it performs for each byte it must move to or from main memory. Write it as flops divided by bytes. A kernel with high intensity does a lot of arithmetic per byte fetched and can keep the processor busy; a kernel with low intensity is starved, doing a trickle of arithmetic between long waits for data.
Compare two kernels. Adding two vectors of length n, c = a + b, does n additions but must read 2n numbers and write n — about three memory accesses per flop, an intensity well below one. No amount of blocking saves it, because each number is used exactly once: there is simply no reuse to exploit. Now matrix multiply: n^3 flops against, with blocking, on the order of n^2 numbers moved — an intensity that grows with n, into the hundreds or thousands. That is precisely why blocking transforms matrix multiply and cannot touch vector addition. The arithmetic intensity is a property of the math itself, and it sets a ceiling on how fast any implementation can possibly run.
The roofline: memory-bound or compute-bound
Arithmetic intensity earns a picture, and the picture has a name: the roofline model. Draw a graph with arithmetic intensity along the horizontal axis and achievable performance (flops per second) up the vertical axis. The machine imposes two hard ceilings. One is its peak arithmetic rate — a flat horizontal line, the most flops it can ever retire per second no matter what. The other is its peak memory bandwidth — a slanted line rising from the left, because at low intensity your speed is bandwidth times intensity: more flops per byte means more flops per second, until you hit the flat ceiling.
The two lines meet at a corner, and the corner tells you everything. To the left of it, on the slanted part, your kernel is memory-bound: it is limited by how fast bytes arrive, and its performance is pinned to the bandwidth roof. To the right, on the flat part, your kernel is compute-bound: it has enough reuse to keep the arithmetic units saturated, and is limited only by raw flop rate. Place your kernel by its intensity, and you instantly know which wall you are pressed against — and therefore which optimizations can possibly help. Vector addition sits far left, hopelessly memory-bound; well-blocked matrix multiply sits right at or past the corner, the rare kernel that actually reaches the flat roof.
Be honest about what the roofline is and is not. It is an upper bound on a single machine, a clean back-of-envelope ceiling — not a promise. Real kernels also stall on instruction overhead, imperfect prefetching, cache conflicts, and the round-off-free but bandwidth-hungry traffic of bringing in cache lines you only partly use; so measured performance sits below the roof, often well below. The model's gift is not an exact prediction but a diagnosis: it tells you whether to fight the memory wall or the compute wall, and it stops you from optimizing the one that was never your bottleneck. Keep this map in hand — the next guides climb from a single core's caches out to vectorized BLAS, then to many cores and many machines, where data locality becomes data movement between processors, and the same lesson returns one scale larger.