Branch reduction by two-level conditionals

Share your advanced PureBasic knowledge/code with the community.
Post Reply
User avatar
Keya
Addict
Addict
Posts: 1890
Joined: Thu Jun 04, 2015 7:10 am

Branch reduction by two-level conditionals

Post by Keya »

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):

Code: Select all

Select x
 Case 1:
 Case 2:
 Case 3:
 Case 4:
 Case 5:
 Case 6:
EndSelect
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):

Code: 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
EndSelect
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:

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)
Sample output:

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
Last edited by Keya on Tue Dec 27, 2016 7:10 pm, edited 12 times in total.
Top
User avatar
Keya
Addict
Addict
Posts: 1890
Joined: Thu Jun 04, 2015 7:10 am

Re: Branch reduction by two-level conditionals

Post by Keya »

Here's some of the raw tests i did to reach the square root conclusion:

6 tests:

Code: Select all

Procedure DoTest(x)  ;= 21
  Repeat
    Ifs+1
    If x = 0: Break: EndIf
    Ifs+1
    If x = 1: Break: EndIf
    Ifs+1
    If x = 2: Break: EndIf
    Ifs+1
    If x = 3: Break: EndIf
    Ifs+1
    If x = 4: Break: EndIf
    Ifs+1
    If x = 5: Break: EndIf
  ForEver
EndProcedure

Procedure DoTest(x)  ;= 18
  Repeat    
    Ifs+1    
    If x <= 2    
      Ifs+1
      If x = 0: Break: EndIf
      Ifs+1
      If x = 1: Break: EndIf
      Ifs+1
      If x = 2: Break: EndIf      
    Else      
      Ifs+1
      If x = 3: Break: EndIf
      Ifs+1
      If x = 4: Break: EndIf
      Ifs+1
      If x = 5: Break: EndIf
    EndIf    
  ForEver
EndProcedure

Procedure DoTest(x)  ;= 19
  Repeat    
    Ifs+1    
    If x <= 1    
      Ifs+1
      If x = 0: Break: EndIf
      Ifs+1
      If x = 1: Break: EndIf
    EndIf
    Ifs+1    
    If x <= 3
      Ifs+1
      If x = 2: Break: EndIf      
      Ifs+1
      If x = 3: Break: EndIf    
    Else
      Ifs+1
      If x = 4: Break: EndIf
      Ifs+1
      If x = 5: Break: EndIf
    EndIf    
  ForEver
EndProcedure

For i = 0 To 5
  DoTest(i)
Next i
20 tests (gains become a bit more apparent, dropping from 210 to 105 tests to reach each handler once):

Code: Select all

Procedure DoTest(x)  ;= 210
  Repeat
    Ifs+1
    If x = 0: Break: EndIf
    Ifs+1
    If x = 1: Break: EndIf
    Ifs+1
    If x = 2: Break: EndIf
    Ifs+1
    If x = 3: Break: EndIf
    Ifs+1
    If x = 4: Break: EndIf
    Ifs+1
    If x = 5: Break: EndIf
    Ifs+1
    If x = 6: Break: EndIf
    Ifs+1
    If x = 7: Break: EndIf
    Ifs+1
    If x = 8: Break: EndIf
    Ifs+1
    If x = 9: Break: EndIf
    Ifs+1
    If x = 10: Break: EndIf
    Ifs+1
    If x = 11: Break: EndIf
    Ifs+1
    If x = 12: Break: EndIf
    Ifs+1
    If x = 13: Break: EndIf
    Ifs+1
    If x = 14: Break: EndIf
    Ifs+1
    If x = 15: Break: EndIf
    Ifs+1
    If x = 16: Break: EndIf
    Ifs+1
    If x = 17: Break: EndIf
    Ifs+1
    If x = 18: Break: EndIf
    Ifs+1
    If x = 19: Break: EndIf
  ForEver
EndProcedure

