CPU·IV The machine Chapter 34 of 65

Near and far

If a processor cycle were stretched to a second, fetching a number from main memory would take five minutes, reaching the hard disk a year, and an answer from across the ocean sixteen years. This chapter is a walk through that scale model, from a register to another continent and back, with measurements on the course server.

University 55 minutes Computer architecture History

CPU·IV

The machine

Builds on: 33 · An X-ray of Python 14 · How a list lives in memory

What you will take away

estimate the order of latencies from a register to the network and understand what a miss costs
explain why code of the same complexity runs at different speeds, and walk through data in memory order
build a cache with LRU eviction and know where it helps and where it doesn’t

Chapter 33 ended with a mystery. Summing a matrix by rows and summing it by columns is the same work: the same sixteen million additions, the same machine instructions, only the two loops have swapped places. Yet the walk by columns came out several times slower. If the instructions are the same, the difference must lie in where they get their numbers: some of the numbers lie near, others far away.

These distances are hard to feel. A memory access takes less than a microsecond, and to a human a microsecond is nothing. The Solar System poses the same problem: in kilometers it is beyond imagining, but if the Sun is a ball and the Earth a pea twenty paces away, the picture comes alive. We will build the same kind of scale model for memory, stretching time so that one processor cycle lasts a second, and walk along that scale from a register to another continent. On the way we will find out why columns are slower than rows and how programs keep distant things close at hand.

If a cycle were a second

A processor running at 3.3 gigahertz completes a cycle in 0.3 nanoseconds. That will be our second. The numbers in the model below are typical orders of magnitude: Peter Norvig gathered them in a table for his essay “Teach Yourself Programming in Ten Years” (2001), and Jeff Dean of Google in his talks around 2010. Each machine has its own figures, and they change over the years, but the orders of magnitude have held for decades, and for estimates that is what you need.

A scale model of latencies. On the left is the time of one access, on the right the same time in the model. The switch changes the scale: a cycle as a second, a cycle as a 75-centimeter step, or the distance light travels in a vacuum in that time. The bars use a logarithmic scale: each division is ten times farther than the one before. At the bottom is a calculator of the average access time.

A register is one second: the number is already in your hand. The first-level cache, L1, is three seconds: reach for something on the desk. L2 is about ten seconds, and L3 under a minute: get up and walk to a shelf in the next room. Main memory is five and a half minutes: go downstairs to borrow salt from the neighbors. That is still fast. Reading a small piece of an SSD takes four days. Asking a server in the next rack of a data center takes almost three weeks. A hard disk needs a whole year to move its head to the right track. And a packet across the ocean and back travels for sixteen years, long enough for children to grow up.

Switch the model to steps, and you get the same walk in space. L1 is three steps away, main memory two hundred and fifty meters, an SSD two hundred and fifty kilometers, a hard disk more than half the equator, and a packet across the ocean almost the distance to the Moon.

The calculator at the bottom of the widget shows what follows. Almost any program goes to memory billions of times. If its data is usually close by, in L1, the average access time is close to a nanosecond. If even one access in twenty goes out to main memory, the average grows several times over, and if most accesses miss, the processor spends nearly all its time standing and waiting. The average is computed as $t = h \cdot t_{\text{L1}} + (1 - h) \cdot t_{\text{RAM}}$, where $h$ is the share of accesses that find their data close by. With the factor of 100 in the second term, even a small share of misses decides everything. The “by rows” and “by columns” buttons put in $h$ for the matrix walks of Chapter 33; where “15 of 16” comes from will become clear two sections on.

A nanosecond in your pocket

Grace Hopper, a mathematician, a rear admiral in the US Navy and the author of FLOW-MATIC, the language COBOL was built on, spent many years lecturing to students, officers and engineers. She wanted to explain where delays come from: why, for instance, a satellite link doesn’t answer at once, and why it pays to make computers smaller. As she told it, she asked the engineers: “Please cut off a nanosecond and send it over to me.” What she got was a piece of wire 11.8 inches long, about 30 centimeters, the distance light travels in a billionth of a second. She handed out such wires at her lectures by the bundle.

Next to the nanoseconds she showed a microsecond, a coil of wire 984 feet long, about 300 meters, and urged programmers not to waste even a microsecond. Picoseconds she handed out as grains of ground pepper. A bundle of her “nanoseconds,” about a hundred wires from a 1985 lecture, is kept at the National Museum of American History in Washington.

Switch the model to “how far light gets.” In one cycle, nine centimeters; in one L1 access, Hopper’s wire. For a signal to reach memory and come back within a few cycles, memory has to sit within centimeters of the circuits that compute, and a signal in a wire travels slower than light in a vacuum. That is why the fastest levels of memory live on the processor chip itself, next to the ALU.

Main memory is slow for more reasons than distance: in its hundred nanoseconds light would cover thirty meters. The cell also has to be found by its address and read, and its faint signal amplified. A large memory can’t be made fast: the more drawers there are, the longer the way to each one. For a network, though, distance is the main limit, and nothing removes it. From New York to London is about 5,600 kilometers in a straight line, and light in optical fiber covers roughly 200,000 kilometers a second. So a round trip takes at least 56 milliseconds, however fast the servers are. That is the limit Hopper’s wires were a reminder of.

The memory staircase

Making all memory as fast as registers is impossible: fast memory comes only small and expensive. A processor has hundreds of bytes of registers, tens of kilobytes of L1 per core, from hundreds of kilobytes to a few megabytes of L2, tens of megabytes of L3 shared by all the cores, gigabytes of main memory and terabytes of disk. Each step is tens, even thousands, of times larger than the one above it. It is a few times slower while we stay inside the processor and main memory, and hundreds or thousands of times slower once we go down to the disks. This staircase is called the memory hierarchy, and the time from a request to its answer is called latency.

The steps L1, L2 and L3 are caches: small, fast stores of copies from the large, slow memory. A program knows nothing about them and asks them for nothing. It reads from an address, and the processor itself looks for the byte first in L1, then in L2, then in L3, and only then goes to main memory, leaving copies along the way. To find out which caches the machine running the course sandbox has, you can ask the system.

The figures depend on the processor. There is also a way to see the staircase without asking anyone: measure it. Take an array and turn it into one big ring: each cell holds the number of the next one, and the numbers are shuffled at random. This is a linked list from Chapter 14 with its nodes scattered over memory. The only way through it is one step at a time: until you have read a cell, you don’t know where to go next. The time of one step therefore shows the latency of memory in its pure form. We will make the array larger and larger and watch for the moment it stops fitting on each step of the staircase.

The line climbs in steps. While the array fits in L1, a step costs a couple of nanoseconds (most of that is the loop itself). When the array outgrows L1, the time jumps several times over, then again at the boundaries of L2 and L3, and beyond the caches it climbs past a hundred nanoseconds: that is main memory. On our server it came to about 2 nanoseconds at the start and over 200 at the end, a factor of a hundred, as the model promised. In your run the steps may move: they show the cache sizes of whichever machine the sandbox is running on.

The cache line

Now the mystery of the matrix can be solved. Memory doesn’t travel to the cache one byte at a time but in chunks. Such a chunk is called a cache line, and on most processors it is 64 consecutive bytes (128 on Apple processors; the cell above showed the line size on our server). When the byte you need isn’t in the cache, you get a cache miss: the processor waits while the whole line arrives from memory. In return, the following accesses to its neighbors are hits, almost free.

The matrix of Chapter 33 lies in memory row after row, four bytes per number. The walk by rows runs along memory: one miss brings in sixteen numbers, and the next fifteen accesses are hits. That is where the “15 of 16” in the model’s calculator comes from. The walk by columns jumps a whole row of the matrix at a time, 4096 numbers or 16 kilobytes. Every access lands in a new cache line. The neighboring column will want each of those lines again on the next lap of the outer loop, but in the course of one column the walk has touched 4096 different cache lines, 256 kilobytes, and by the time it comes back our line has long been evicted from L1. A miss on every step.

On a small scale you can watch it happen. Below, a matrix passes through a cache that holds a few lines: a red dot is a miss, a green one a hit, and the shaded cells are those whose lines are in the cache at the moment.

