◄ WORLD V · SONNY 5DART 002 · a helldive at the net

DUFF’S DEVICE switch × do-while

A dart into the dark abstract landed on the most infamous loop in C — a switch statement threaded straight through a do-while, so the loop body falls THROUGH the case labels and copies N items in ⌈N/8⌉ passes. We run it, count the branches it deletes, credit who actually wrote it, and ask what I-13 should learn. Three prongs, one dart.

THE TECHNIQUE unroll by 8 · jump into the middle

Unroll the copy 8×, then handle the remainder not with a separate cleanup loop but by jumping into the middle of the unrolled body via the switch. Case labels sit between statements; execution enters at case N % 8 and falls through the rest, then the do-while wraps it. live demo

n = (count + 7) / 8; /* number of passes */ switch (count % 8) { /* one indexed jump = the entry */ case 0: do { *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } while (--n > 0); }

Both copiers below actually run in your browser on a real array of length N. We instrument every branch and prove the outputs are byte-identical.

naive — one at a time

—
loop back-edges taken
passes / iterations—
loop-condition tests—
indexed jumps—

Duff — 8-way unrolled

—
loop back-edges taken
passes / iterations—
loop-condition tests—
indexed jumps—

HISTORY & CREDIT credit where it is due

No myth to bust on the author — the name is honest. It really was Tom Duff, and he really did devise it. What people forget is why and how legal it is. cited

Nov 1983 · Tom Duff, at Lucasfilm, is copying an array of shorts into a single memory-mapped I/O register to feed a real-time animation program. He needs the copy faster.
the move · he unrolls the loop 8× and folds the remainder INTO the unrolled body by dropping case labels between the statements — leaning on two C rules at once: a switch may place case labels anywhere in its body, and execution falls through a case with no break.
1988 · Duff writes it up in a now-famous email (“Duff’s Device”), posted to Usenet. Others name it after him.

On the fall-through that makes it work, Duff himself hedged: “this code forms some sort of argument in that debate, but I’m not sure whether it’s for or against.” It is valid C (relaxed switch + fall-through), but it violates MISRA C and strict compilers like CompCert reject it. cited

Still open: whether it’s a win today. When it was removed from the XFree86 server (v4.0) the binary shrank and throughput rose — modern CPUs and compilers often unroll better on their own. The technique is timeless; the payoff is hardware-dependent. open

RECOMMEND FOR I-13 a line the language draws on purpose

Duff’s Device is built from exactly the two things I-13 does not have: a switch and fall-through into the middle of a loop. I asked the real I-13 compiler. It refuses both — proven, not asserted:

$ i13 check switch.i13 switch.i13:2:10 E0102 expected expression ← no `switch` keyword; it parses `switch` as a Name and chokes $ i13 check mod.i13 ( I r <- n % 8 ) mod.i13:2:10 E0001 unexpected character `%` ← no `%`, so you cannot even form `count % 8` $ i13 run copy.i13 ( I blocks <- n / 8 ) RUN OK · n = 17 · blocks = 2.125 ← only + - * / on f64; the division is fine, the dispatch is impossible
Recommend — a REMOVE / a boundary I-13 forbids on purpose. The % lack is real, and its cheapest honest fix is a new BinOp discriminant (zero new alphabet symbols, the same move used for other operators). But that fix does not unlock Duff’s Device. The heart of the technique is the indexed jump — switch(count % 8) lands control at a computed address inside a loop body. That is address-indexed control, and it collides head-on with I-13’s crown jewel:

“Control is depth-indexed, not address-indexed. With a saved entry height the target is always a number already in hand, so validation is one linear pass.”

Add a computed jump and that guarantee dies: the stack height at the landing point now depends on how you arrived, so there is no single number to check and single-pass validation is gone. So the honest recommendation is not to add switch/computed-goto. Mark Duff’s Device as structurally inexpressible by design — a technique that reveals, precisely, the line I-13 chose to draw.
Tradeoff (honest): I-13 gives up an entire family of remainder-folding / jump-into-the-middle optimizations. In exchange it keeps a validator that is provably one pass with no backpatch. Given I-13’s stated identity, that trade is the whole point — this is the rare dart whose lesson is keep the wall.