A cache never fetches a single byte. It fetches a whole 64-byte line, so the value next to the one you just read is already there. This lecture builds a cache, shows that reading in order is eight times cheaper than jumping a line at a time, and applies it to a table of prices.
Memory comes in lines
Fetching from memory has a fixed cost no matter how many bytes you ask for, so hardware asks for a lot at once. Memory is cut into blocks of 64 bytes, and the cache always loads and evicts whole blocks. Picture a lift that carries 64 bytes up to the cache: if the lift is going up anyway, it costs nothing to take your neighbours along, and the next time you need one of them it is already upstairs.
A block of consecutive bytes, 64 on most processors, that the cache loads and evicts as one unit. Line number n holds the bytes from 64n to 64n + 63.
Every byte has an address, a number that says where it is. To find the line of an address, divide by the line size and drop the remainder. The code below prints the line of four addresses.
line_bytes = 64for address in (0, 63, 64, 130): print(address, "is in line", address // line_bytes)
0 is in line 0 63 is in line 0 64 is in line 1 130 is in line 2
Addresses 0 and 63 share line 0, so once one of them is loaded the other is free. Address 64 starts line 1, and 130 is in line 2. Everything in this topic follows from that integer division.
A cache is a table of slots
The simplest cache is a table with one slot per line it can hold. A 32 KB cache with 64-byte lines has 512 slots. Each line of memory is allowed in exactly one slot, found by a remainder: line number modulo the number of slots. That is called a direct-mapped cache. Because many lines share a slot, the slot also keeps a tag that says which line it holds right now.
- 1Find the lineDivide the address by the line size.
- 2Find the slotTake the line number modulo the number of slots.
- 3Compare the tagIf the slot holds this line, it is a hit.
- 4Replace on a missLoad the line into the slot and forget the one that was there.
That is the whole cache. The class below is a complete, working version in fifteen lines. We read four neighbouring values, then the next line, then go back to address 0.
def line_of(address, line_bytes): return address // line_bytesclass Cache: def __init__(self, size_bytes, line_bytes): self.line_bytes = line_bytes self.n_lines = size_bytes // line_bytes self.tags = [None] * self.n_lines self.hits = 0 self.misses = 0 def access(self, address): line = line_of(address, self.line_bytes)1 slot = line % self.n_lines if self.tags[slot] == line:2 self.hits += 1 return True self.misses += 1 self.tags[slot] = line return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")
[False, True, True, True, False, True, True, False, False] 5 hits and 4 misses
- 1The slot is the line number modulo the number of slots.
- 2A hit means the tag in the slot is this very line.
Read the list of flags: the first read misses and loads line 0, the next three reads hit because they are in line 0, 64 misses and loads line 1, 72 hits, and going back to 0 hits again because line 0 was not evicted. Then address 512 is line 8, which maps to slot 0 as well (8 modulo 8), so it evicts line 0, and the last read of address 0 misses again: seven hits would have been possible, but one conflict cost us a miss.
A 512-byte cache with 64-byte lines has only 8 slots, not 512. Forgetting to divide the size by the line size is the usual way to build a cache that looks huge and behaves wrongly.
Reading in order against jumping
Now use the cache. A float64 value takes 8 bytes, so a line holds eight of them. Read an array in order and the first read of each line misses and the next seven hit: one miss in eight. Read it with a stride, which means skipping a fixed number of values between reads, and the reads land in different lines. The next code measures the miss rate for strides of 1, 2, 4, 8 and 16 values.
def sequential_trace(n, elem_bytes): return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride): return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64): cache = Cache(size_bytes, line_bytes) for address in trace: cache.access(address) return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16): print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))
stride 1 values: 0.125 stride 2 values: 0.25 stride 4 values: 0.5 stride 8 values: 1.0 stride 16 values: 1.0
The miss rate doubles with each doubling of the stride until it reaches 1.0: with a stride of 8 values the jump is 64 bytes, a whole line, so every read opens a new line and the cache saves nothing. A bigger stride cannot be worse than that, only equal. The pattern is the formula below.
On almost all x86 and server ARM chips, yes. Some chips use 128 bytes in an outer cache, so measure the line size of the machine you target. Our cache takes it as a parameter so you can try both.
The layout of a table decides the stride
A table of daily bars has five numbers per day: open, high, low, close and volume. Store it row by row, as most programs do, and the five numbers of a day sit side by side. To read only the closes you then skip four values between reads: a stride of 5, which is 40 bytes. Store each column on its own and the closes are one after another: a stride of 1. Same numbers, same reads, different layout.
closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout: ", as_rows)
column layout: 0.125 row layout: 0.625
Five times as many reads miss when the closes are strided. That does not change the answer of your program, only its speed, and no profiler line of arithmetic will show it: the extra time is spent waiting for memory.
What you will build
The lab asks for the pieces you just read, in the same order, and ends with the study on the real SPY table.
- Function · questionBuilds on
- line_of(address, line_bytes)Which line holds this address?Integer division
- Cache(size_bytes, line_bytes).access(address)Is this read a hit?line_of
- sequential_trace(n, elem_bytes)Which addresses does an in-order read touch?Plain arithmetic
- strided_trace(n, elem_bytes, stride)Which addresses does a jumping read touch?Plain arithmetic
- miss_rate(trace, size_bytes, line_bytes)What share of a trace misses?Cache
- study(bars)What does the row layout cost for the SPY closes?miss_ratestrided_trace
Next topic: a direct-mapped cache has a weakness this lecture touched on, the conflict between lines that share a slot. In Associativity and conflict misses you give each slot several places, and see why a table whose rows are 4096 bytes apart can ruin a cache.
Lab · what's graded
6 tasks · 100 pts- The line of an address10 pts
- A direct-mapped cache25 pts
- An in-order read10 pts
- A strided read10 pts
- The miss rate of a trace20 pts
- The study on the SPY table25 pts