A Few Hundred Entries Decide Whether Your Program Falls Off a Cliff

Last timeThe Address Is Not the Address

Translation would cost four memory reads per access if it were not cached. The cache is tiny, it covers a fixed amount of memory, and programs that outgrow it slow down suddenly.

The price of a miss

The previous lesson ended with an uncomfortable fact. On a common 64-bit

machine the map is four levels deep, each level lives in memory, and so a

translation that nothing has cached costs four memory reads before your own

read can be issued.

Price that honestly. If all four reads went to main memory at around eighty

nanoseconds each, one load would cost four hundred nanoseconds of looking

followed by eighty of reading. Every program would run at a fifth of its speed

and nobody would have built this.

Two things rescue it. The table entries are ordinary memory, so they sit in the

ordinary data caches like anything else, and the upper levels are reused by

every address in a huge region, so they are almost always warm. And the result

of the whole walk is remembered in a dedicated cache, so the walk itself is

rare.

FIG 1Where the shortcut sits

Three paths with costs about two orders of magnitude apart. Which one you are on is decided entirely by how your program walks memory, and nothing in the source distinguishes them.

The cache nobody mentions

The structure at the top of that diagram is a small associative cache of recent

translations. Every memory access consults it, which places a hard limit on how

big it can be: it must answer in a fraction of a cycle, in parallel with the

start of the data cache lookup, and the time to search an associative structure

grows with its size.

So it is small. Typical machines have on the order of sixty to a hundred

entries in the fastest level and a thousand to three thousand in a second,

slightly slower level. Compare that with a data cache holding tens of

megabytes. This is one of the smallest and most consequential structures in the

machine, and most programmers have never heard of it.

FIG 2What the cache can cover

: the amount of memory whose translations can be held at once
: the number of entries in the translation cache
: the block size, four kilobytes by default

One multiplication, and it is the most useful number in this lesson. It says how much memory your program can be touching before translation stops being free, and it has nothing to do with how much memory the machine has.

How much memory it covers

Put numbers in and the problem becomes obvious.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents