TLB (translation lookaside buffer): Visual walkthrough

We assume only that you know an address must be translated before memory is touched — the Virtual Memory idea. Everything else is earned below.

Step 1 — Name the two clocks we are racing

WHAT. Before we can add up any time, we must name every duration that a single memory access can spend. There are exactly two places time gets consumed: searching a small fast box, and touching slow memory.

WHY these two and not more? Because in the whole machine only two speeds matter to us here. One is the tiny hardware lookup table (the TLB) that answers in a fraction of a nanosecond. The other is DRAM, roughly a hundred times slower. Every cost we compute will be built out of just these two bricks — so we name them first, before any symbol is used.

PICTURE. Look at the two bars: the short blue bar is the TLB search, the long red bar is one memory access. Everything later is these bars stacked.

Figure — TLB (translation lookaside buffer)

Step 2 — Every access starts the same way: search the TLB

WHAT. No matter what happens next, the very first thing the hardware does on any memory reference is search the TLB. So every access pays $t_{TLB}$ — no exceptions, no branches yet.

WHY start here? Because the TLB sits on the critical path: the CPU cannot know the physical frame without first asking "is this translation cached?" That question is the TLB search, and asking it costs $t_{TLB}$ unconditionally. Making this the shared "floor" of the cost is the key trick that later lets us collapse the formula.

PICTURE. One blue bar at the front of the timeline, before the road forks.

$cost so far = always paid: the search t_{TLB}$

Step 3 — The road forks: hit vs miss

WHAT. After the search, exactly one of two things is true. Either the translation was in the TLB (a hit), or it was not (a miss). These are the only two outcomes, and they are mutually exclusive — this is why locality (Locality of Reference) matters: it decides how often we take the cheap branch.

WHY a fork and not a formula yet? Because the two branches cost different amounts, we cannot write a single number until we price each branch on its own. So we draw the fork, price each side, then re-merge them by weighting.

PICTURE. The timeline splits into a green upper path (hit) and a red lower path (miss). The green path is short; the red path has a big walk block in the middle.

Step 4 — Price the HIT road (green)

WHAT. On a hit, the TLB instantly hands back the physical frame number (PFN). From the Page Table nothing is read. So we just do the one real data access to memory. Total green cost: the search plus one memory touch.

WHY only one $t_{m}$ ? Because the point of the TLB is to skip the page-table walk entirely. The translation is already known, so the only unavoidable memory work left is fetching the actual data byte you asked for — that is one $t_{m}$ , the long red bar.

PICTURE. Green road = one short blue bar (search) + one long bar (data). No walk block.

$cost_{hit} = the search t_{TLB} + fetch the data t_{m}$

Step 5 — Price the MISS road (red): the walk

WHAT. On a miss, the translation is not cached, so the hardware must walk the page table to find the PFN. The parent note told us a walk costs $W$ memory accesses ( $W = 1$ for a single-level table, $W = L$ for an $L$ -level table). After the walk finds the PFN, we still do the one final data access. So the miss road pays: search + walk + data.

WHY the extra $W t_{m}$ ? Each level of the page table lives in DRAM. Reading one level = one $t_{m}$ . An $L$ -level table therefore costs $L$ memory reads before you can even fetch the data. This is the whole reason the TLB exists — to avoid paying $W t_{m}$ on every access. (Note: a miss is not a Page Fault — the page is in memory, we just re-look-up the map.)

PICTURE. Red road = short blue bar (search) + $W$ stacked memory bars (walk) + one final long bar (data).

$cost_{miss} = the search t_{TLB} + walk: W page-table reads W t_{m} + fetch the data t_{m}$

Step 6 — Merge the roads by their probabilities

WHAT. Now we glue the two prices back into one expected number. Each road is taken with its probability: the green road $h$ of the time, the red road $1 - h$ of the time. The expected (average) cost is each price times how often you pay it.