A matrix in a small cache. The thin marks inside the rows of the matrix are the boundaries of cache lines. The cache is fully associative and evicts whatever has gone unused the longest. Change the order of the walk, the size of a line and the number of lines in the cache.

Compare three walks on an 8 × 8 matrix with lines of 4 numbers and a cache of 4 lines. By rows: 16 misses out of 64, the least possible, since every cache line is loaded once. By columns: 64 misses out of 64. Then, keeping the walk by columns, enlarge the cache to 8 lines. The misses drop back to 16: the first column loaded 8 cache lines, and the next three columns find everything at hand. The walk by columns, then, hurts only when a column doesn’t fit in the cache. The third order, in tiles, walks the matrix in square blocks the size of a cache line, by columns inside each block, and also reaches the minimum. Fast programs for multiplying and transposing matrices work this way, and so will your solution to one of the tasks at the end of the chapter.

The same experiment can be run in Python. The sandbox has a module, cs.cachesim, in which a matrix lies the way it would in memory, row after row, and every access goes through a model of a cache and gets counted.

512 misses against 4096, eight times fewer, as many as there are elements in a cache line. On hardware the times differ by less than a factor of eight: the processor notices that the program is moving through memory in order and fetches the next lines ahead of time. But that only helps when the walk is predictable.

Near in time, near in space

A cache holding a fraction of a percent of memory helps almost any program, and the reason is a property of programs themselves, called locality. Locality in time: what was accessed recently will probably be needed again, like a loop counter, a running sum, the top of the stack. Locality in space: after address $x$ you will probably need $x + 8$, the next element of an array, the next instruction of a program. Cache lines profit from the second kind, and evicting what has long gone unused profits from the first.

Seen this way, the data structures of Part II of the course look different. A Python list is an array of references stored one after another, and walking it suits the cache well. The linked list of Chapter 14 is a chain of nodes scattered over memory: every hop is a potential miss, and the staircase experiment showed what that costs. The hash table of Chapter 16 scatters keys as randomly as it can on purpose, so every lookup is probably a miss, yet that is still one or two cache lines instead of twenty hops down a tree. An estimate like $O(n)$ doesn’t see these differences: it counts steps, not distances. Two algorithms with the same asymptotics can differ in speed several times over, depending on how they move through memory.

Walk through data in the order it lies in memory, and come back to it while it is still in the cache. Loop order is a free optimization: the same number of operations, less waiting.

Timing in three languages

In Chapter 33 the walk by columns in C came out about six times slower. Here is the same experiment in pure Python and in numpy.

In pure Python the difference is smaller than in C and jumps around from run to run: we saw anything from ten percent to a factor of two. The reason is in Chapter 33: on each addition the interpreter spends tens of nanoseconds on its own work, and the wait for memory gets lost in it. Besides, a list of lists holds references to objects scattered over memory, so there are plenty of misses in both orders. In numpy the numbers lie side by side, eight bytes each, there is almost no work of its own, and the difference comes out large: for us, about ten times, sometimes less, sometimes more. The strides attribute tells how many bytes you must move in memory to go one cell along each axis: 8 along a row, 24,000 along a column. The less work a language does of its own, the more the wait for memory shows.

Where to put a line

So far our cache could put any line in any place. Processor caches are almost never built like that. Finding a line in the cache means comparing its address with every address stored there, and comparing thousands of addresses in one cycle is expensive. That is why a processor cache is divided into sets. The number of the set is computed from the line’s address, for example as the remainder after dividing by the number of sets, and a line can only go into its own set, into one of a few places. If a set has one place, the cache is called direct-mapped; if it has eight, eight-way set-associative; and if there is one set for the whole cache, fully associative.

Sets have a price: two addresses that fall into the same set can keep pushing each other out even when the rest of the cache is empty. Here are two arrays of 32 numbers, one right after the other, and a program that adds them element by element.

With direct mapping, a[i] and b[i] always fall into the same set: their addresses differ by 32, which is eight sets of four numbers. Every access knocks out the line that will be needed next, and there are no hits at all. Two places in a set already save the day. That is why processor caches are built with several ways, and why programmers who fight for speed avoid arrays whose size is a large power of two: such arrays are more likely to tread on each other’s sets. In the task “Cache simulator” you will write a cache like this yourself.

