Lesson 27 · Building and performance

Writing fast C++

Fast C++ starts with an optimised build and a measurement, and very often ends with memory. Follow two loop nests that add up the same 4 × 4 grid: one walks memory in the order it is stored and pays one cache miss per line, the other jumps by a whole row on every read and misses every time. Same instructions, same answer, very different speed.

12 min9 steps5 questionsAdvanced

Fig 27 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01You time a program built with plain g++ main.cpp and no -O option. What is wrong with that measurement?

-O0 is GCC's (and Clang's) default. Build with -O2 (or the level you ship) before you measure, or you optimise the wrong program.

02A std::vector<int> g holds an N × N grid row by row. Which element sits right after g[r * N + c] in memory?

A std::vector stores its elements contiguously, and the grid is laid out row by row, so the right-hand neighbour in the same row is the next int in memory.

03In the figure a cache line holds 4 ints and the cache holds 2 lines. How many misses does the row-order loop cost for the 16 cells?

Each miss brings a whole line of 4 ints, and the next three reads hit. Four lines, four misses. The column order, which jumps by N every read, misses all 16 times.

04Why does walking a big grid column by column slow the program down?

Both orders do the same work and give the same sum. The column order uses one int per line fetched, so it misses far more often, and a trip to main memory costs a hundred or more cycles against a few for a hit.

05Your hot loop walks a std::list<int>. What is the most likely memory problem?

std::list stores each element in its own node linked by pointers, with no contiguous storage. A std::vector keeps elements side by side, so walking it uses every cache line fully. Measure to confirm.

Key terms

Glossary

Optimisation level: A compiler option such as -O0 (none, GCC's default) or -O2 (most optimisations) that sets how hard the compiler works to make the program fast.
Profiler: A tool, such as perf on Linux, that measures where a running program spends its time.
Contiguous: Stored side by side in one block of memory, as a std::vector stores its elements.
Cache: A small, fast memory next to the CPU that keeps copies of recently used memory.
Cache line: The unit the cache moves to and from main memory: 64 bytes on current Intel and AMD chips.
Cache miss: A read whose data is not in the cache, so it must be fetched from a slower level or from main memory.
Row-major order: Storing a grid row by row, so cells of the same row are neighbours in memory.
Hot loop: A loop where the program spends a large share of its time; the place where speed-ups pay off.

Fine print

Notes and sources

The figure's cache is a toy: 2 lines of 4 ints, throwing out the least recently used line. Real caches hold hundreds of 64-byte lines in several levels (L1, L2, L3), but a real grid is also far bigger: for N = 4096 one column touches 4096 lines (256 KiB), more than an L1 data cache holds.
Cache lines are 64 bytes on current Intel and AMD x86-64 chips; some Arm chips, such as Apple's M-series, use 128 bytes. C++17's std::hardware_destructive_interference_size gives the compiler's hint for your target.
Exact latencies depend on the chip. Drepper's measurements (2007) give about 3 cycles for an L1 hit, 14 for L2 and about 240 for main memory; Hennessy and Patterson quote about 1 ns for L1 and 50 to 100 ns for DRAM.
Real CPUs also prefetch: they spot a regular pattern of reads and fetch the next lines early. That softens the cost of a stride, but walking memory in order is still what they handle best.
The full program behind the card is real C++20. Build it with g++ -std=c++20 -O2 grid.cpp -o grid -Wall -Wextra; it times both loop orders on a 4096 × 4096 grid with std::chrono::steady_clock and prints the same sum, 16777216, twice. The times depend on your machine, so measure them yourself.
Some compilers can swap simple loop nests themselves (GCC's -floop-interchange is on at -O3). Do not rely on it: write the loop in memory order and check the result by measuring.

Quiz Unlocks after the last step.