WHY multiply and add? This is just a weighted average — the honest way to answer "on a typical access, what do I pay?" If $98%$ of trips are cheap and $2%$ are expensive, your average trip is $0.98 \times (cheap) + 0.02 \times (expensive)$ .

PICTURE. Two bars, one scaled by $h$ (fat, green), one scaled by $1 - h$ (thin, red), summing to one average bar.

$EMAT = hit fraction h green price (t_{TLB} + t_{m}) + miss fraction (1 - h) red price (t_{TLB} + W t_{m} + t_{m})$

WHAT. Look at both prices: both contain $t_{TLB}$ (Step 2 said the search is always paid) and both contain a final $t_{m}$ (both roads end with one data fetch). Those are shared. The only difference is the walk $W t_{m}$ , which lives only on the red road.

WHY this simplification? Because pulling out the common floor makes the answer readable: it says "you always pay search + one data access, and then a walk penalty only on the miss fraction." Algebraically:

$h (t_{TLB} + t_{m}) + (1 - h) (t_{TLB} + t_{m}) = (h + 1 - h) (t_{TLB} + t_{m}) = t_{TLB} + t_{m} .$

The weights $h$ and $1 - h$ add to $1$ , so the shared part is paid in full, once. What survives from the red road is only its extra piece, weighted by $1 - h$ :

$EMAT = always search t_{TLB} + always one data fetch t_{m} + walk, only on the miss fraction (1 - h) W t_{m}$

PICTURE. A tall stack: a fixed floor ( $t_{TLB} + t_{m}$ ) that never changes, plus a small red cap $(1 - h) W t_{m}$ that shrinks as $h \to 1$ .

Step 8 — The edge cases (do the limits)

WHAT. A formula you trust must survive its extremes. Push $h$ to each end and $W$ up.

WHY. If the formula gave nonsense at $h = 1$ or $h = 0$ we would know we built it wrong. Checking limits is how you prove to yourself the picture is right.

Perfect TLB, $h = 1$ : the red cap vanishes, $(1 - 1) W t_{m} = 0$ , so $EMAT = t_{TLB} + t_{m}$ . Every access is as cheap as the green road. This is the dream.
Useless TLB, $h = 0$ : the cap is full, $(1 - 0) W t_{m} = W t_{m}$ , so $EMAT = t_{TLB} + t_{m} + W t_{m}$ . Every access walks — exactly the "no help" world the parent warned about.
Deeper page table, larger $W$ : the red cap grows linearly with $W$ . On x86-64, $W = 4$ , so a miss stings four times harder — which is precisely why a high $h$ is worth so much.

PICTURE. The red cap plotted against $h$ : a straight line falling from $W t_{m}$ (at $h = 0$ ) to $0$ (at $h = 1$ ), one line per value of $W$ .

The one-picture summary

Everything above compresses into a single diagram: the search floor, the fork, the walk on the red road only, and the merge that leaves a shrinking red cap on top of a fixed floor.

Recall Feynman: the whole walkthrough in plain words

Every time the CPU wants memory, it first peeks at its pocket sticky-note (the TLB) — that peek always costs a tiny bit of time ( $t_{TLB}$ ). Then the road forks. If the note has the answer (a hit, which happens most of the time, fraction $h$ ), we just go grab the data — one memory trip ( $t_{m}$ ). If the note is blank (a miss, fraction $1 - h$ ), we first walk all the way to the big map in the office — that's $W$ memory trips — then grab the data. Because both roads always include the pocket-peek and always end with one data grab, those two costs are just a fixed floor you always pay. The only thing that changes is whether you took the expensive office walk, and that happens only on the miss fraction. So the average cost is: floor ( $t_{TLB} + t_{m}$ ) plus the walk penalty $W t_{m}$ scaled down by how rarely you miss $(1 - h)$ . Make the note good ( $h \to 1$ ) and the penalty melts to zero.

Related: Cache (memory hierarchy) uses the same hit/miss-weighted-average idea; a Context Switch can drop $h$ suddenly by cooling the TLB.