Whom to evict

A cache is always full: once a program has run for a little while, every place is taken. Each miss forces a decision about whose line to throw out to make room. The obvious rule is to throw out the line that has gone unused the longest. If there is locality in time, what was forgotten long ago will most likely stay unneeded. This rule is called LRU, for “least recently used.” There are others: throw out whoever came first (FIFO), or a random one.

The rule that cannot be beaten was described in 1966 by László Bélády of IBM, who was studying eviction in virtual memory: throw out the one that will be needed latest of all. The trouble is that it requires knowing the future. In practice Bélády’s rule serves as a yardstick: practical rules are measured against it by running the same recorded requests through all of them.

Four eviction rules on the same requests. The letters can stand for anything: lines of memory, pages of a website, a function’s answers. The table at the bottom counts the misses for every rule at once; you can type in your own requests, separated by spaces.

Start with “favorite”: A is requested every other time. LRU keeps it in the cache throughout and misses 7 times out of 12, while FIFO at one point throws A out only because it came first, and pays with an extra miss. Now choose “loop” with three places: four letters going around in a circle. LRU misses on every request: by the time a letter is needed again, it is the oldest one and was thrown out a moment ago. The random rule beats LRU here almost by a factor of two. This is LRU’s weak spot, and it is worth remembering: if a program cycles through data slightly larger than the cache, LRU throws out whatever will be needed next. The walk by columns that opened this chapter behaves the same way. Set four places, and all the rules come out equal: the loop fits.

Python has a ready-made cache with LRU eviction, the functools.lru_cache decorator. Like the memoization of Chapter 22, it remembers a function’s answers, but it keeps no more than the maxsize most recent ones and throws out the old.

Seven misses and five hits, as with LRU on “favorite” with three places in the widget. The last line shows that the @cache of Chapter 22 is the same lru_cache, only with maxsize=None: it throws nothing out and grows without limit. For recursion with memory that is what you want. For a server that remembers answers to its users’ requests it is a memory leak: after a month of running, the cache will eat all the RAM. There you need a limit and an eviction rule.

Caching as a general idea

Keeping a copy of something distant close at hand is an idea that works on every step of our scale, inside the processor and far beyond it. The memoization of Chapter 22 keeps the results of computations at hand, and “far” there means the time it would take to compute them again. The operating system keeps recently read pieces of the disk in main memory, so a file opened a second time is read instantly (more on this in Chapters 38 and 40). Your browser keeps the images and scripts of sites you have already visited on your disk.

This website is an example too. Photos and the heavy materials of the courses are stored in DigitalOcean Spaces, in a data center in Frankfurt, and the pages link to them through the address cdn.legost.in. This is a content delivery network, or CDN: its servers stand in many cities and keep copies of the files, so the answer comes from the nearest one rather than from Frankfurt. When we checked the response headers for one of the blog’s photos, they included cache-control: max-age=3600, which lets the browser go an hour without asking for the picture again, and cf-cache-status: HIT: the copy was found at a node of the delivery network, and the request never reached the storage. You can see such headers in your browser’s developer tools, on the Network tab.

All these caches share one difficulty: a copy can go stale. If a photo in the storage is replaced, the browser will keep showing the old one for an hour, and the nodes of the delivery network will do so until they check the original. No wonder the programmer Phil Karlton is credited with the saying “There are only two hard things in Computer Science: cache invalidation and naming things.”

Tasks

Write a class LRUCache. The constructor takes a capacity capacity (at least 1). The method get(key) returns the value for a key, or None if there is no such key. The method put(key, value) stores a value or updates the old one; if there are now more keys than capacity, it throws out the one that has gone unused the longest. Both get and put count as a use.

Each operation must take $O(1)$ on average: in the last test a cache of 50,000 keys handles 300,000 operations within three seconds.

You need two things at once: finding a key in $O(1)$, which calls for a dictionary, and knowing the order of use, which calls for a queue you can take an item out of from the middle. A list won’t do: remove from the middle is $O(n)$, as you saw in Chapter 14.

