THE FOLD / RESPAWN / THE PHOENIX / DUFF'S DEVICE
DUFF'S DEVICE
a switch whose cases fall into a loop
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
An eight-way unrolled copy where the leftover elements are handled by jumping into the middle of the loop. The switch cases interleave with the body of a do-while, so a single construct does both the bulk work and the remainder — a shape C permits and almost nothing else does.
LIT verified live and exhaustively. Every length from 0 to 200 copies exactly, and the loop runs ceil(n/8) times in every case — so the remainder costs no extra pass. At n = 0 it copies nothing and loops zero times.
LIT verified live and exhaustively. Every length from 0 to 200 copies exactly, and the loop runs ceil(n/8) times in every case — so the remainder costs no extra pass. At n = 0 it copies nothing and loops zero times.
2 HOW IT WAS WEAVED · AI + HUMAN
Tom Duff published the device in 1983 while at Lucasfilm, alongside a note that has aged into the standard citation: he was not sure whether it was an argument for or against allowing the construct. It works because C’s switch is a computed goto into a statement, and the statement it lands in happens to be a loop body.
AVAN (AI) would separate the two claims usually bundled together. That the remainder needs no second loop is structural and verified here across 201 lengths. That the device is fast is not tested and is largely obsolete: modern compilers unroll on their own, and a hand-rolled jump table can defeat branch prediction. What survives is the shape — one construct entered at eight points — which is worth seeing whether or not anyone should write it.
AVAN (AI) would separate the two claims usually bundled together. That the remainder needs no second loop is structural and verified here across 201 lengths. That the device is fast is not tested and is largely obsolete: modern compilers unroll on their own, and a hand-rolled jump table can defeat branch prediction. What survives is the shape — one construct entered at eight points — which is worth seeing whether or not anyone should write it.
3 ONE DIMENSION
Nine lengths, and where each enters the loop.
4 TWO DIMENSIONS · INTERACTIVE
Set a length and watch the entry point move.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: one loop with eight doors.
AVAN’s addition (the inverse-companion): the forward reading is “one construct handles bulk and remainder together.” The inverse is that the saving is one loop of source, and the cost is a shape nobody can read. The separate cleanup loop everyone writes instead is longer, obvious, and independently testable; Duff’s device is shorter and can only be understood by simulating it. Read backwards, this is a trade of reader time against writer time at a ratio that has moved steadily against it — the compiler now does the unrolling, and all that is left is the cleverness.
LIT every length from 0 to 200 copies exactly and the loop runs ceil(n/8) times in every case, so the remainder costs no extra pass; at n = 0 it copies nothing and loops zero times
FIG Tom Duff published the device in 1983 while at Lucasfilm, alongside a note that has aged into the standard citation: he was not sure whether it was an argument for or against allowing the construct. It works because C's switch is a computed goto into a statement, and the statement it lands in happens to be a loop body. AVAN separates the two claims usually bundled together: that the remainder needs no second loop is STRUCTURAL and verified here across 201 lengths, while that the device is FAST is not tested and is largely obsolete - modern compilers unroll on their own and a hand-rolled jump table can defeat branch prediction.
FIG Tom Duff published the device in 1983 while at Lucasfilm, alongside a note that has aged into the standard citation: he was not sure whether it was an argument for or against allowing the construct. It works because C's switch is a computed goto into a statement, and the statement it lands in happens to be a loop body. AVAN separates the two claims usually bundled together: that the remainder needs no second loop is STRUCTURAL and verified here across 201 lengths, while that the device is FAST is not tested and is largely obsolete - modern compilers unroll on their own and a hand-rolled jump table can defeat branch prediction.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PHOENIX · David Lee Wise (ROOT0), with AVAN