Jump table - faster case selection

[Keya]

A jump table is an efficient way to immediately jump to the code you need to use, instead of, for example, a "Select Case" statement where every case needs to be iterated through until it finds the right one. If you have a "Select Case" statement with 100 cases, you could require up to 100 tests to find the right match, whereas with a jump table you jump to the right code on the 1st try, every time.

SCENARIO: Imagine you have an image and you want to go through every pixel (For y = 1 to height, and For x = 1 to width), but you want to be able to do a different operation to each pixel each time - perhaps fill each pixel a certain color, or invert every pixel etc, but you don't want to create different versions of the same large procedure where they only have one line different.

Lets say we have 5 operations to choose from. You might use something like this:

Code: Select all

Procedure ModifyAllPixels(Operation, width, height)
  For y = 1 To height
    For x = 1 To width
      
      Select Operation          
        Case PIXELOP_FILL:
          ;DoFill
          
        Case PIXELOP_ADD:
          ;DoAdd
          
        Case PIXELOP_SUB:
          ;DoSub
          
        Case PIXELOP_INVERT:
          ;DoInvert
          
        Case PIXELOP_REPLACE:
          ;DoReplace
          
      EndSelect
    Next x
  Next y
EndProcedure

The BEST CASE scenario - the operation will be the 1st tested case statement (PIXELOP_FILL).
But the WORST CASE scenario - it has to test all 5 case statements if it's the last one (PIXELOP_REPLACE). And that's for EVERY pixel so it could get really slow especially with more operations/case statements to test!

That's called O(somethingorrather)-time... or something.

Using a JUMP TABLE allows us to instead jump straight to the operation we want (best case scenario every time):

Code: Select all

Enumeration PIXELOPS 0 Step SizeOf(Integer) 
  #PIXELOP_REPLACE  ;their values are 32bit-x86 (0,4,8..) or 64bit-x64 (0,8,16..) indexes
  #PIXELOP_ADD
  #PIXELOP_SUB
  #PIXELOP_FILL
  #PIXELOP_INVERT
  #PIXELOPEND
EndEnumeration


Procedure ModifyAllPixels(Operation, width, height)
  If Operation < 0 Or Operation => #PIXELOPEND: ProcedureReturn 0: EndIf  ;ensure valid Operation index
  Protected OpFunc = PeekI(?PIXELOP_JMPTABLE + Operation)  ;the address of the specified PIXELOP_xxx label
  
  For y = 1 To height
    For x = 1 To width

      ! jmp dword [p.v_OpFunc] ;Jump to the specified Operation using the jump table. Change dword to qword on x64
      
      ;These can be in any order...
      PIXELOP_FILL:
      ;DoFill
      GOTO PixelOpEnd
      
      PIXELOP_ADD:
      ;DoAdd
      GOTO PixelOpEnd
      
      PIXELOP_SUB:
      ;DoSub
      GOTO PixelOpEnd
      
      PIXELOP_INVERT:
      ;DoInvert
      GOTO PixelOpEnd                
      
      PIXELOP_REPLACE:             
      ;DoReplace
      ;GOTO PixelOpEnd ;not needed on last
      
      PixelOpEnd:
    Next x
  Next y
  
  DataSection          ;the DataSection MUST be WITHIN the Procedure code for labels to be recognised by the compiler
    PIXELOP_JMPTABLE:  ;these MUST be listed in the same order as listed in Enumeration PIXELOPS
    Data.i ?PIXELOP_REPLACE, ?PIXELOP_ADD, ?PIXELOP_SUB, ?PIXELOP_FILL, ?PIXELOP_INVERT ;addresses of labels
  EndDataSection
EndProcedure

[Fred]

You can also do it with structure and protytope:

Code: Select all

Enumeration PIXELOPS
  #PIXELOP_REPLACE
  #PIXELOP_ADD
  #PIXELOP_SUB
  #PIXELOP_FILL
  #PIXELOP_INVERT
  #PIXELOPEND
