Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 67 ยท Real-World Machines and Performance

Writing Cache- and CPU-Friendly Code

Turn hardware knowledge into faster programs: data layout, loop tiling, branch-free code, alignment and NumPy versus loops, tested with runnable models.

Two programs can compute exactly the same answer and differ in speed by a factor of ten or a hundred. The difference is rarely the algorithm's big-O; it is how well the program fits the machine underneath. A cache that holds the right lines, a branch predictor that guesses right, a loop that the hardware can run on many numbers at once: these are the things that decide the constant factor.

This lesson collects the practical rules that follow from everything you have learned so far, and tests each rule in a small model you can run. You will see why data layout matters, how loop tiling rescues a cache-hostile loop, why unpredictable branches are expensive, what alignment does, and why NumPy beats a Python loop by a huge margin. It builds on cache performance and the three Cs, branch prediction and SIMD and vector processing.

Measure first, then fix the right thing

Hardware intuition tells you what to look for. It does not tell you where the time goes. Programs spend most of their time in a few small regions, and optimizing anything else changes nothing you can notice. Amdahl's law from Measuring Performance says the same thing in numbers: speeding up a part that takes 5% of the time can never give more than a 5% gain.

flowchart LR
  M["Measure with a profiler"] --> H["Find the hot loop"]
  H --> W["Ask: cache, branches<br/>or too many instructions?"]
  W --> C["Change one thing"]
  C --> R["Measure again"]
  R --> M

Performance work is a loop: measure, find the hot spot, change one thing, measure again.

The rest of this lesson gives you the "change one thing" options. Keep two cautions in mind. First, timings are noisy, so repeat a measurement and keep the best time. Second, the compiler or interpreter may already do part of the work for you, so always check that a change helped.

Rule 1: walk memory in the order it is stored

A cache fetches whole blocks, typically 64 bytes. If your loop uses every byte of each block before moving on, you pay one miss per block. If it jumps by a large stride, you may use 8 of 64 bytes and then evict the block before coming back. That is the lesson of the memory hierarchy and locality, and it explains why the order of two nested loops matters so much.

Matrix transpose is the textbook trap, because one of the two matrices must be walked the "wrong" way. The model below counts cache misses for a 64 by 64 matrix of 8-byte numbers (32 KB, much larger than the 4 KB cache) for the naive double loop and for tiled versions that process small square blocks one at a time.

Python Loop tiling in a cache model

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive loop misses on 56.2% of its 8,192 accesses. Tiles of 4 or 8 bring that down to 19.3% and 17.7%. Look at the last two rows: tiles of 16 and 32 are as bad as no tiling at all. A tile only helps if the blocks it touches fit in the cache together. With 8 by 8 tiles, each tile touches 8 lines of the destination, which just fits. With 16 by 16 it needs 16 lines in a region that maps to only a few sets, the lines evict each other before they are reused, and the benefit vanishes. Real code picks the tile size from the cache size, or uses a library that has already done so.

The sets in this model are crowded for a second reason. The matrix rows are 512 bytes apart, a power of two, so many column elements land in the same few sets. Powers of two in strides and array widths are a classic cause of conflict misses. Padding each row with a few extra elements is a common cure.

Rule 2: keep the data you use together

Loops usually read a few fields of many records. How the records are laid out in memory decides how much of every cache block is useful.

  • Array of structures (AoS): each record is stored whole, one after another: id x y z, id x y z, .... Good when you use most fields of one record at once.
  • Structure of arrays (SoA): one array per field: x x x x ..., y y y y .... Good when a loop touches one or two fields of many records, because every cache block is full of useful numbers, and SIMD instructions can load several of them in one go.
flowchart TB
  subgraph AoS["Array of structures: a loop over x skips 24 of every 32 bytes"]
    direction LR
    a1["id|x|y|z"] --- a2["id|x|y|z"] --- a3["id|x|y|z"]
  end
  subgraph SoA["Structure of arrays: a loop over x reads only x values"]
    direction LR
    b1["x|x|x|x|x|x|x|x"]
    b2["y|y|y|y|y|y|y|y"]
  end

The same data in two layouts: a loop over one field wastes most of each cache block in the first layout and none in the second.

