SyntaxBomb - Indie Coders

Ive been messing around with some case statement code recently and am starting to find that.

Lets say we have case 0 to 255 works as expected. A lovely sequential order works perfect!

Now rearrange that as 0,1,255,16,24 as you write the code! And it really bogs down why!?

Baggey

can you send a code example? I do not understand the problem..

The generated code of:
SuperStrict
Framework Brl.StandardIO

Local i:Int = 0
Select i
case 0; print "is 0"
case 1; print "is 1"
case 2; print "is 2"
default; print "is something else"
End Select


is:
#include "untitled1.bmx.console.release.linux.x64.h"
struct BBString_4{BBClass_String* clas;BBULONG hash;int length;BBChar buf[4];};
struct BBString_17{BBClass_String* clas;BBULONG hash;int length;BBChar buf[17];};
static struct BBString_4 _s0={
&bbStringClass,
0x26e6f62aab5c04d6,
4,
{105,115,32,48}
};
static struct BBString_4 _s1={
&bbStringClass,
0x19b78fc511e60752,
4,
{105,115,32,49}
};
static struct BBString_4 _s2={
&bbStringClass,
0xefff255b16b3c4e,
4,
{105,115,32,50}
};
static struct BBString_17 _s3={
&bbStringClass,
0x41437bbe2f24fb4b,
17,
{105,115,32,115,111,109,101,116,104,105,110,103,32,101,108,115,101
}
};
static int _bb_main_inited = 0;
int _bb_main(){
if (!_bb_main_inited) {
_bb_main_inited = 1;
__bb_brl_blitz_blitz();
__bb_brl_standardio_standardio();
BBINT bbt_i=0;
BBINT bbt_=bbt_i;
if(bbt_==0){
brl_standardio_Print((BBString*)&_s0);
}else{
if(bbt_==1){
brl_standardio_Print((BBString*)&_s1);
}else{
if(bbt_==2){
brl_standardio_Print((BBString*)&_s2);
}else{
brl_standardio_Print((BBString*)&_s3);
}
}
}
return 0;
}
return 0;
}


So it means it uses "nested if-else" to simulate the "Select".
One needs to measure if "nested if-else" are slower than "else-ifs" ... or if the C compiler optimizes that at the end anyways.


Edit: To answer what might "bog down" the speed is the order of your "ifs" (or here - the order of your "select cases"))
Assume you have to select by the "age" of people.
Now you know most people are 18 or older.
If your select looks like this:

select
case 1; ...
case 2; ...
case 3; ...
...
case 18; ...
...
end select

Then the code will do a lot of checks before it reaches the 18 ... "if age == 1; else if age == 2 ... else if age == 3 ..."

This means to optimize ifs/ifelses/selects you might consider "sorting" them by their probabilities. So if your "instructions" are mostly 3 digits and more, than start with them.
Another "speedup" can possibly be reached if you "nest" your selects

if instruction < 100
  Select
     case 1...
  End Select
else
  Select
     case 100
     case 101
  End Select
endif

This will "branch" earlier, and in our case of an instruction of "120" you will not check 1 till 100 before.

Yet this all sems to indicate that the wrong "logic" might be used here. Maybe having a lookup table containing "instruction -> function" is faster in such a case.

bye
Ron

To emphasize that:
SuperStrict
Framework Brl.StandardIO


Local t:Int
Local runs:Int = 1000000


t = Millisecs()

Local s:Int = 0
For local j:Int = 0 until runs
Local i:Int = 30
Select i
case 0; s :+ i
case 1; s :+ i
case 2; s :+ i
case 3; s :+ i
case 4; s :+ i
case 5; s :+ i
case 6; s :+ i
case 7; s :+ i
case 8; s :+ i
case 9; s :+ i
case 10; s :+ i
case 11; s :+ i
case 12; s :+ i
case 13; s :+ i
case 14; s :+ i
case 15; s :+ i
case 16; s :+ i
case 17; s :+ i
case 18; s :+ i
case 19; s :+ i
case 20; s :+ i
case 21; s :+ i
case 22; s :+ i
case 23; s :+ i
case 24; s :+ i
case 25; s :+ i
case 26; s :+ i
case 27; s :+ i
case 28; s :+ i
case 29; s :+ i
case 30; s :+ i
End Select
Next
print s
print "took " + (Millisecs() - t) + "ms"

