Here is one working set, on one machine, through one memory system, measured two ways:
$ cd courses/mem/assets/samples && ./build_samples.sh 2>&1 | sed -n '/3. LINE/,/the prefetcher/p'
A 64 MiB working set, 1,048,576 lines, entirely outside
every level of the cache:
pointer chase, random order 131.468 ns 0.487 GB/s
sequential sweep, +64 each time 3.463 ns 18.479 GB/s
the prefetcher, by subtraction 37.96x
The two differ by 38×, and neither is wrong. Both touch 1 048 576 lines, all 64 bytes of each, spread over the same 64 MiB of address space, and every one of those lines is supplied by the same DRAM. A program that believes “DRAM costs 131 ns” will make one set of decisions; a program that believes “DRAM delivers 18 GB/s” will make another; and both beliefs are supportable from this table while neither is the whole story.
The difference is a single property that is invisible in the numbers: whether the address of the next access can be computed before the current one has returned. In the chase it cannot — the address is the value that was just loaded, so each access waits for the previous one and the sequence is a chain of dependent loads. In the sweep it can, and a hardware prefetcher that recognises the stride issues the fetch for line i+k while the program is still consuming line i. The 38× is not the prefetcher's speed; it is the number of accesses that end up in flight at once instead of one at a time.
This is why the previous concept insisted on the rule before anything else was measured. Two functions four lines apart, one of which the compiler may even rewrite into the other, produce numbers 38× apart that both look like a property of the memory. Every “memory is slow” figure in the wild is one of these two measurements, and the advice that follows from the wrong one is worse than useless: latency cannot be fixed by moving fewer bytes, and bandwidth cannot be fixed by reordering the accesses.
Two bodies, and the difference between them is one instruction each:
a chase: the next ADDRESS comes from memory
mov (%p), %p /* p = *(void**)p */
dec %c
jnz 1b
a sweep: the next address comes from arithmetic
movdqu 0(%p), %xmm0
movdqu 64(%p), %xmm1
movdqu 128(%p), %xmm2
movdqu 192(%p), %xmm3
add $256, %p
dec %c
jnz 1b
The chase's cost is latency: each iteration's load cannot begin until the previous iteration's load has produced its address, so the measured ns-per-hop is the memory latency at that footprint. The sweep's cost is throughput: the address is known immediately, so the loop's rate is set by how many bytes the memory system can hand over per unit time once the prefetcher has a stream going. And the model that connects them is the one that makes the 38× a number rather than an anecdote:
Two consequences fall out of that, and both are testable. First, the chase's per-hop time is a genuine latency measurement and is the only clean one available here — which is why the next concept builds its whole curve out of chases. Second, the sweep is bounded twice: by DRAM bandwidth when the data is far away, and by the loop's own throughput when the data is close, and the second bound is easy to mistake for the first. That mistake has its own retraction, below.
There is a third quantity in the section, and it is the one that takes practice to read. A sweep can be made stride-aware, and the two rates that come out of it are not the same rate:
And the trap in the dense end of that table is worth stating before it appears, because it is the same loop-floor trap as the previous course's: at strides 4 and 8 the walk uses every byte of every line it fetches, so the two rows differ only in the loop's own per-element overhead and their order moves between runs. A table of nine rows therefore contains two different regimes, and reading a claim off a row without knowing which regime it is in is how the artifact ended up printing a sentence about monotonicity that was false — see the last section of this concept.
The 38× figure is a ratio, and this is the first place in the course where quoting a ratio rather than two absolute numbers pays off. Across the three runs shipped with the course:
chase (ns) sweep (ns) ratio run 1 131.468 3.463 37.96x run 2 132.627 3.464 38.28x run 3 133.637 3.469 38.52x the chase moves 1.6% across three runs and the sweep moves 0.2%, but the RATIO moves 1.5% and is the same claim every time.
And the full stride table, which is what a program's own access pattern actually looks like. The useful column is what the program wanted; the line column is what the memory system had to move:
$ ./membench 2>&1 | sed -n '/stride elements/,/16 to 1/p'
stride elements ns/element useful GB/s line GB/s
4 4194304 0.4525 8.84 8.84
8 2097152 0.5105 7.83 15.67
16 1048576 0.6418 6.23 24.93
32 524288 1.0097 3.96 31.69
64 262144 1.9267 2.08 33.22
128 131072 2.2488 1.78 28.46
256 65536 2.3908 1.67 26.77
1024 16384 4.8121 0.83 13.30
4096 4096 8.8147 0.45 7.26
'useful GB/s' counts the 4 bytes each element really
wanted. 'line GB/s' counts the 64-byte lines the memory
system had to move to supply them. At a 4096-byte
stride the system moved 256 KiB of lines to deliver
16 KiB of wanted data -- 16 to 1 -- and every one of
those lines was in a different 4 KiB page as well.
Three readings of that table, in increasing order of usefulness:
The last row is where a page-based access pattern lives. A stride of 4096 bytes means one 4-byte element per page, and the system moved 256 KiB of lines to deliver 16 KiB the program wanted — 16 to 1. The useful rate is 0.45 GB/s and the line rate is 7.26 GB/s, and neither of them is “the speed of memory”. They are what a program does to its memory system when it walks a page-strided structure, which is exactly what a naive linked list or a column operation on a row-major matrix does.
The two columns peak in different places, which is the first sign they are different quantities. The useful column peaks at the densest stride (8.84 GB/s at stride 4) and collapses to 0.45 by the sparsest — a factor of 19. The line column peaks in the middle (33.22 GB/s at stride 64) because that is the stride at which each fetched line is used exactly once and no line is fetched twice.
And a page is a bigger unit than a line, which the next two concepts turn into their subject. Every line in that last row was in a different 4 KiB page, and this machine's translation cache covers 64 of them. The row is therefore paying two costs at once: 16 to 1 on line traffic, and a translation for every element. Concept 5 isolates the second one; this table cannot, and says so.
Then there is the retraction, which is about what happens when a sweep's loop is the bottleneck. An early version of this table reported a steady 3.30 ns per line at every footprint from 256 KiB to 64 MiB — and a rate that is the same for L2-resident data and for DRAM data is the rate of a loop, not of a memory:
3. "Sequential reads sustain 64 GB/s." The units were wrong AND the loop was the bottleneck: the first version measured 3.30 ns per line at EVERY footprint from 256 KiB to 64 MiB, and a rate that is the same for L2-resident and for DRAM data is the rate of a loop, not of a memory. With four lines per iteration: 0.700 ns per line over a 4 MiB L2-resident region and 3.800 ns over 64 MiB of DRAM, i.e. 91.4 and 16.8 GB/s. THE SWEEP SATURATES, and this is the honest limit of the measurement rather than a property worth teaching as one: at 3 ns for four 16-byte loads the loop is a real part of the cost, so this instrument cannot report the bandwidth of an L2-resident region. The DRAM figure it does report is 16.8 GB/s, and the cache-resident figure comes from section 6's smallest row instead.
That is the most instructive retraction in the course, because the tell was in the shape rather than in the number. “Same cost at every footprint” is not a plausible property of a hierarchy: a two-level memory with a 19× latency spread cannot deliver a constant per-line rate unless something else is setting the rate, and the something else was the loop. Unrolling to four lines per iteration removed the loop from the denominator and the curve appeared — and the honest residue is that the sweep still saturates for L2-resident data, so this instrument reports 16.8 GB/s for DRAM and no bandwidth figure at all for the caches.
The first version of the paragraph that follows the stride table said the useful rate “falls monotonically with the stride”, and printed the two ends as evidence. It is false, and the way it is false is worth more than the fact:
The harness was asserting the same false thing, in the form of max(use) <= use[0] * 1.30 — “no stride is much more useful than a dense one” — and it failed on exactly the run where stride 8 outran stride 4. Both were fixed, and the fix was not a looser threshold: the check now asserts that the most useful stride is a dense one, which is true because a sparse stride pays a full line for four useful bytes, and it is a claim about the shape rather than about which of two noisy rows won.
The lesson generalises past this table. A column of nine measurements taken at nine different moments contains the clock's drift as well as the memory's behaviour, and a monotonicity claim is the easiest way to mistake one for the other. The artifact's own diagnostic is the one to steal: if a table is non-monotonic where the arithmetic says it must rise, that is not noise — it is a signal that either the loop or the layout is doing something the caption does not mention. It is how the layout bug from the previous concept was caught, and it is how this sentence was caught.
$ cd courses/mem/assets/samples $ ./membench 2>&1 | sed -n '/3. LINE/,/4. ASSOC/p' $ python3 crosscheck.py 2>&1 | sed -n '/^ --- group C:/,/^ --- group D:/p'
Then write the two bodies yourself, which is twenty lines and teaches more than the table does:
1. Allocate 64 MiB. Fill it with a permutation
cycle (the artifact's layout_of does this in
fifteen lines) and time one lap of
mov (%p), %p ; dec %c ; jnz
over 4 million hops. Then time a plain
`add $64, %p` walk over the same region.
(Expect a factor of tens. If you get anything
under 4x, check that the compiler did not
rewrite your chase: look at the disassembly,
and put the loop in inline asm if it did.
A deterministic xorshift sum is a benchmark
the optimiser will delete outright.)
2. Now make it a LATENCY curve instead of one
number. Shrink the working set from 64 MiB to
64 KiB in steps and watch the chase's per-hop
time fall in steps.
(Expect steps, not a slope: a hierarchy is
made of plateaus with cliffs between them.
This is the next concept's table, and seeing
it appear out of a twenty-line program is
the point.)
3. Measure the prefetcher by subtraction, which
is the only way to measure it here. Run a
sweep over a fixed footprint with one stream,
then with two interleaved streams 32 MiB
apart, then four.
(Expect the per-line rate to fall as the
streams multiply, because the prefetcher can
only track so many. The number of streams at
which it stops helping is a property of the
machine; the METHOD -- hold the footprint
fixed, add streams, watch the rate -- is the
part that transfers.)
4. Finally, break it: pass `--quick` and then
compare the two runs' tables. The absolute
numbers move, the ratios move much less, and
the ones that move most are the ones taken
from the loop-limited rows.
Exercise 1 is the one that makes the distinction physical. A chase is the only memory benchmark whose number cannot be flattered by the loop, the compiler, or the prefetcher, because the chain of dependent loads is the measurement: there is nothing to overlap, nothing to unroll away, and no stride for the prefetcher to learn. That is why this course uses chases for every latency claim it makes and sweeps only for the two throughput claims it is willing to defend.
Exercise 3 is the one that generalises to real code, because a prefetcher that stops helping at two streams is a reason to think about how many independent arrays a loop is walking, not a reason to rewrite the loop. The mechanism is not observable here — no PMU, no counter, no way to see a prefetch request — so the result is a difference and the explanation is a hypothesis. Saying so is part of the measurement: the subtraction gives a number, and the number does not name its cause.
The direct parent is the previous course's latency concept, and the relationship is a substitution. That concept measured a dependent chain of add r8,r8 and found 2.7× an independent operation, with a marginal cost of about one tick per link — a chain in registers, resolved inside the core at one cycle per link. This concept is the same measurement with the register replaced by memory: the chain still exists, the dependency is still what costs, and the marginal cost per link has gone from about 1 ns to 131 ns. The instruction-level parallelism that hid the register chain cannot hide this one, because there is nothing to issue until the address arrives.
That is also why that course's dependency concept had to end where it did, and this concept picks it up at the exact point: the previous course measured that a dependency is a constraint and not a cost, and that the hardware hides it by finding other work. Here the constraint is 131 ns deep and the hardware's answer is not to hide it but to avoid needing it — which is what a prefetcher is, and what a programmer should be thinking about when the answer is not available.
Two connections outward, both about what a page is. The object course measured that a section's alignment is stated in a header and enforced by nothing, and this course's last row is what happens when alignment is taken seriously: one element per 4096-byte page is 16× the line traffic the program needed. And the ELF course's program-header table is where the mapping that a page belongs to is written down — the file's statement of an alignment whose cost this course can now put a number on.
And the connection forward is the point of the whole module. This concept established that a chase measures latency and a sweep measures throughput, and 38× is the difference. The next concept takes the chase — the clean measurement, the one the loop cannot flatter — and runs it over twenty footprints from 512 bytes to 256 MiB. What comes out is a curve, and the interesting question about a curve is not where its steps are but how wide its plateaus are.