The previous concept measured how many lines fit in each level, and the answer was a curve. That curve is what a cache does when the accesses are spread over all of its sets, which is what a random permutation over a large footprint does. Real programs are not random permutations. They index arrays, they walk matrices, they nest structures, and the arithmetic of those addresses decides which set each access lands in — and a cache is a set of small fully-associative memories, not one big one.
The consequence is measurable, and it is one of the few places in this course where a prediction can be written down before the measurement and then confirmed by it. On this machine:
$ cd courses/mem/assets/samples && ./build_samples.sh 2>&1 | sed -n '/4. ASSOC/,/group C/p'
/sys says: L1d is 8 ways, 64 sets, 64 B line.
therefore lines a multiple of 4096 bytes apart share an
L1d set, and 9 of them cannot coexist in 8 ways.
PREDICTION, before the measurement: the cost must rise
between 8 and 9 lines at stride 4096, and must NOT
rise at stride 4160, which spreads them over distinct sets.
lines aliased spread ratio
4 1.661 1.544 1.08x
6 1.661 1.717 0.97x
7 1.520 1.564 0.97x
8 1.541 1.573 0.98x
9 7.240 1.714 4.22x
10 6.150 1.593 3.86x
12 6.327 1.446 4.38x
16 6.255 1.525 4.10x
24 6.342 1.392 4.56x
32 6.218 1.588 3.92x
Nine lines — 576 bytes of working set — cost 4.22× the same nine lines laid out differently, and any one of those lines would fit in the L1d fifty-six times over. No capacity explanation survives that: the working set is smaller than the previous concept's smallest measured footprint, and the previous concept measured that footprint at L1 speed. The difference is entirely in the addresses within each 16-bit slice of the low bits, and that is what associativity means.
The second thing to notice is the control, and it is the reason this table is stronger than its numbers look. The two layouts in every row hold the same number of lines and span the same 131 072 bytes. They differ by one thing: which set each line lands in. That is what turns a measurement into an experiment, and it is what makes the phrase “a conflict miss” mean something specific here — a miss that has nothing to do with capacity and everything to do with the low bits of an address.
The arithmetic is short enough to do in your head, which is why it is worth doing before running anything:
The address arithmetic gives a second number, and it is the one the artifact prints because a reader needs it to design a control: the aliasing stride is sets × line, and one set holds ways × line bytes — 4096 and 512 here. A layout at stride 4096 puts every line in set 0. A layout at stride 4160 — 4096 plus one line — advances the set by exactly one per line, so 32 lines cover 32 distinct sets and no set is asked for more than one line. Same footprint, same stride magnitude, same number of lines, opposite result.
And the model predicts the shape of the onset, not just its existence. This is where a capacity curve and a conflict curve can be told apart:
Two limits of this model matter for reading the table honestly. First, it predicts the onset and the plateau, and it does not predict where the plateau sits: whether the thrashing nine lines land in the L2 or the L3 depends on the replacement policy and on what else is in flight, and neither is in /sys. Second, “cache” here means L1d on this machine, and the same arithmetic with different constants applies to the L2 and the L3 — 1024 sets at 4096 bytes gives an L2 aliasing stride of 65536 bytes, and the L2 is shared between the SMT siblings of a core, which is why its shared_cpu_map line says so.
The prediction, and then what happened to it:
$ ./membench 2>&1 | sed -n '/at exactly 8 lines/,/group C/p'
at exactly 8 lines the aliased layout costs 1.541 ns
against 1.573 ns for the spread layout, a ratio of 0.98x.
At 9 lines it costs 7.240 ns against 1.714 ns, a ratio of
4.22x. A working set of 576 BYTES is now costing L2
latency, and it would fit in the L1d 56 times over.
The worst row in the aliased column is 9 lines, at
7.240 ns -- worse than the 32-line row. /sys publishes capacity and
not policy, so the replacement policy cannot be read off
from it, and the shape INSIDE the thrashing regime is not
explained here. That is a limit, not a result.
--- group C: the associativity predicted from /sys
[PASS] at `ways` lines the aliased layout is not slow yet a working set that fits the ways costs L1
[PASS] at ways+1 lines the aliased layout IS slow the onset is where /sys says it must be
[PASS] the spread layout never slows down at these counts by construction it never puts two lines in one set
[PASS] the step is a step, not a ramp one extra line is enough; there is no gradual onset
Four readings, in the order the numbers support them.
The onset is at 9, and the table's own justification for that claim is the arithmetic rather than the data. 8 ways means at most 8 lines per set; 9 aliased lines can only be 7 hits and 2 misses at best, and the measured ratio goes from 0.98× to 4.22× in one row. A model that predicted a ramp — progressive eviction, a gradual slope — is refuted by the fact that the row before the step is at 0.98×, i.e. indistinguishable from the control. One line is the difference between “as fast as an L1” and “L2 latency”.
The control is flat, and that is the load-bearing half of the experiment. The spread layout at 9, 10, 12, 16, 24 and 32 lines never exceeds 1.15× the L1 reference, because by construction it never puts two lines in one set. Without it, the 9-line result would be a number; with it, the 9-line result is a difference between two layouts that differ only in their low address bits.
The plateau is at L2 latency, not L3, and the model does not predict which. 7.24 ns is the L2 band from the previous concept (4.77–5.50 ns) plus the loop, not the L3's 19–25 ns. That is what a set conflict looks like: the lines are evicted from the L1 and land in the next level down, whose own sets are large enough (1024 of them) that 9 lines cannot conflict there.
And the worst row is 9 lines rather than 32, which the model does not explain and the artifact declines to explain. A prediction of “more lines, more misses” would put the peak at 32; measured, the peak is at the onset and the plateau thereafter is slightly lower. The honest reading is the artifact's own: that is a limit, not a result, and the reason it is a limit is that the replacement policy is not in /sys and the miss count is not available without a PMU. What can be said is that the shape inside the thrashing regime is not a simple function of the line count, and that anyone who needs it has to measure it on their own machine.
This section's real lesson is a retraction, and it is the most dangerous kind of wrong number in the whole course: the effect was real, reproducible, and attributed to something else. An earlier draft of this table measured a 5.28× slowdown for “256 lines at a 4096-byte stride” and reported it as the cost of address translation — a TLB effect, since 256 lines at one per page is 256 pages and the TLB holds 64.
The number was real. The interpretation was not, and the giveaway was in the layout function:
the offending layout put line i at
base + i*4096 + 64*(i mod 8)
which is 256 lines spread over 8 SETS of an
8-way cache -- 32 lines per set, four times
the ways. the measurement was a CONFLICT MISS,
measured one page at a time, and the pages had
nothing to do with it.
the same bug in its other form put one line per
4096-byte page with off = 0, and since one line
per 4096 bytes IS the aliasing stride, every
page's line landed in L1 SET 0. that produced a
"TLB cliff at 32 pages" which was also a set
conflict, and which vanished when the offset
spread the lines over all 64 sets.
Two findings had to be withdrawn and the real cliff turned out to be at 64 pages — which is a genuine translation limit and is measured properly, with a huge-page control, in the next concept. What makes this retraction worth a section rather than a line is that it was invisible from the output: the numbers were stable, the effect was large, the model was plausible, and the words “4096-byte stride” were in the caption. The only thing that ever catches this class of error is a control layout — the second column of the table above — because the control differs in exactly the thing the explanation claims and nothing else.
And there is an arithmetic tell that would have caught it immediately, which the artifact prints for exactly that reason. A 4096-byte stride in a 64-set cache with 64-byte lines is the aliasing stride, and that identity is published by the level itself:
=> the L1d aliasing stride is sets x line = 64 x 64 = 4096 bytes
and one L1d set holds ways x line = 512 bytes
Any experiment whose page size coincides with the cache's aliasing stride cannot separate the two, and the fix is arithmetic rather than experimental: use an offset that is not a multiple of the line and not a multiple of the stride. That is what off = 64*(i mod 64) is for in the next concept: it puts line i in set i mod 64 whatever the stride, so two arms comparing page counts have the same set distribution by construction and the only difference left is the pages.
$ cd courses/mem/assets/samples $ ./membench 2>&1 | sed -n '/4. ASSOC/,/5. ADDRESS/p' $ python3 crosscheck.py 2>&1 | sed -n '/^ --- group D:/,/^ --- group E:/p'
Then reproduce it on your own machine, which is the exercise that makes associativity a fact rather than a word:
1. Read the geometry and compute the stride:
for i in 0 1 2 3; do
d=/sys/devices/system/cpu/cpu0/cache/index$i
cat $d/level $d/type $d/size \
$d/ways_of_associativity $d/number_of_sets \
$d/coherency_line_size
done
(Expect sets*line to be a power of two, usually
4096 on x86-64 and often 1024 or 2048 on
AArch64 -- which means the SAME C code can be
free of conflicts on one machine and full of
them on the other. This is the first portability
fact in the course.)
2. Build the two layouts and reproduce the step.
A chase over n lines at stride `sets*line`, and
the same n at stride `sets*line + line`.
(Expect a step at ways+1 and a flat control.
If your step is at a different count, re-read
the ways value: it is the number that decides.)
3. Break the control on purpose. Use a stride of
`sets*line` for BOTH arms and confirm they
agree -- then wonder how many real benchmarks
do exactly that by accident.
(This is the retraction above, in five minutes,
and it is the most valuable exercise here.)
4. Do it for the L2 and the L3 as well, and watch
the stride scale with the set count. The L2's
aliasing stride on this machine is 65536 bytes.
(Expect the effect to be SMALLER at the outer
levels, because a larger level has more ways
and because it is shared. The size of the
effect is a property of the level's geometry,
not of the level's position.)
5. Finally, look for it in a program you own:
a matrix transpose, a bucket array, a struct
of arrays. Compute the stride between two
elements that land in the same set, and see
whether your inner loop ever hits it.
Exercise 1 is the one that changes how a reader writes code, because the aliasing stride is a number of bytes and most structs and matrices are designed in numbers of elements. A row of a 1024-wide matrix of 4-byte floats is exactly 4096 bytes — which is this machine's L1d aliasing stride, so a column walk of that matrix hits one L1 set 1024 times in a row. That is not a hypothetical: it is the most common accidental conflict miss in numerical code, and it is invisible in a profiler on a machine with a PMU because a conflict miss and a capacity miss are the same event there.
Exercise 3 is the one that keeps the reader honest, because it is a demonstration that a plausible experiment can be guaranteed to find an effect it is not measuring. Two arms whose addresses collide produce a large, stable, reproducible difference for a reason the experiment's own caption denies. Every retraction in this course is a variation on that theme, and the defence is always the same: make the two arms differ in exactly one thing and prove that they do — which, for addresses, means counting them rather than asserting them.
The direct parent is the previous concept, and the relationship is the one the two concepts' own caveats set up. That concept's curve used a random permutation over each footprint, which spreads the accesses over all sets — so it measured capacity and nothing else, and its author said so. This concept removes the spreading and finds the other half of “cache”. Put together, the two tables are a description of a level: how many lines it holds, and how it decides which of them to keep. The first is in /sys and the second is not.
The connection to the previous course's front-end concept is a shared structure rather than a shared number. That concept measured that an instruction loop's performance depends on where its bytes sit within 64-byte blocks, and declined to name a mechanism because three were plausible and none was measurable. This concept is the same claim in the data side, and it can name its mechanism, because a set index is arithmetic that /sys publishes while an instruction-cache fetch policy is not published anywhere. Same class of effect, different epistemic status: one is derivable, the other is measurable only.
Two connections outward, and both are places where a number in this table stops being abstract. The object course measured that alignment is a promise in a header, and this table quantifies what breaking it costs when the promise is about a stride rather than a start. And the DWARF course's address-to-line mapping is the reverse direction of the same arithmetic: a compiler that emits a line table is recording where code ended up in the address space, and this course is what the machine does with those addresses once code begins to execute.
And the connection forward is a number that this concept's arithmetic makes possible to isolate. A page is 4096 bytes on this machine, which is exactly the L1d aliasing stride, which is why the first attempt to measure translation measured a set conflict instead. The next concept compares two layouts whose sets are identical by construction and whose page counts differ, and what is left over when the sets cancel is the cost of translating an address at all — a cliff at 64 pages, and 512 times the reach for the same walk when the page is 2 MiB.