s = 0
t = Millisecs()
For local j:Int = 0 until runs
Local i:Int = 30
if i = 0
s :+ i
elseif i = 1
s :+ i
elseif i = 2
s :+ i
elseif i = 3
s :+ i
elseif i = 4
s :+ i
elseif i = 5
s :+ i
elseif i = 6
s :+ i
elseif i = 7
s :+ i
elseif i = 8
s :+ i
elseif i = 9
s :+ i
elseif i = 10
s :+ i
elseif i = 11
s :+ i
elseif i = 12
s :+ i
elseif i = 13
s :+ i
elseif i = 14
s :+ i
elseif i = 15
s :+ i
elseif i = 16
s :+ i
elseif i = 17
s :+ i
elseif i = 18
s :+ i
elseif i = 19
s :+ i
elseif i = 20
s :+ i
elseif i = 21
s :+ i
elseif i = 22
s :+ i
elseif i = 23
s :+ i
elseif i = 24
s :+ i
elseif i = 25
s :+ i
elseif i = 26
s :+ i
elseif i = 27
s :+ i
elseif i = 28
s :+ i
elseif i = 29
s :+ i
elseif i = 30
s :+ i
EndIf
Next
print s
print "took " + (Millisecs() - t) + "ms"


To see a time difference do a debug build (else you will for sure see "0ms" - maybe because it optimizes stuff automatically).

You will see there is only a marginal difference (in my case it is 1044ms vs 1029ms ... so the "elseif" should be faster than a nested if).

But now replace the "if i = 0" with "if i = 30" and check times then. For me it dropped to 99ms. So this means the other 900ms are just used because of all the other "ifs" it checks first.

The more "biased" the incoming data is (so not equally distributed) the more you benefit from a custom "ordering" or a kind of "pre-filtering/pre-branching".


Maybe think of your old TV channel ordering years ago - you ordered by your favorites so you do not need to go through all these nonsense shopping channels. You also order your clothes so the "most often used" ones are easier to reach ... etc etc.

bye
Ron

Quote from: Derron on May 01, 2024, 12:17:49...
Yet this all sems to indicate that the wrong "logic" might be used here. Maybe having a lookup table containing "instruction -> function" is faster in such a case.
..
bye
Ron

This is interesting. But how can this be done? The 255 functions or branches would be part of a ARRAY?

This code is only symbolic (not working). How can I add a FUNCTION as FIELD of a TYPE?

SuperStrict
ActionTable.Add 0,A
ActionTable.Add 1,B
ActionTable.Add 2,C

ActionTable.DoIt 2

Type ActionTable
    Global Action:ActionTable[3]
    Field  Reaction:TFunction

    Function Add( Number:Int, Reaction:Byte Ptr)
            Action[Number] = New ActionTable
            Action[Number].Reaction = New TFunction
    End Function
   
    Function DoIt(Number:Int)
        Action[Number].Reaction()
    End Function
End Type

Function A()
    Print "A"
End Function

Function B()
    Print "B"
End Function

Function C()
    Print "C"
End Function


You simply create an array of something.

If you want to store a kind of "config" together with the function itself you simply do
Type TFunctionHandler
   Method Run:Int()
   End Method
End Type

Global functionHandlers:TFunctionHandler[255] '255 handlers?

...

Type TFunctionHandlerXYZ extends TFunctionHandler
  Method New(param1:Int, param2:String)
     ...
  End Method


  Method Run:Int()
    if param2 is "hello" then return param1
    return 0
  End Method
End Type


functionHandlers[1 -1] = New TFunctionHandlerXYZ(100, "hello")


receivedCommand = somewhereSomehow...
if receivedCommand <= functionHandlers.length and receivedCommand > 0
  local handler:TFunctionHandler = functionHandlers[receivedCommand -1]
  if handler then handler.run()
endif


Alternatively - if you want to avoid the "type" overhead and have a unified "param"-style, then you can do

Global commandFunctions:Int(o:object)[255] '255 of them?
'or
'Global commandFunctions:Int(o:object)[] 'empty at initialization


Function CommandXYZFunction:Int(o:Object)
End Function

commandFunctions[1 -1] = CommandXYZFunction

...

params = new TMap 'or a list or a string, array, ... some object
if receivedCommand <= commandFunctions.length and receivedCommand > 0
  local f:int(o:object) = commandFunctions[receivedCommand -1]
  if f then f(params)
endif



And last but not least - how to store the function in type instance
Type TFunctionHandler
   Field myFunction:Int(params:object)

   Method Run:Int(params:object)
    if myFunction Then Return myFunction(params)
    Return 0
   End Method
End Type

Global functionHandlers:TFunctionHandler[255] '255 handlers?

...
Function CommandXYZFunction:Int(o:Object)
End Function

functionHandlers[1 -1] = New TFunctionHandler()
functionHandlers[1 -1].myFunction = CommandXYZFunction


params = new TMap 'or a list or a string, array, ... some object
receivedCommand = somewhereSomehow...
if receivedCommand <= functionHandlers.length and receivedCommand > 0
  local handler:TFunctionHandler = functionHandlers[receivedCommand -1]
  if handler then handler.run(params)
  'or directly... if you never override TFunctionHandler
  if handler and handler.myFunction Then handler.myFunction(params)
endif



bye
Ron

Thank you @Derron . This will solve @Baggey 's problems with performance.

You gave a lot of information! A little bit simplified this means, I can "store" 255 functions in an array and now call one of the 255 functions via it's array-index.
This would prevent @Baggey  from iterating through 255 Ifs or Cases.

Each Instruction-ID lead directly to the corresponding function without searching through a table:

(this is a runnable example)
SuperStrict
Global NextInstruction:Int=2

Global ActionTable()[3]
'  put the functions into the array:
ActionTable[0] = f_A
ActionTable[1] = f_B
ActionTable[2] = f_C

CallFunction NextInstruction

Function CallFunction(InstructionID:Int)
    ActionTable[InstructionID]()
End Function

Function f_A()
    Print "A"
End Function

Function f_B()
    Print "B"
End Function

Function f_C()
    Print "C"
End Function

And here is the same with parameters sent to the function:

SuperStrict
Global NextInstruction:Int=2
'  put the functions into the array:

Global ActionTable(Value:Int)[] =[f_A, f_B, f_C]

CallFunction NextInstruction, 4

Function CallFunction(InstructionID:Int, value:Int)
    ActionTable[InstructionID] value
End Function

Function f_A(Value:Int)
    Print "A" + Value
End Function

Function f_B(Value:Int)
    Print "B" + Value
End Function

Function f_C(Value:Int)
    Print "C" + Value
End Function


And here is the same with returning values:

SuperStrict
'  put the functions into the array:
Global ActionTable:Int(Value:Int)[] = [Plus, Minus, Square]

Print CallFunction(0,4)
Print CallFunction(1,4)
Print CallFunction(2,4)

Function CallFunction:Int(InstructionID:Int, Value:Int)
    Local f:Int(t:Int) = ActionTable[InstructionID]
    Return f(Value)
    'Return ActionTable[InstructionID](Value)
End Function

Function Plus:Int(Value:Int)
    Print "function PLUS 5+" + Value + " = " + (Value+5)
    Return (Value+5)
End Function

Function Minus:Int(Value:Int)
    Print "function MINUS 5-" + Value + " = " + (5-Value)
    Return (5-Value)
End Function

Function Square:Int(Value:Int)
    Print "function SQUARE " + Value + "^2 = " + (Value^2)
    Return (Value^2)
End Function

But why do I need two code lines in the CallFunction() and cannot be done with the one line?

You can do it in one line ... but this will lead to two lookups for the array access (an array access is more costly than a local variable on the stack I guess).

If you KNOW that a function exists for the given ID (so 0-255 in the 256 indices array are "occupied") then you do not need to have a check.
But if you do NOT know, then you need to check the existence.

'check
If myarr[10] then myarr[10]()
'no check
myarr[10]

See that in the first case I do access the array element via its index TWICE.
It is rather "common" to store stuff in a temporary variable if you use it multiple times.


bye
Ron

Thankyou @Derron and @Midimaster even more speed

Kind Regards Baggey