The next TryIt measures the effect on real hardware (your browser's CPU). It also times a plain Python loop against NumPy. Exact times differ from machine to machine, so the program prints ratios and checks that both versions produce the same answer.

Python Layout and NumPy against a loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On a typical machine the Python loop is hundreds of times slower than the NumPy dot product, and the strided read of one field takes noticeably longer than the contiguous one (often two to four times). Why is the loop so slow? Each Python iteration runs dozens of interpreter instructions, checks types and creates a temporary number. NumPy runs one tight compiled loop over contiguous memory, which the CPU can prefetch and often execute with SIMD instructions that handle several numbers per instruction. NumPy is a living example of the idea from SIMD, vector processing and GPUs: give the hardware a large, regular, contiguous chunk of work.

Rule 3: help the branch predictor, or remove the branch

A branch the predictor guesses right is nearly free. One it guesses wrong costs a pipeline flush, often 15 to 20 cycles on a modern core. Branches that depend on data are the dangerous ones, because their pattern may look random.

The model below runs a 2-bit saturating counter (see Branch Prediction) over the branch in if v >= 128: total += v, once for random data and once for the same data sorted. Then it shows two branchless versions of conditional code: a vectorized mask in NumPy and a bit trick for min.

Python Predictable versus unpredictable branches

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Random data makes the predictor wrong about half the time (50.4%), which is no better than a coin flip, while sorted data is almost perfectly predicted (3 wrong guesses in 20,000). The famous consequence is that a loop over a sorted array can run several times faster than the same loop over a shuffled one, with identical instructions.

The branchless forms turn a control dependency into arithmetic. The compiler can often do this itself with a conditional move (cmov on x86, csel on ARM). Use branchless tricks only in hot loops where a profiler shows mispredictions, because they usually make code harder to read, and for well-predicted branches a plain if is just as fast. (In Python the bit trick works on small values because Python integers have no fixed width. In C you would use 64-bit signed integers and watch for overflow in a - b.)

Rule 4: respect alignment and padding

Hardware reads memory in aligned chunks. A value is aligned when its address is a multiple of its size, which is why compilers insert padding between struct fields. Padding wastes space, and it can cost you cache lines. Two things to know:

  • Field order changes struct size. Putting large fields first removes padding.
  • A value that straddles two cache lines needs two accesses. Records whose size does not divide the line size will sometimes straddle.
Python Padding and cache-line straddling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On a typical 64-bit system, the same three char and three double fields take 48 bytes when interleaved and 32 bytes with the doubles first. The record sizes show the other effect: 32-byte and 64-byte records never straddle a line, but 24-byte records straddle in a quarter of cases and 40- and 48-byte records in half. Many performance-minded designs round record sizes to 32 or 64 bytes, or align the whole array to a cache line, for exactly this reason.

More pitfalls worth knowing

  • Pointer chasing. A linked list or tree with nodes scattered across memory defeats prefetching, since the address of the next node is only known after the current one loads. Arrays or index-based structures usually beat them for the same size.
  • False sharing. Two threads writing different variables that share one cache line force the line to bounce between cores. See cache coherence. Pad per-thread counters to separate lines.
  • Power-of-two strides. Array widths of 1024 or 4096 elements map many rows to the same sets, causing conflict misses. Pad the width.
  • Too many small allocations. Many tiny heap objects spread data around. Allocating arrays of values keeps it dense.
  • Doing less work. The fastest memory access is the one you avoid. Compute once, reuse, and prefer a better algorithm before any micro-optimization.

Do not optimize blindly. A tiled loop, a branch-free trick or a packed struct all add complexity. Measure the hot spot first, apply one change, and keep it only if the timing improves on the machine that matters.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does loop tiling reduce cache misses in a matrix transpose?

    Tiling reorders the iterations so each small block of both matrices fits in the cache together and every fetched line is reused.
  2. 2. In the tiling model, tiles of 16 and 32 were as bad as the naive loop. What is the best explanation?

    A tile helps only while its working set fits in the cache; once it does not, conflict and capacity misses return.
  3. 3. A loop sums only the x field of a million 32-byte records. Which layout lets every fetched cache line be full of useful data?

    With a structure of arrays, the x values are adjacent, so each 64-byte block holds eight useful values instead of two.
  4. 4. Why can summing the values of a sorted array that are at least 128 be faster than doing the same on shuffled data?

    The same instructions run, but on sorted data the branch is taken in one long run, which a predictor guesses almost perfectly.
  5. 5. What is the first step of sensible performance work?

    Only a small part of a program usually matters. Profiling finds it, and Amdahl's law shows why optimizing anything else changes little.

Summary

  • Fast code fits the machine: reuse cache lines, keep branches predictable and give the hardware regular work.
  • Walk memory in storage order. When a loop must go the other way, use tiling with a tile whose working set fits in the cache.
  • Use a structure of arrays when loops touch few fields of many records; use an array of structures when you use most fields together.
  • Unpredictable data-dependent branches are costly; branchless forms (masks, conditional moves) help only where profiling shows a problem.
  • Struct field order, padding and alignment affect size and cache-line straddling; powers of two in strides cause conflict misses.
  • Vectorized libraries such as NumPy beat interpreted loops by hundreds of times by running compiled, contiguous, SIMD-friendly code.
  • Always measure before and after, and optimize the hot spot, not everything.

Time to apply it all: build a complete processor in Project: A Complete Mini CPU Simulator.