A Python dictionary remembers the order of insertion. If on every use you delete the key and insert it again, it ends up at the end, and the least recent key is at the start: next(iter(d)). Handier still is collections.OrderedDict with its methods move_to_end(key) and popitem(last=False).

Inside, an OrderedDict is a dictionary plus a doubly linked list from Chapter 14: the dictionary finds the node, the list keeps the order, and moving a node to the end takes a couple of reference reassignments. This is the classic design of an LRU cache. The catch in the task is the update: put on an existing key must make the key fresh without throwing anyone out.

Write a function count_misses(trace, line, sets, ways) that counts the cache misses on a trace of accesses. trace is a list of addresses in bytes. A cache line is line bytes long: address a lies in line number a // line. The cache consists of sets sets; line number $k$ can only go into set k % sets, which has ways places; if the set is full, the line that has gone unused the longest is thrown out of it. The cache starts out empty.

You may not use the cs.cachesim module: that is the module you are writing. The last test has a trace of a million addresses, with four seconds allowed.

First turn the address into a line number, then the line number into a set number. Each set is a little LRU cache with ways places, as in the previous task, only without values.

In the second example lines 0 and 4 fall into the same set ($0 \bmod 4 = 4 \bmod 4 = 0$), and the set has only one place, so they knock each other out. With ways=2 there would be two misses.

Fourteen lines, and you hold a tool that processor architects use: before they build a cache in silicon, they test it on recorded traces of working programs. By changing line, sets and ways while keeping the total size, you can watch the misses grow from crowding in the sets, and by running the trace with Bélády’s rule, see how much LRU loses against the ideal.

The matrices Matrix from the cs.cachesim module lie in memory row after row, and every get and set goes through a shared cache of 32 lines of 8 numbers. Write two functions that make do with a minimum of misses:

col_sums(m, n) returns the list of column sums of an $n \times n$ matrix m; for $n = 64$, at most 600 misses;
transpose(a, b, n) writes the transpose of a into b, that is, b[j][i] = a[i][j]; both matrices go through the same cache; for $n = 64$, at most 1200 misses.

The functions must work for any $n$, multiple of eight or not: the tests also check transposition for $n = 128$ (at most 4600 misses) and for $n = 100$ (at most 3600). The contents of the matrices may be read only through get and set. The starter holds straightforward versions: their answers are right, but they make too many misses.

col_sums: set up all $n$ sums at once and walk the matrix by rows, adding each number to the sum of its column. There are as many sums as columns, and the walk follows the order of memory.

transpose can’t be rescued that way: if you read a by rows, you have to write b by columns, and vice versa. Swap the loops, and the misses stay the same. The way out is tiles, as in the grid widget: handle an $8 \times 8$ block completely while its lines are in the cache for both a and b.

Four loops: the two outer ones step over the corners of the blocks by 8, the two inner ones over the cells of a block. When $n$ is not a multiple of eight, handle the edges with min(start + 8, n).

For $n = 64$, column sums by rows make 512 misses, one per cache line, the least possible. Transposing in blocks makes 1024: each cache line of a and of b is loaded once, while the straightforward version makes 4608. An $8 \times 8$ block touches eight cache lines in a and eight in b, 16 of the 32 places in all, and everything it needs stays close by until its work is done. With $4 \times 4$ blocks there would be 1536 misses: each cache line of b is filled in two visits and has time to be evicted in between. Fast linear algebra libraries such as BLAS, to which numpy hands matrix multiplication, also work in blocks.

What next

The walk has ended where it began, at the registers. The processor, it turns out, spends most of its time waiting for data, and its whole cache rests on programs being predictable: once a program has touched one place, it will soon touch the neighbors. The processor adapts to the program too: it notices a sequential walk and fetches lines in advance, without waiting to be asked.

It goes further. So as not to sit idle while data travels from memory, the processor guesses which way the next if will turn and starts executing instructions ahead of time. When it guesses right, it wins; when it guesses wrong, the results are thrown away as if nothing had happened. Almost nothing: traces remain in the cache. And this chapter has shown that the time an access takes gives away whether data lies near or far. So the processor, guessing the future, sometimes gives away other people’s secrets. How this works, and how it turned into one of the loudest vulnerabilities in history, is the subject of Chapter 35.