THE FOLD / BOSS / THE GAUNTLET / THE STRENGTH REDUCTION
THE STRENGTH REDUCTION
a constant that was a number is now a decision
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A multiply by a constant can sometimes be replaced by shifts and adds. Sometimes. Whether it is worth doing depends entirely on the bit pattern of that constant, and most constants are not worth it.
LIT verified live. With a multiply costing 5 and a shift or add costing 1, 9 constants tested: only 4 reduce to something cheaper and 5 keep the multiply, saving 14 cost units in total. 10 has two set bits and costs 3. 7 has three and costs exactly 5 — a wash. 255 has eight, and the multiply stays.
LIT verified live. With a multiply costing 5 and a shift or add costing 1, 9 constants tested: only 4 reduce to something cheaper and 5 keep the multiply, saving 14 cost units in total. 10 has two set bits and costs 3. 7 has three and costs exactly 5 — a wash. 255 has eight, and the multiply stays.
2 HOW IT WAS WEAVED · AI + HUMAN
Strength reduction is the oldest trick in the peephole toolkit and the one most often over-remembered as always-a-win.
AVAN (AI) dropped 1 from the test set after running it. x * 1 needs no instruction at all, and scoring it as a one-cycle shift would have counted a free operation as a saving and inflated the win rate. The honest result is that fewer than half the constants tested are worth reducing.
AVAN (AI) dropped 1 from the test set after running it. x * 1 needs no instruction at all, and scoring it as a one-cycle shift would have counted a free operation as a saving and inflated the win rate. The honest result is that fewer than half the constants tested are worth reducing.
3 ONE DIMENSION
Nine constants, and which ones are worth it.
4 TWO DIMENSIONS · INTERACTIVE
Pick a constant and see its bits decide.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a number’s bits deciding its cost.
AVAN’s addition (the inverse-companion): the forward reading is that strength reduction makes multiplication cheaper. The inverse is that it makes the cost of your code depend on the value of a literal. Change a 10 to a 7 in the source and the instruction count changes, though nothing about the program’s meaning did. Read backwards, the optimisation smuggles the machine’s arithmetic up into the source text, and a constant that used to be a number is now also a decision about the shape of the emitted code.
LIT with a multiply costing 5 and a shift or add costing 1, of 9 constants tested only 4 reduce to something cheaper while 5 keep the multiply, saving 14 cost units in total - 10 has two set bits and costs 3, 7 has three and costs exactly 5 which is a wash, and 255 has eight so the multiply stays
FIG Strength reduction is the oldest trick in the peephole toolkit and the one most often over-remembered as always-a-win. AVAN dropped 1 from the test set after running it: x * 1 needs no instruction at all, and scoring it as a one-cycle shift would have counted a free operation as a saving and inflated the win rate. The honest result is that fewer than half the constants tested are worth reducing.
FIG Strength reduction is the oldest trick in the peephole toolkit and the one most often over-remembered as always-a-win. AVAN dropped 1 from the test set after running it: x * 1 needs no instruction at all, and scoring it as a one-cycle shift would have counted a free operation as a saving and inflated the win rate. The honest result is that fewer than half the constants tested are worth reducing.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GAUNTLET · David Lee Wise (ROOT0), with AVAN