You already know that memory is just a long row of numbered bytes, and that a pointer is nothing more than one of those numbers. Earlier chapters also mentioned in passing that reading memory "in order" is faster than jumping around, because of something called the cache. What those chapters did not cover is why, or how much it actually costs. This chapter opens that up: the chain of storage the CPU pulls data through before it can use it, why the CPU never fetches a single byte on its own, and why two pieces of code that do the exact same amount of work — same number of operations, same Big-O — can run at wildly different speeds depending only on how the data is arranged.
As always: small runnable C++ code, real output (or, for the CPU-internals parts where there is nothing to print, a clear worked trace), then a plain explanation. This chapter has two full benchmarks. Type them in and run them yourself. The exact milliseconds you get will differ from the example numbers printed here — your machine is not my machine — but which version wins, and by roughly how much, will not.
A CPU does not keep all storage at the same distance. Some storage sits right inside the CPU chip and answers almost instantly; some sits a short trip away; some sits on a completely separate chip and takes a comparatively huge trip. Chip designers arrange several layers, each one smaller and faster than the layer below it. That stack of layers is called the memory hierarchy.
malloc actually point into) sits on its own chip, reached over wires outside the CPU. It is huge compared to any cache level, and it is roughly 100 times slower than L1.The numbers above (nanoseconds, kilobytes, megabytes) are rough and will differ from CPU to CPU — do not memorize them as exact facts. What matters, and what stays true on nearly every machine you will ever profile a game on, is the shape: each step down the hierarchy is roughly an order of magnitude bigger and an order of magnitude slower than the step above it.
A nanosecond is too small to feel, so stretch it out. Imagine reading from L1 cache takes one second. On that scale, reading from L2 takes about four seconds, reading from L3 takes about fifteen seconds, and reading from RAM takes well over a minute and a half. If your program does that RAM trip millions of times because the data is scattered all over memory, instead of a handful of times because the data sits together, you can see why the difference shows up as real, measurable frame time.
Here is where registers fit into a tiny, familiar loop. There is nothing to print for this one — the interesting part is where each piece of data physically lives while the loop runs, not what it outputs.
int sum = 0;
for (int i = 0; i < 4; i++) {
sum += arr[i];
}
Here is the detail that explains almost everything else in this chapter. When the CPU needs a byte, or an int, or any small piece of data from RAM, the hardware does not go fetch just that value. It fetches a fixed-size chunk containing it, called a cache line — commonly 64 bytes on the CPUs in modern laptops and desktops. The whole 64-byte chunk moves together, as one unit, between RAM and the caches.
Think of a warehouse that only ever ships full pallets, never single boxes. Order one box, and the whole pallet shows up at your dock. The other boxes on that pallet are now sitting there too — free, if you happen to need them next.
A plain int is 4 bytes, so a 64-byte line holds exactly sixteen of them. Touch arr[0] for the first time, and — as long as the array starts at the beginning of a line, which a freshly allocated array normally does — arr[1] through arr[15] arrive in the same trip, at no extra cost.
std::vector<int> arr(16, 0);
for (int i = 0; i < 16; i++) arr[i] = i;
int total = 0;
for (int i = 0; i < 16; i++) total += arr[i]; // reads arr[0] .. arr[15]
Worked trace: the second loop reads sixteen values, but it only ever leaves the chip once. Reading arr[0] triggers one cache-line fetch that happens to cover the entire array, so the other fifteen reads are already sitting in L1 — no trip to RAM needed for them at all.
The idea behind the previous section has a name: spatial locality ("spatial" — about location). It says that if a program touches one address, it is likely to touch a nearby address very soon. Walking an array from index 0 upward is the cleanest possible example of spatial locality, because every next element is guaranteed to be 4 bytes after the last one.
There is a second effect stacked on top of this. Many CPUs include a hardware prefetcher — a piece of hardware that watches your memory access pattern, notices "this code is reading address after address in a straight line," and starts pulling in the next cache line before your code even asks for it. Sequential access benefits twice: the elements sharing your current line are already free, and the prefetcher is quietly loading the next line in the background while you finish this one.
A cache miss is what just happened four times above: the CPU asked for data that was not already sitting in cache, so it had to wait for the slow trip out to RAM. A cache hit is the sixty other reads: the data was already there, so it cost almost nothing. Sequential access keeps the miss count tiny compared to the number of elements you actually touch.
Now do the opposite. Instead of walking an array, follow a chain of pointers where each node was allocated separately and happens to land at some unrelated address on the heap — exactly what a linked list looks like in memory once you have inserted its nodes one at a time. There is no fixed stride between one node and the next, so neither spatial locality nor the prefetcher can help. Each hop is a coin flip on a completely different part of RAM.
This pattern — following a pointer to find the next thing to read, over and over, with no predictable address stride — is called pointer chasing. Every hop can cost the full ~100 ns trip to RAM from section 1, instead of the ~1 ns an L1 hit costs. Section 3's array touched 64 elements for 4 trips to RAM. This touches 64 elements for roughly 64 trips. Sixteen times the RAM traffic, to add up the exact same numbers.
Time to see it, not just reason about it. This program builds the same two million integers two ways: once as a plain contiguous array, and once as a linked list whose nodes are created in order but then chained together in a shuffled order — so walking the list means hopping to a effectively random address every step, just like section 4's diagram. Both sums touch every value exactly once, so both are doing O(n) work.
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <numeric>
struct Node {
int value;
Node* next;
};
int main() {
const int N = 2000000;
// ---- contiguous: a plain array ----
std::vector<int> arr(N);
std::iota(arr.begin(), arr.end(), 0); // fill 0, 1, 2, 3, ...
auto t0 = std::chrono::steady_clock::now();
long long sum1 = 0;
for (int i = 0; i < N; i++) sum1 += arr[i];
auto t1 = std::chrono::steady_clock::now();
// ---- scattered: the same N values, but as a linked list whose ----
// ---- nodes are chained together in shuffled order ----
std::vector<Node*> nodes(N);
for (int i = 0; i < N; i++) nodes[i] = new Node{i, nullptr};
std::vector<int> order(N);
std::iota(order.begin(), order.end(), 0);
std::mt19937 rng(42);
std::shuffle(order.begin(), order.end(), rng);
for (int i = 0; i + 1 < N; i++)
nodes[order[i]]->next = nodes[order[i + 1]];
Node* head = nodes[order[0]];
auto t2 = std::chrono::steady_clock::now();
long long sum2 = 0;
for (Node* p = head; p != nullptr; p = p->next) sum2 += p->value;
auto t3 = std::chrono::steady_clock::now();
double ms1 = std::chrono::duration<double, std::milli>(t1 - t0).count();
double ms2 = std::chrono::duration<double, std::milli>(t3 - t2).count();
std::cout << "contiguous sum = " << sum1 << " time = " << ms1 << " ms\n";
std::cout << "scattered sum = " << sum2 << " time = " << ms2 << " ms\n";
for (Node* p : nodes) delete p;
}Example output (one run on a laptop — your exact milliseconds will differ, but the gap will not):
contiguous sum = 1999999000000 time = 2.8 ms
scattered sum = 1999999000000 time = 41.3 msBoth sums are identical, 1999999000000 — the sum of every integer from 0 up to 1,999,999, since both structures hold the exact same values, just visited in a different order. Both loops are O(n): one addition per element, two million elements. And yet the scattered version took roughly 15 times longer. Nothing about the algorithm changed. What changed is exactly what sections 2 through 4 described: the array version needed a trip to RAM only once every sixteen elements, while the list version needed one on almost every single hop.
std::vector vs std::list timing gap from the data structures chapter. Both containers give you O(n) iteration. The vector wins in practice because its memory is contiguous, which is exactly the case this benchmark just measured directly.Separately from caching, modern CPUs also speed things up by not running one instruction fully start-to-finish before starting the next one. Instead, running an instruction is split into stages — a simplified version has four: fetch (read the instruction from memory), decode (figure out what it means), execute (do the actual work), writeback (store the result). Real CPUs use far more stages than four, but four is enough to see the idea.
The CPU overlaps these stages across different instructions, like an assembly line: while instruction 1 is executing, instruction 2 can already be decoding, and instruction 3 can already be fetching. This overlap is called pipelining.
Pipelining only pays off if the CPU can keep the assembly line fed — it has to know several instructions ahead of time which instructions are coming next, so it can fetch and decode them early. For ordinary straight-line code that is easy: instruction after instruction, in order. A branch — an if, a loop condition, a switch — breaks that assumption, because the very next instruction depends on a value the CPU has not finished computing yet.
If the CPU simply stopped and waited every time it hit a branch until the condition was fully computed, the pipeline from the last section would empty out and refill on every single if — brutally slow. Instead, the CPU guesses which way the branch will go, using a small piece of hardware called a branch predictor, and immediately keeps fetching, decoding, and even executing instructions down the guessed path before it actually knows the answer. Running instructions based on a guess like this is called speculative execution.
The predictor's guess is usually based on recent history for that same branch: if this if has been taken the last several times control reached it, bet that it will be taken again. This works very well for branches that are almost always one way, or that follow a steady repeating pattern — a loop's exit check, for example, is "not done" thousands of times in a row and then "done" exactly once. It works badly when the outcome is close to a coin flip with no pattern to learn, which is exactly what an if on unsorted, random data looks like.
If the guess turns out right, the cost is close to zero — the pipeline just carries on with work it already started. If the guess is wrong, that is a misprediction: every instruction the CPU speculatively ran down the wrong path has to be thrown away, and fetching has to restart from the correct instruction. That is called a pipeline flush, and it costs roughly a whole pipeline's worth of wasted cycles — often ten to twenty or more, every single time it happens.
This is the classic way to see branch misprediction cost with your own eyes. The code below fills an array with random bytes (values 0-255) and sums only the ones that are 128 or higher. It runs that exact same summing loop twice: once while the data is still in random order, and once after sorting the array first. The sum total cannot change from sorting — every value is still there, just in a different order — but the branch inside the loop suddenly becomes far easier to guess.
#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
#include <iostream>
int main() {
const int N = 10000000;
std::vector<int> data(N);
std::mt19937 rng(7);
std::uniform_int_distribution<int> dist(0, 255);
for (int i = 0; i < N; i++) data[i] = dist(rng);
// ---- unsorted: roughly 50/50, the branch is hard to guess ----
auto t0 = std::chrono::steady_clock::now();
long long sum1 = 0;
for (int i = 0; i < N; i++)
if (data[i] >= 128) sum1 += data[i];
auto t1 = std::chrono::steady_clock::now();
// ---- sorted: long runs of "no", then long runs of "yes" ----
std::sort(data.begin(), data.end());
auto t2 = std::chrono::steady_clock::now();
long long sum2 = 0;
for (int i = 0; i < N; i++)
if (data[i] >= 128) sum2 += data[i];
auto t3 = std::chrono::steady_clock::now();
double ms1 = std::chrono::duration<double, std::milli>(t1 - t0).count();
double ms2 = std::chrono::duration<double, std::milli>(t3 - t2).count();
std::cout << "unsorted: sum = " << sum1 << " time = " << ms1 << " ms\n";
std::cout << "sorted: sum = " << sum2 << " time = " << ms2 << " ms\n";
}Example output (one run on a laptop — the exact sum depends on the random seed, but the two sums always match each other, and sorted always wins by a wide margin):
unsorted: sum = 957530441 time = 54.1 ms
sorted: sum = 957530441 time = 11.4 msSame sum both times — sorting only reorders the array, it does not change which values are 128 or higher. Same loop, same comparison, same amount of arithmetic. Yet the sorted run finished roughly 5 times faster. Before sorting, whether data[i] >= 128 is basically a coin flip every step, so the branch predictor guesses wrong close to half the time — a pipeline flush on nearly every other element. After sorting, all the "no" values are grouped at the front and all the "yes" values are grouped at the back, so the branch says "no" thousands of times in a row, then "yes" thousands of times in a row. The predictor locks onto each long run almost immediately and is right almost every time, with only two mispredictions in the entire pass — one at the start, one where the run flips from "no" to "yes."
std::sort call itself costs time too — but if you sum the same array many times (a common pattern: filter or bucket a list once per frame, then process it repeatedly), paying the sort cost once and getting a predictable branch on every later pass is often a clear win. As always, measure your actual case.Put sections 5 and 8 side by side and a pattern jumps out. Neither benchmark changed the algorithm at all — same loop, same comparisons, same Big-O, same final answer. The only thing that changed was how the data sat in memory or in what order it was visited, and that alone was worth a 5x to 15x difference in real time. That is bigger than most algorithmic improvements a beginner is likely to find, and it costs nothing extra to think about up front.
This is exactly why the earlier data structures chapter found std::vector beating std::list even though both are O(n) to iterate — you now know the hardware reason: contiguous memory means few cache misses and a predictable stride the prefetcher can ride, while scattered nodes mean a cache miss on nearly every step. The same logic applies to branches: a loop over sorted or bucketed data, where the same branch keeps going the same way for long stretches, runs its pipeline full-speed; a loop with a coin-flip branch on every element pays a flush over and over.
The practical rule for a game programmer: when two approaches have similar Big-O, prefer the one whose hot loop walks contiguous memory in a predictable order with simple, predictable branches. For the entity counts, particle counts, and per-frame data sizes typical in games (thousands to a few hundred thousand items, not billions), this constant-factor difference from cache misses and mispredictions usually matters more to your actual frame time than swapping in a fancier algorithm.
Here is where this idea is heading in a later chapter. Say you have a thousand game entities, each with a position, a velocity, and health. The natural first instinct is one struct per entity, stored in one array — array of structures (AoS). But a system that only needs positions (say, a broad-phase collision check) still drags every entity's velocity and health into cache along with its position, because they all share the same cache lines.
The alternative, structure of arrays (SoA), keeps a separate array for each field. A loop that only touches positions now packs nothing but positions into every cache line, so it wastes zero bandwidth on data it does not need. This is the core idea behind data-oriented design, and it is exactly why Unity's DOTS/ECS and most high-performance engines organize entity data this way. You do not need to build a full ECS to use this idea today — even splitting one array of structs into a few parallel arrays, when a hot loop only touches some of the fields, is the same trick.
if, a loop condition, a switch.struct Vec3 { float x, y, z; }; // each float is 4 bytes -> 12 bytes per Vec3
Vec3 positions[1000];Vec3 elements fit inside one 64-byte cache line? (b) After the CPU reads positions[0].x for the first time, roughly how many additional whole Vec3 elements are now sitting in cache for free? (c) At minimum, how many cache lines does the entire 1000-element array span?
(a) 64 / 12 = 5.33, so 5 whole Vec3 elements fit in one line, with a few leftover bytes that spill into the start of the next line.
(b) Reading positions[0] loads the line containing it, which also holds elements 1 through 4 in full (5 elements total, including 0) — so 4 additional whole elements are free after the one you asked for.
(c) The whole array is 1000 * 12 = 12000 bytes. 12000 / 64 = 187.5, which rounds up to 188 cache lines, since a partial line still counts as a line that must be fetched.
(a) Twelve ints at four per line need 12 / 4 = 3 lines total, so summing the array costs 3 misses — one every four elements, then three free hits each time.
(b) Every node sits alone in its own never-touched line, so every single read is a fresh miss: 12 misses, one per node.
(c) 12 / 3 = 4, so the scattered version causes 4 times as many cache misses for the identical logical work (read twelve values, add them up). This is the same effect, at toy scale, that section 5's benchmark measured directly with real timings.
Pattern B is far friendlier to the predictor. A simple predictor bets "same as last time." In pattern B there is only one place where the outcome changes (from T to F, at step 9), so it causes roughly 1 misprediction out of 16 — the predictor locks onto each long run almost immediately and rides it correctly.
In pattern A the outcome flips on every single step, which is the worst possible case for a "same as last time" predictor — it guesses wrong on almost every step after the first, roughly 14-15 mispredictions out of 16. Both patterns have the same 50/50 split of T and F overall, so a naive "count how often it's taken" view would call them equally unpredictable — but what actually matters is the run length between changes, not the overall ratio. This is exactly why sorting the data in section 8 helped so much: it turned a coin-flip pattern into long, predictable runs.
That is the chapter. Underneath every algorithm you write, the CPU is pulling your data through a hierarchy of storage in fixed-size cache lines, and pipelining instructions while guessing which way your branches go. Contiguous, sequential access keeps that pipeline and that cache full and happy; scattered access and coin-flip branches starve it, one stall at a time. Carry the same habit forward into every later chapter: pick a reasonable algorithm, keep the hot data contiguous and the hot branches predictable, and measure before you trust a guess about which version is faster.