Procedure DoTest(x)  ;= 130
  Repeat
    Ifs+1
    If x <= 9    
      Ifs+1
      If x = 0: Break: EndIf
      Ifs+1
      If x = 1: Break: EndIf
      Ifs+1
      If x = 2: Break: EndIf
      Ifs+1
      If x = 3: Break: EndIf
      Ifs+1
      If x = 4: Break: EndIf
      Ifs+1
      If x = 5: Break: EndIf
      Ifs+1
      If x = 6: Break: EndIf
      Ifs+1
      If x = 7: Break: EndIf
      Ifs+1
      If x = 8: Break: EndIf
      Ifs+1
      If x = 9: Break: EndIf     
    Else      
      Ifs+1
      If x = 10: Break: EndIf
      Ifs+1
      If x = 11: Break: EndIf
      Ifs+1
      If x = 12: Break: EndIf
      Ifs+1
      If x = 13: Break: EndIf
      Ifs+1
      If x = 14: Break: EndIf
      Ifs+1
      If x = 15: Break: EndIf
      Ifs+1
      If x = 16: Break: EndIf
      Ifs+1
      If x = 17: Break: EndIf
      Ifs+1
      If x = 18: Break: EndIf
      Ifs+1
      If x = 19: Break: EndIf
    EndIf
  ForEver
EndProcedure

Procedure DoTest(x)  ;= 105
  Repeat
    Ifs+1
    If x <= 4    
      Ifs+1
      If x = 0: Break: EndIf
      Ifs+1
      If x = 1: Break: EndIf
      Ifs+1
      If x = 2: Break: EndIf
      Ifs+1
      If x = 3: Break: EndIf
      Ifs+1
      If x = 4: Break: EndIf
    EndIf
    Ifs+1
    If x <= 9
      Ifs+1
      If x = 5: Break: EndIf
      Ifs+1
      If x = 6: Break: EndIf
      Ifs+1
      If x = 7: Break: EndIf
      Ifs+1
      If x = 8: Break: EndIf
      Ifs+1
      If x = 9: Break: EndIf     
    EndIf
    Ifs+1
    If x <= 14
      Ifs+1
      If x = 10: Break: EndIf
      Ifs+1
      If x = 11: Break: EndIf
      Ifs+1
      If x = 12: Break: EndIf
      Ifs+1
      If x = 13: Break: EndIf
      Ifs+1
      If x = 14: Break: EndIf
    Else
      Ifs+1
      If x = 15: Break: EndIf
      Ifs+1
      If x = 16: Break: EndIf
      Ifs+1
      If x = 17: Break: EndIf
      Ifs+1
      If x = 18: Break: EndIf
      Ifs+1
      If x = 19: Break: EndIf
    EndIf
  ForEver
EndProcedure



Procedure DoTest(x)  ;= 106  (we've breached square root - there are now more Level1 tests than Level2, bzzzt!)
  Repeat
    Ifs+1
    If x <= 3    
      Ifs+1
      If x = 0: Break: EndIf
      Ifs+1
      If x = 1: Break: EndIf
      Ifs+1
      If x = 2: Break: EndIf
      Ifs+1
      If x = 3: Break: EndIf
    EndIf
    Ifs+1
    If x <= 7    
      Ifs+1
      If x = 4: Break: EndIf      
      Ifs+1
      If x = 5: Break: EndIf
      Ifs+1
      If x = 6: Break: EndIf
      Ifs+1
      If x = 7: Break: EndIf
    EndIf
    Ifs+1
    If x <= 11      
      Ifs+1
      If x = 8: Break: EndIf
      Ifs+1
      If x = 9: Break: EndIf     
      Ifs+1
      If x = 10: Break: EndIf
      Ifs+1
      If x = 11: Break: EndIf
    EndIf
    Ifs+1
    If x <= 15      
      Ifs+1
      If x = 12: Break: EndIf
      Ifs+1
      If x = 13: Break: EndIf
      Ifs+1
      If x = 14: Break: EndIf
      Ifs+1
      If x = 15: Break: EndIf
    Else      
      Ifs+1
      If x = 16: Break: EndIf
      Ifs+1
      If x = 17: Break: EndIf
      Ifs+1
      If x = 18: Break: EndIf
      Ifs+1
      If x = 19: Break: EndIf
    EndIf    
  ForEver
EndProcedure
Top
Post Reply

Return to “Tricks 'n' Tips”