THE FOLD / CHEAT / THE SPEEDRUN / THE PREFETCHER
THE PREFETCHER
the whole performance cliff is a missing sentence
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The hardware watches your address stream and fetches ahead of you. It is not clairvoyant — it is a pattern matcher, and it only wins when there is a pattern.
LIT verified live. 200,000 accesses. Walking forward, the next address is the previous plus one 199,999 times out of 200,000 — 100.00% predictable, with a single miss at the very first access because there is nothing before it. The identical count of accesses drawn at random is predictable 0 times — 0.00%. Same data, same working set, same instruction count; only the order changed.
LIT verified live. 200,000 accesses. Walking forward, the next address is the previous plus one 199,999 times out of 200,000 — 100.00% predictable, with a single miss at the very first access because there is nothing before it. The identical count of accesses drawn at random is predictable 0 times — 0.00%. Same data, same working set, same instruction count; only the order changed.
2 HOW IT WAS WEAVED · AI + HUMAN
Stride prefetchers have been in commodity CPUs since the 1990s and are the reason array code outruns pointer code by margins that look like measurement error.
AVAN (AI) counted predictability rather than modelling a cache, because predictability is the property the prefetcher actually depends on and it can be counted exactly. The single miss in the sequential run is worth keeping: it is the cold start, and reporting 199,999 rather than rounding to “all of them” is the difference between a count and a slogan.
AVAN (AI) counted predictability rather than modelling a cache, because predictability is the property the prefetcher actually depends on and it can be counted exactly. The single miss in the sequential run is worth keeping: it is the cold start, and reporting 199,999 rather than rounding to “all of them” is the difference between a count and a slogan.
3 ONE DIMENSION
Two address streams. One has a next; one does not.
4 TWO DIMENSIONS · INTERACTIVE
Shuffle the order and watch predictability collapse.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a machine guessing where you are going.
AVAN’s addition (the inverse-companion): the forward reading is that the prefetcher rewards sequential access. The inverse is that it punishes you for information it does not have. Your random walk is not disordered — you know exactly where you are going next; the hardware simply cannot see it, because the only channel between your intent and the memory system is the address you already issued. Read backwards, prefetching is a guess made necessary by an interface with no way to say “next I will need this”, and the whole performance cliff is a missing sentence.
LIT over 200,000 accesses, walking forward the next address is the previous plus one 199,999 times - 100.00% predictable, with a single miss at the very first access because nothing precedes it - while the identical count drawn at random is predictable 0 times, 0.00%, on the same data, same working set and same instruction count
FIG Stride prefetchers have been in commodity CPUs since the 1990s and are why array code outruns pointer code by margins that look like measurement error. AVAN counted predictability rather than modelling a cache, because predictability is the property the prefetcher depends on and it can be counted exactly. The single miss in the sequential run is worth keeping: it is the cold start, and reporting 199,999 rather than rounding to all of them is the difference between a count and a slogan.
FIG Stride prefetchers have been in commodity CPUs since the 1990s and are why array code outruns pointer code by margins that look like measurement error. AVAN counted predictability rather than modelling a cache, because predictability is the property the prefetcher depends on and it can be counted exactly. The single miss in the sequential run is worth keeping: it is the cold start, and reporting 199,999 rather than rounding to all of them is the difference between a count and a slogan.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN