THE FOLD / GRIND / THE GRINDSTONE / THE STRIDED ACCESS
THE STRIDED ACCESS
the premium on an insurance policy everyone else claims on
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Memory arrives in cache lines, not in variables. Ask for four bytes and sixty-four turn up. Whether that is generous or wasteful depends entirely on how far apart your next four bytes are.
LIT verified live. Four-byte elements on 64-byte lines. Stride 1 puts 16 elements on every line and uses 100.0% of what arrives. Stride 16 puts 1 element per line and uses 6.3% — 93.7% of every line fetched is thrown away. Past stride 16 nothing improves and nothing worsens: it is already one element per line, and the floor is 6.3%.
LIT verified live. Four-byte elements on 64-byte lines. Stride 1 puts 16 elements on every line and uses 100.0% of what arrives. Stride 16 puts 1 element per line and uses 6.3% — 93.7% of every line fetched is thrown away. Past stride 16 nothing improves and nothing worsens: it is already one element per line, and the floor is 6.3%.
2 HOW IT WAS WEAVED · AI + HUMAN
This is why array-of-structs and struct-of-arrays are different programs with the same data, and why column stores exist.
AVAN (AI) swept every stride rather than contrasting two, because the shape matters more than the endpoints: efficiency halves with each doubling until it hits one element per line, and then it stops. The plateau is the useful part — beyond stride 16 the layout cannot get worse, which means the damage is done long before the access pattern looks dramatic.
AVAN (AI) swept every stride rather than contrasting two, because the shape matters more than the endpoints: efficiency halves with each doubling until it hits one element per line, and then it stops. The plateau is the useful part — beyond stride 16 the layout cannot get worse, which means the damage is done long before the access pattern looks dramatic.
3 ONE DIMENSION
Useful bytes per 64-byte line, by stride.
4 TWO DIMENSIONS · INTERACTIVE
Walk the stride and watch the line empty out.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a line arriving mostly unwanted.
AVAN’s addition (the inverse-companion): the forward reading is that large strides waste bandwidth. The inverse is that the line was a guess about your intentions, and it is usually right. Fetching sixty-four bytes for a four-byte request is a bet on spatial locality that pays off overwhelmingly often — which is why nobody offers you a four-byte fetch. Read backwards, stride-16 access is not being punished for being slow; it is being charged the premium on an insurance policy that everyone else is claiming on.
LIT with four-byte elements on 64-byte lines, stride 1 puts 16 elements on every line and uses 100.0% of what arrives while stride 16 puts 1 element per line and uses 6.3% - throwing away 93.7% of every line fetched - and past stride 16 nothing changes at all, because it is already one element per line and 6.3% is the floor
FIG This is why array-of-structs and struct-of-arrays are different programs with the same data, and why column stores exist. AVAN swept every stride rather than contrasting two, because the shape matters more than the endpoints: efficiency halves with each doubling until it hits one element per line, then stops. The plateau is the useful part - beyond stride 16 the layout cannot get worse, which means the damage is done long before the access pattern looks dramatic.
FIG This is why array-of-structs and struct-of-arrays are different programs with the same data, and why column stores exist. AVAN swept every stride rather than contrasting two, because the shape matters more than the endpoints: efficiency halves with each doubling until it hits one element per line, then stops. The plateau is the useful part - beyond stride 16 the layout cannot get worse, which means the damage is done long before the access pattern looks dramatic.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN