Branch reduction by two-level conditionals
Posted: Tue Dec 27, 2016 5:52 pm
While PB makes it super easy to use jump tablesā„ I was also curious about the effect of using two levels of IF/SELECT/etc conditional statements to hopefully reduce the amount of tests required to reach each condition handler once. Im sure this is something Ada Lovelace figured out (nothing new about divide and conquer!) but i needed to feed my curious mind.
For example, instead of this (where it takes 1 test for best-case, 6 tests for worst-case, and 21 tests to reach each handler once):I was curious about the effects of setups like this (which takes 18 tests to reach each handler once - not a great demo of gains but im keeping it simple! See below for better gains examples):
Select statements cant be used for this test though because they dont allow for a counter before each test, so I simply reconstructed them as If statements, as the difference is only semantic.
Anyway I quickly concluded that to calculate the optimal number of Level1 tests simply take the square root of the number of total tests, rounded down. (wow amazing! lol) That is, there must be equal-or-more tests in each Level2 set than the number of Level1 tests. Gains are typically 45-50% less tests required.
From that I then wrote this little program to output a skeleton of the optimised structure:Sample output:
For example, instead of this (where it takes 1 test for best-case, 6 tests for worst-case, and 21 tests to reach each handler once):
Code: Select all
Select x
Case 1:
Case 2:
Case 3:
Case 4:
Case 5:
Case 6:
EndSelectCode: Select all
Select x
Case 1 To 3: ;Level1
Select x
Case 1: ;Level2
Case 2: ;Level2
Case 3: ;Level2
EndSelect
Default: ;Level1
Select x
Case 4: ;Level2
Case 5: ;Level2
Case 6: ;Level2
EndSelect
EndSelectAnyway I quickly concluded that to calculate the optimal number of Level1 tests simply take the square root of the number of total tests, rounded down. (wow amazing! lol) That is, there must be equal-or-more tests in each Level2 set than the number of Level1 tests. Gains are typically 45-50% less tests required.
From that I then wrote this little program to output a skeleton of the optimised structure:
Code: Select all
Procedure CalcLevel1(varName.s, nStatements)
If nStatements < 4
L1 = 0
Else
L1 = Round(Sqr(nStatements),#PB_Round_Down)
EndIf
Debug ";Use " + Str(L1) + " x Level1 tests for " + Str(nStatements) + " tests"
If L1 <= 0: ProcedureReturn 0: EndIf
nStatements-1
eachset.f = Round(nStatements / L1,#PB_Round_Up)
Debug "Select " + varName
For i = 1 To L1
last = (i*eachset)-1
If i = L1: last = nStatements: EndIf
If i = L1
Debug " Default: ;" + Str((i-1)*eachset) + " to " + Str(last)
Else
Debug " Case " + Str((i-1)*eachset) + " to " + Str(last) + ":"
EndIf
Debug " Select " + varName
If i = L1: last = nStatements: EndIf
For i2 = (i-1)*eachset To last
Debug " Case " + Str(i2) + ":"
If i2 = nStatements: Break: EndIf
Next i2
Debug " EndSelect"
Next i
Debug "EndSelect"
EndProcedure
;Example use:
nStatements = 20
CalcLevel1("nvar", nStatements)Code: Select all
;Use 4 x Level1 tests for 20 tests
Select nvar
Case 0 to 4:
Select nvar
Case 0:
Case 1:
Case 2:
Case 3:
Case 4:
EndSelect
Case 5 to 9:
Select nvar
Case 5:
Case 6:
Case 7:
Case 8:
Case 9:
EndSelect
Case 10 to 14:
Select nvar
Case 10:
Case 11:
Case 12:
Case 13:
Case 14:
EndSelect
Default: ;15 to 19
Select nvar
Case 15:
Case 16:
Case 17:
Case 18:
Case 19:
EndSelect
EndSelect