EndEnumeration

Prototype GenericOpPrototype(Value)


Structure JumpStructure
  JumpTable.GenericOpPrototype[5]
EndStructure


Procedure ReplaceOp(Value)
  Debug "Replace " + Value
EndProcedure

Procedure AddOp(Value)
  Debug "Add " + Value
EndProcedure

Procedure SubOp(Value)
  Debug "Sub " + Value
EndProcedure

Procedure FillOp(Value)
  Debug "Fill " + Value
EndProcedure

Procedure InvertOp(Value)
  Debug "Invert " + Value
EndProcedure


a.JumpStructure
a\JumpTable[#PIXELOP_REPLACE] = @ReplaceOp()
a\JumpTable[#PIXELOP_ADD] = @AddOp()
a\JumpTable[#PIXELOP_SUB] = @SubOp()
a\JumpTable[#PIXELOP_FILL] = @FillOp()
a\JumpTable[#PIXELOP_INVERT] = @InvertOp()

For k = 0 To 4
  a\JumpTable[k](k)
Next

For optimal perf, you could just use a function pointer and select it before running your inner loop

[davido]

@Fred,

Nice demo, thank you.

[Psychophanta]

A bit ugly.
There should work dim for prototypes definitions, but it does not

Code: Select all

Enumeration PIXELOPS
  #PIXELOP_REPLACE
  #PIXELOP_ADD
  #PIXELOP_SUB
  #PIXELOP_FILL
  #PIXELOP_INVERT
  #PIXELOPEND
EndEnumeration

Prototype GenericOpPrototype(Value)

Procedure ReplaceOp(Value)
  Debug "Replace " + Value
EndProcedure

Procedure AddOp(Value)
  Debug "Add " + Value
EndProcedure

Procedure SubOp(Value)
  Debug "Sub " + Value
EndProcedure

Procedure FillOp(Value)
  Debug "Fill " + Value
EndProcedure

Procedure InvertOp(Value)
  Debug "Invert " + Value
EndProcedure


Dim b.GenericOpPrototype(4)
b(#PIXELOP_REPLACE) = @ReplaceOp()
b(#PIXELOP_ADD) = @AddOp()
b(#PIXELOP_SUB) = @SubOp()
b(#PIXELOP_FILL) = @FillOp()
b(#PIXELOP_INVERT) = @InvertOp()


For k = #PIXELOP_REPLACE To #PIXELOP_INVERT
  b(k)
Next

[wilbert]

A bit ugly.
There should work dim for prototypes definitions, but it does not

You can use dim with a structure with a prototype in it
http://www.purebasic.fr/english/viewtop ... 81#p496681
but that also probably not what you want.

[Keya]

btw the reason im using a JMP table is to avoid the overhead of CALLs (which isn't just the call and ret instructions, but also the function prologue and epilogue instructions), which is why i didn't put each pixel operation in its own Procedure()

[wilbert]

I think inline asm is the easies option for now.
It would be interesting to check if it really makes a lot of difference in speed if you do a jmp vs a call.

In this case I probably would make a separate case for each operation which handles 1 line of pixels instead of 1 pixel.

[#NULL]

i made a test.

the jmp (goto) is almost as fast as a direct inline operation.
select is betweeen jmp and function calls.

Code: Select all

case 1 total (inline) : 3799
case 2 total (goto)   : 3883
case 3 total (select) : 4818
case 4 total (func)   : 5879
case 5 total (proto)  : 6517

the difference between func and proto doesn't mean much and goes almost away if you cache the function pointer before going into the loops in the proto case.

increase maxPerCase if its to fast on you computer.

Code: Select all

; testing speed of..

; - direct inline operation
; - jumptable using goto
; - select
; - direct function pointer (using protoype)
; - jumptable using structure array of prototypes

; ----------------------------------------

Macro OP(i, k, c)    ; used by all cases as final operation
  Plot(i, k, c)      ; (uncomment for empty operation)
EndMacro

; ----------------------------------------

Procedure test_inline(w, h)
  w - 1
  h - 1
  For k=0 To h
    For i=0 To w
      OP(i, k, $ffffff)
    Next
  Next
EndProcedure

; ----------------------------------------

Enumeration GOTO_PIXELOPS 0 Step SizeOf(Integer)
  #GOTO_PIXELOP_DUMMY_1  ;their values are 32bit-x86 (0,4,8..) or 64bit-x64 (0,8,16..) indexes
  #GOTO_PIXELOP_REPLACE
  #GOTO_PIXELOP_DUMMY_2
  #GOTO_PIXELOPEND
EndEnumeration

Procedure test_goto(w, h, pixelop)
  If pixelop < 0 Or pixelop => #GOTO_PIXELOPEND
    PrintN("test_goto error")
    ProcedureReturn 0
  EndIf
  Protected OpFunc = PeekI(?PIXELOP_JMPTABLE + Operation)
  w - 1
  h - 1
  For k=0 To h
    For i=0 To w
      CompilerIf #PB_Processor_x64
        ! jmp qword [p.v_OpFunc]
      CompilerElse
        ! jmp dword [p.v_OpFunc]
      CompilerEndIf
     
      GOTO_PIXELOP_DUMMY_1:
      OP(i, k, $ffffff)
      Goto PixelOpEnd
     
      GOTO_PIXELOP_REPLACE:
      OP(i, k, $ffffff)
      Goto PixelOpEnd
     
      GOTO_PIXELOP_DUMMY_2:
      OP(i, k, $ffffff)
      ;Goto PixelOpEnd ;not needed on last
     
      PixelOpEnd:
    Next i
  Next k
 
  DataSection
    PIXELOP_JMPTABLE:  ;### These MUST be listed in the same order as listed in Enumeration PIXELOPS
    Data.i ?GOTO_PIXELOP_DUMMY_1, ?GOTO_PIXELOP_REPLACE, ?GOTO_PIXELOP_DUMMY_2 ;addresses of labels
  EndDataSection
EndProcedure

; ----------------------------------------

Enumeration SELECT_PIXELOPS
  #SELECT_PIXELOP_DUMMY_1
  #SELECT_PIXELOP_REPLACE
  #SELECT_PIXELOP_DUMMY_2
  #SELECT_PIXELOPEND
EndEnumeration

Procedure test_select(w, h, pixelop)
  If pixelop < 0 Or pixelop => #SELECT_PIXELOPEND
    PrintN("test_select error")
    ProcedureReturn 0
  EndIf
  w - 1
  h - 1
  For k=0 To h
    For i=0 To w
      Select pixelop
        Case #SELECT_PIXELOP_DUMMY_1
          ;
        Case #SELECT_PIXELOP_REPLACE
          OP(i, k, $ffffff)
        Case #SELECT_PIXELOP_DUMMY_2
          ;
      EndSelect
    Next i
  Next k
EndProcedure

; ----------------------------------------

Prototype func_pixelop(i, k, c)

Procedure func_replace(i, k, c)
  OP(i, k, c)
EndProcedure

Procedure test_func(w, h, pixelop.func_pixelop)
  If pixelop <> @func_replace()
    PrintN("test_func error")
    ProcedureReturn 0
  EndIf
  w - 1
  h - 1
  For k=0 To h
    For i=0 To w
      pixelop(i, k, $ffffff)
    Next
  Next
EndProcedure

; ----------------------------------------

Enumeration PROTO_PIXELOPS
  #PROTO_PIXELOP_DUMMY_1
  #PROTO_PIXELOP_REPLACE
  #PROTO_PIXELOP_DUMMY_2
  #PROTO_PIXELOPEND
EndEnumeration

Prototype proto_pixelop(i, k, c)

Structure JumpStructure
  JumpTable.proto_pixelop[#PROTO_PIXELOPEND]
EndStructure

Procedure proto_replace(i, k, c)
  OP(i, k, c)
EndProcedure

jt.JumpStructure
jt\JumpTable[#PROTO_PIXELOP_DUMMY_1] = @proto_replace()
jt\JumpTable[#PROTO_PIXELOP_REPLACE] = @proto_replace()
jt\JumpTable[#PROTO_PIXELOP_DUMMY_2] = @proto_replace()

Procedure test_proto(w, h, pixelop)
  If pixelop < 0 Or pixelop => #PROTO_PIXELOPEND
    PrintN("test_proto error")
    ProcedureReturn 0
  EndIf
  Shared jt
 
  ;Protected func.proto_pixelop = jt\JumpTable[pixelop]
 
  w - 1
  h - 1
  For k=0 To h
    For i=0 To w
      jt\JumpTable[pixelop](i, k, $ffffff)
      ;func(i, k, $ffffff)
    Next
  Next
EndProcedure

; ----------------------------------------

If #PB_Compiler_Debugger
  MessageRequester("", "disable the debugger!")
  End
EndIf
OpenConsole()

w = 1000
h = 1000
CreateImage(0, w, h)
If StartDrawing(ImageOutput(0))
  ;DrawingMode(#PB_2DDrawing_AllChannels)
 
  t1 = 0
  t2 = 0
  t3 = 0
  t4 = 0
  t5 = 0
 
  alternatingCases = 10
  maxPerCase = 50
 
  For n=1 To alternatingCases
   
    ; test inline
    t = ElapsedMilliseconds()
    For m=0 To maxPerCase
      test_inline(w, h)
    Next
    t = ElapsedMilliseconds()-t
    PrintN("case 1: " + t)
    t1 + t
   
    ; test goto
    t = ElapsedMilliseconds()
    For m=0 To maxPerCase
      test_goto(w, h, #GOTO_PIXELOP_REPLACE)
    Next
    t = ElapsedMilliseconds()-t
    PrintN("case 2: " + t)
    t2 + t
   
    ; test select
    t = ElapsedMilliseconds()
    For m=0 To maxPerCase
      test_select(w, h, #SELECT_PIXELOP_REPLACE)
    Next
    t = ElapsedMilliseconds()-t
    PrintN("case 3: " + t)
    t3 + t
   
    ; test func
    t = ElapsedMilliseconds()
    For m=0 To maxPerCase
      test_func(w, h, @func_replace())
    Next
    t = ElapsedMilliseconds()-t
    PrintN("case 4: " + t)
    t4 + t
   
    ; test proto
    t = ElapsedMilliseconds()
    For m=0 To maxPerCase
      test_proto(w, h, #PROTO_PIXELOP_REPLACE)
    Next
    t = ElapsedMilliseconds()-t
    PrintN("case 5: " + t)
    t5 + t
   
  Next
 
  StopDrawing()
EndIf

PrintN("")
PrintN("case 1 total (inline) : " + t1)
PrintN("case 2 total (goto)   : " + t2)
PrintN("case 3 total (select) : " + t3)
PrintN("case 4 total (func)   : " + t4)
PrintN("case 5 total (proto)  : " + t5)
Input()

[#NULL]

i just reread the topic tile and added a case for select, which is somewhere betweeen jmp and function calls.

[BarryG]

Okay, so I'm trying to understand jump tables. I have an app that has like 100 x Case statements, all of which are specific non-related strings, so I can't use "Case 1 To 10" or anything like that. Obviously if the last Case (100) is the match, then the app has so iterate over all the previous 99 to get to it. So, below is a small example. Without judging it or telling me to use Val() or Dim instead, how would I literally convert this example to a jump table version? No other changes to the logic, please. Thanks.

Code: Select all

Global one$="1"
Global two$="2"
Global three$="3"
Global four$="4"
Global five$="5"
; Global six$ to ninetynine$ would go here.
Global hundred$="100"

Procedure DoSomething(num$)
  Select num$
    Case one$ : Debug 1
    Case two$ : Debug 2
    Case three$ : Debug 3
    Case four$ : Debug 4
    Case five$ : Debug 5
    ; Case six$ to ninetynine$ would go here.
    Case hundred$ : Debug 100
  EndSelect
EndProcedure

DoSomething(LTrim("00100","0")) ; Want Debug output of: 100

[Keya]

Barry, the example (both before and after) is in the first post! it's virtually the same as yours so it should be very easy to convert to a jump table based on my example, and as you can see there's not much code (or code change) involved so it should be easy for somebody with your experience. Please let me know if there's anything my example doesn't make clear enough. Please try to convert it yourself first by reading through my example code (and post it here!), but if you get stuck then I will help.

[BarryG]

Not sure how to convert it to use strings? Below is my work. Note: You have to remember, that even though I'm sending the number 100 to the procedure, this is actually a non-numerical string in my production app. I'm just using a literal string of "100" for this example, when it reality I could be sending "hello" or "there" instead.

Code: Select all

Enumeration 1 Step SizeOf(Integer)
  #JUMP_ONE
  #JUMP_TWO
  #JUMP_THREE
  #JUMP_FOUR
  #JUMP_FIVE
  ; #JUMP_SIX TO #JUMP_NINETYNINE HERE
  #JUMP_HUNDRED
EndEnumeration

Procedure DoSomething(num$)

  Protected OpFunc = PeekI(?JUMPTABLE + num$)
  
  !jmp dword [p.v_OpFunc]

  JUMP_ONE:
    Debug 1
    Goto JumpTableEnd
    
  JUMP_TWO:
    Debug 2
    Goto JumpTableEnd
    
  JUMP_THREE:
    Debug 3
    Goto JumpTableEnd
    
  JUMP_FOUR:
    Debug 4
    Goto JumpTableEnd
    
  JUMP_FIVE:
    Debug 5
    Goto JumpTableEnd
    
  JUMP_HUNDRED:
    Debug 100
    Goto JumpTableEnd
    
  JumpTableEnd:
  
EndProcedure

DoSomething(LTrim("00100","0")) ; Want to see: 100

End

DataSection
  JUMPTABLE:
  Data.i ?JUMP_ONE, ?JUMP_TWO, ?JUMP_THREE, ?JUMP_FOUR, ?JUMP_FIVE, ?JUMP_HUNDRED
EndDataSection

[Keya]

the conversion looks good!
but yes you can't use strings for jumps, need to use integers ... so you need to assign each string an integer. (You could possibly do this with the ADDRESS of each string but I'm just thinking out loud)
And although you could be using non-numeric strings like "hello" instead of "3" etc, you still know the string a priori as they're static so it shouldn't be a problem.

Try to find a way to change Procedure DoSomething(num$) to Procedure DoSomething(num.i), where num.i is the #STRING_INDEX. You might need a function to convert a string to its index, eg StringToIndex.i(num$) and call that first.
Or perhaps group the strings into an Array ... String(0) = "1", String(2) = "2", String(3) = "Hello"

[BarryG]

I'm still trying, but as a test I changed:

Code: Select all

Protected OpFunc = PeekI(?JUMPTABLE + num$)

to this:

Code: Select all

Protected OpFunc = PeekI(?JUMPTABLE + num) ; num instead of num$

And now I get this error, which doesn't make sense:

Code: Select all

Label not found (JUMP_ONE)

The label definitely does exist in the procedure... so, what the?

[Keya]

And now I get this error, which doesn't make sense:

Code: Select all

Label not found (JUMP_ONE)

The label definitely does exist in the procedure... so, what the?

That is super weird!!! I confirm I get the same result. I'm not sure why though :/

[edit] Found out why! check next reply