Answers · How a program runs
Why does reading one byte from memory load 64 bytes?
In shortMemory hardware moves data in fixed sixty-four-byte blocks, so a one-byte read fetches the whole block; the extra bytes cost almost nothing because reaching the memory row costs most of the time.
Reading one byte loads sixty-four because the hardware has no smaller operation. Memory moves fixed blocks of sixty-four bytes, aligned to a sixty-four-byte boundary, so the request for one byte can only be served by fetching the block that contains it. There is no transaction anywhere in the machine that moves four bytes: the path from memory to processor, the caches, and the protocol that keeps cores consistent all speak in blocks. The cost is dominated by getting to the memory chip and opening a row there, not by the number of bytes sent back, so the other sixty-three bytes ride along for almost nothing.
Why the extra bytes are cheap
Price one fetch. The request takes 15 ns to leave the processor. Activating a row inside the memory chip takes another 45 ns, so 60 ns have gone before any data moves. The first eight bytes arrive at 65 ns; the remaining fifty-six arrive at 80 ns. The extra fifty-six bytes therefore cost 15 ns, about 0.27 ns per byte, while the first eight, if you divide the 65 ns by 8, cost 8.125 ns per byte. The full sixty-four bytes cost 80 ns against 65 ns for the first eight: eight times the data for 15 ns more. That is the trade: a small stake against another 65 ns of latency if the neighbours are needed later.
| step | stage | nanoseconds | bytes delivered so far | what happened |
|---|---|---|---|---|
| 1 | request leaves the processor | 15 | 0 | Travel to the memory controller and chip. |
| 2 | row activated in the chip | 45 | 0 | The expensive internal step: thousands of bits are sensed into a buffer. |
| 3 | first eight bytes returned | 65 | 8 | The first data arrives after most of the wait. |
| 4 | remaining fifty-six returned | 80 | 64 | Fifteen nanoseconds for another fifty-six bytes. |
This is the pricing that decides the block size. The row activation is already paid, so the marginal cost of the fifty-six extra bytes is small. A machine that fetched only the bytes you asked for would pay the same 65 ns to first byte and then need another transaction for the neighbour, and another. The block turns many potential waits into one.
The natural guess is that memory hands over exactly what you ask for, so reading a four-byte field should move four bytes. It does not. Take a million records of 64 bytes each and read one four-byte field from every record. Each record begins a fresh block, so the traversal touches 1,000,000 blocks. The traffic is bytes, or 64 MB. The useful bytes are bytes, or 4 MB. The amplification is . The other sixty bytes per record travelled the full distance, occupied cache space, and were never read. Asking how much data the program reads is therefore close to meaningless; the question that predicts cost is how many distinct blocks it touches and how much of each block it uses.
| stride in bytes | values used per block | bytes moved for a million values | nanoseconds per value |
|---|---|---|---|
| 4 | 16 | 4,000,000 | 1 |
| 16 | 4 | 16,000,000 | 4 |
| 64 | 1 | 64,000,000 | 10 |
| 256 | 1 | 64,000,000 | 11 |
| 4096 | 1 | 64,000,000 | 38 |
Check the first three rows against . A million contiguous four-byte values occupy 4,000,000 bytes. Divide by 64: blocks. Traffic is bytes. At a stride of 16 bytes, the values span 16,000,000 bytes, so blocks and bytes. At a stride of 64 bytes, each value lands in a new block: bytes. The last column moves from 1 ns to 10 ns per value, a factor of . Same arithmetic, same number of values, sixteen times the traffic and ten times the time.
Where the bet stops paying
The block bet fails when the next access lands in a new block and uses only a few bytes of it. A stride of 256 bytes or 4,096 bytes gives the same 64,000,000 bytes of traffic as a stride of 64, because one block per access is the worst case for traffic. The further rise to 38 ns at a stride of 4,096 comes from translation misses, not from the block size: blocks are skipped between accesses. Going in order also turns on the prefetcher, which watches a constant stride and fetches ahead, so sequential access beats the latency numbers alone. A pointer chase forfeits that: the next address is inside the current block, so the prefetcher cannot see it and the misses cannot overlap. The prefetcher also stops at the boundaries of the mapped region, typically every 4 KB, which is blocks, and starts again. If records are packed several to a block, the waste per record falls; if one record spans several blocks, it rises. The fixed unit is still the block, so the traffic is still .
Worth keeping
- Traffic between memory and processor is set by the number of distinct sixty-four-byte blocks touched, not by the number of bytes requested.
- A stride larger than sixty-four bytes makes every access touch a new block, so the same arithmetic can cost about ten times more.
- Sequential access is faster still because the prefetcher can fetch ahead, while a pointer chase cannot be predicted.
Where this goes next
This question is one step of Memory, All the Way Down, a course that works through its subject from the beginning. The page that teaches this part of it is It Fetches More Than You Asked For, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- Why does every program I run see the same memory addresses?A pointer's number is a private label for a block of memory, not a physical chip location, so two programs can use the same label for different places.
- How does the CPU avoid walking the page table on every single memory access?A small cache of recent translations, called the TLB, is checked on every memory access; a hit skips the page-table walk, and a miss walks once then stores the result.
- Why does 2 + 3 * 4 equal 14 and not 20?The multiplication is done first: three times four makes twelve, and only then is the two added, giving fourteen. Reading left to right would give twenty.
- How many samples does a profiler need before a percentage in the report means anything?It depends on how many samples landed on that line: you need a few hundred samples on the line you care about, because the relative error is roughly one over the square root of that count.
- If I make one part of my program twice as fast, how much faster does the whole program get?Less than twice as fast: only the share of run time you actually touch can improve, so the untouched remainder caps the gain, often at a few per cent.
- Why can two threads that each work correctly still give the wrong answer?Each thread reads the shared value and writes it back in two separate steps, so the other thread can run in between and one increment silently overwrites the other.