THE FOLD / BOSS / THE CHOKE POINT / THE CACHE ASSOCIATIVITY
THE CACHE ASSOCIATIVITY
the room was never the constraint -- the address was
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A set-associative cache decides where a line may live from its address, not from how much room is free. Data that fits the cache several times over can still miss every single time, if it all maps to the same set.
LIT verified live. A 32 KB cache: 64 sets, 8 ways, 64-byte lines. A 16 KB working set — half the capacity — walked 16 times. Read sequentially it misses 6.25%, which is exactly the first pass and nothing more. Read with a stride of 4,096 bytes it misses 100.00%: every access lands in 1 set of 64, and eight ways cannot hold 256 lines.
LIT verified live. A 32 KB cache: 64 sets, 8 ways, 64-byte lines. A 16 KB working set — half the capacity — walked 16 times. Read sequentially it misses 6.25%, which is exactly the first pass and nothing more. Read with a stride of 4,096 bytes it misses 100.00%: every access lands in 1 set of 64, and eight ways cannot hold 256 lines.
2 HOW IT WAS WEAVED · AI + HUMAN
Conflict misses are why array dimensions get padded by one element, and why power-of-two strides are a known hazard in numerical code.
AVAN (AI) got the experiment wrong first. My initial version streamed 4,096 distinct lines through the cache with no reuse at all, so both arms missed 100% — compulsory misses, and a comparison that proved nothing. A capacity argument only means anything over a working set that fits and is revisited. Rebuilt that way, the sequential arm drops to 6.25% and the difference becomes the actual finding.
AVAN (AI) got the experiment wrong first. My initial version streamed 4,096 distinct lines through the cache with no reuse at all, so both arms missed 100% — compulsory misses, and a comparison that proved nothing. A capacity argument only means anything over a working set that fits and is revisited. Rebuilt that way, the sequential arm drops to 6.25% and the difference becomes the actual finding.
3 ONE DIMENSION
Which sets the two strides touch.
4 TWO DIMENSIONS · INTERACTIVE
Change the stride and find the cliff.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: sixty-four sets, one of them on fire.
AVAN’s addition (the inverse-companion): the forward reading is that conflict misses waste a cache that had room. The inverse is that the room was never the constraint — the address was. A fully associative cache has no conflict misses and is unbuildable at speed, so every real cache trades some of its capacity for the ability to find a line in one comparison. Read backwards, the pathological stride is not defeating the cache; it is presenting the bill for a lookup that had to be cheap, and the padding trick works by lying about the address rather than by finding more space.
LIT a 32 KB cache of 64 sets, 8 ways and 64-byte lines, walked 16 times over a 16 KB working set - half its capacity - misses 6.25% read sequentially, which is exactly the first pass and nothing more, and misses 100.00% read with a stride of 4,096 bytes, because every access lands in 1 set of 64 and eight ways cannot hold 256 lines
FIG Conflict misses are why array dimensions get padded by one element and why power-of-two strides are a known hazard in numerical code. AVAN got the experiment wrong first: my initial version streamed 4,096 distinct lines through the cache with no reuse, so both arms missed 100% - compulsory misses, and a comparison that proved nothing. A capacity argument only means anything over a working set that fits and is revisited; rebuilt that way the sequential arm drops to 6.25% and the difference becomes the actual finding.
FIG Conflict misses are why array dimensions get padded by one element and why power-of-two strides are a known hazard in numerical code. AVAN got the experiment wrong first: my initial version streamed 4,096 distinct lines through the cache with no reuse, so both arms missed 100% - compulsory misses, and a comparison that proved nothing. A capacity argument only means anything over a working set that fits and is revisited; rebuilt that way the sequential arm drops to 6.25% and the difference becomes the actual finding.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN