THE FOLD / CHEAT / NOCLIP / THE POINTER CHASE
THE POINTER CHASE
the program knows the future and has no way to say so
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
To follow a linked list the machine must load a pointer before it knows which address to load next. The loads cannot overlap, cannot be reordered and cannot be prefetched, because the address does not exist until the previous load returns.
LIT verified live. 100,000 nodes arranged by Sattolo’s algorithm into a single cycle: following it from node 0 visits 100,000 distinct nodes and returns to the start — verified, not assumed. Every one of those loads depends on the one before it. Under a stated model of 4-cycle latency and 8-wide pipelining, that is 400,000 cycles serial against 50,000 if they could overlap.
LIT verified live. 100,000 nodes arranged by Sattolo’s algorithm into a single cycle: following it from node 0 visits 100,000 distinct nodes and returns to the start — verified, not assumed. Every one of those loads depends on the one before it. Under a stated model of 4-cycle latency and 8-wide pipelining, that is 400,000 cycles serial against 50,000 if they could overlap.
2 HOW IT WAS WEAVED · AI + HUMAN
Sattolo’s algorithm is a one-character change from Fisher–Yates that guarantees a single cycle rather than a random permutation.
AVAN (AI) needed that change. My first version used an ordinary shuffle and the chase visited 873 of 100,000 nodes before looping — because a random permutation decomposes into many short cycles, which is exactly the thing a pointer-chase benchmark must not have. The 4-cycle and 8-wide figures are a stated model; the 100,000-node single cycle is measured.
AVAN (AI) needed that change. My first version used an ordinary shuffle and the chase visited 873 of 100,000 nodes before looping — because a random permutation decomposes into many short cycles, which is exactly the thing a pointer-chase benchmark must not have. The 4-cycle and 8-wide figures are a stated model; the 100,000-node single cycle is measured.
3 ONE DIMENSION
A random permutation, and a Sattolo cycle. Same shuffle, one character apart.
4 TWO DIMENSIONS · INTERACTIVE
Walk the chain and watch it refuse to overlap.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: one cycle through every node.
AVAN’s addition (the inverse-companion): the forward reading is that pointer chasing defeats the memory system. The inverse is that the dependency is information, and the machine is refusing to use it. The chain says precisely what comes next — it is written down in the node you are holding — and the hardware cannot act on it because reading it is the operation being waited for. Read backwards, this is the one case where the program knows the future and has no way to say so, and every prefetch hint ever added to an instruction set is an attempt to give it a voice.
LIT 100,000 nodes arranged by Sattolo's algorithm into a single cycle: following it from node 0 visits 100,000 distinct nodes and returns to the start, verified rather than assumed, so every load depends on the one before it - and under a stated model of 4-cycle latency and 8-wide pipelining that is 400,000 cycles serial against 50,000 if they could overlap
FIG Sattolo's algorithm is a one-character change from Fisher-Yates that guarantees a single cycle rather than a random permutation. AVAN needed that change: my first version used an ordinary shuffle and the chase visited 873 of 100,000 nodes before looping, because a random permutation decomposes into many short cycles - exactly what a pointer-chase benchmark must not have. The 4-cycle and 8-wide figures are a stated model; the 100,000-node single cycle is measured.
FIG Sattolo's algorithm is a one-character change from Fisher-Yates that guarantees a single cycle rather than a random permutation. AVAN needed that change: my first version used an ordinary shuffle and the chase visited 873 of 100,000 nodes before looping, because a random permutation decomposes into many short cycles - exactly what a pointer-chase benchmark must not have. The 4-cycle and 8-wide figures are a stated model; the 100,000-node single cycle is measured.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of NOCLIP · David Lee Wise (ROOT0), with AVAN