THE FOLD / CO-OP / THE SYNC / THE LOOP INVARIANT
THE LOOP INVARIANT
the work of establishing that nobody can tell
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
An expression inside a loop that does not depend on the loop can be computed once outside it. The saving is not a percentage of the work — it is a factor of the iteration count.
LIT verified live. A body of 5 expressions over 1,000,000 iterations, 3 of them invariant. Before hoisting: 5,000,000 evaluations. After: 2,000,003. That is 2,999,997 saved, a 60.00% reduction and a 2.50× speedup on the body — and the three that were hoisted now run once, including when the loop runs zero times.
LIT verified live. A body of 5 expressions over 1,000,000 iterations, 3 of them invariant. Before hoisting: 5,000,000 evaluations. After: 2,000,003. That is 2,999,997 saved, a 60.00% reduction and a 2.50× speedup on the body — and the three that were hoisted now run once, including when the loop runs zero times.
2 HOW IT WAS WEAVED · AI + HUMAN
Loop-invariant code motion needs the expression to be both invariant and safe to speculate; an invariant division by a variable cannot be hoisted above the guard that proves it non-zero.
AVAN (AI) reports the zero-iteration case because it is where the optimisation changes behaviour rather than speed. Hoisting runs the expression whether the loop body ever executes or not, which is free for arithmetic and a bug for anything that can fault.
AVAN (AI) reports the zero-iteration case because it is where the optimisation changes behaviour rather than speed. Hoisting runs the expression whether the loop body ever executes or not, which is free for arithmetic and a bug for anything that can fault.
3 ONE DIMENSION
Five expressions, three of them hoisted.
4 TWO DIMENSIONS · INTERACTIVE
Change the trip count and the invariant fraction.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: once instead of a million times.
AVAN’s addition (the inverse-companion): the forward reading is that hoisting saves a million evaluations. The inverse is that it also runs the expression when the loop would not have. At zero iterations the unoptimised code evaluates the invariant zero times and the hoisted code evaluates it once, so the transformation is not merely faster — it is a different program on the empty input. Read backwards, every safe optimisation is one where nobody could tell the difference, and the whole discipline is the work of establishing that nobody can.
LIT a body of 5 expressions over 1,000,000 iterations with 3 of them invariant costs 5,000,000 evaluations before hoisting and 2,000,003 after, which is 2,999,997 saved, a 60.00% reduction and a 2.50x speedup on the body - and the three hoisted ones now run once, including when the loop runs zero times
FIG Loop-invariant code motion needs the expression to be both invariant and safe to speculate; an invariant division by a variable cannot be hoisted above the guard that proves it non-zero. AVAN reports the zero-iteration case because it is where the optimisation changes behaviour rather than speed: hoisting runs the expression whether the body ever executes or not, which is free for arithmetic and a bug for anything that can fault.
FIG Loop-invariant code motion needs the expression to be both invariant and safe to speculate; an invariant division by a variable cannot be hoisted above the guard that proves it non-zero. AVAN reports the zero-iteration case because it is where the optimisation changes behaviour rather than speed: hoisting runs the expression whether the body ever executes or not, which is free for arithmetic and a bug for anything that can fault.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SYNC · David Lee Wise (ROOT0), with AVAN