Jump Tables Effectiveness

[zemtex]

Howdy.

Does anyone have good experience with jump tables. I've used them a couple of times before, but that was many many years ago in 16 bit dos with TASM. I have a procedure with 43 switches, if - elseif statements. Do you think that using a jump table will improve that amount of switches?

In my understanding a jump table has a little bit overhead in the beginning, this overhead will make it slightly slower for the very first few set of switches, but in average it will make the whole line of switches perform with the same speed.

[Tight_Coder_Ex]

It depends on how you've implemented your switches.  Lets say for example you use -A -B -C ..... -Z for switches.  Then you would just need 26 dword vectors and by simply calculation you could determine by the address that is at that offset where to branch or if not applicable that entry would be zero

A = 0000 = 401118
B = 0004 = 000000
C = 0008 = 000000
D = 000C = 40127c

As you can see -A -D would result in something being processed, but nothing for B & C.

[zemtex]

I've implemented a jump table for all 43 switches. Oh yes it is faster now. I have pretty new hardware in my computer so it should be a pinpoint that jump tables are still effective.

[jj2007]

Here is a very simple example. It is definitely smaller than a huge .if .elseif .endif chain, but less flexible of course...

Code Select Expand

include \masm32\include\masm32rt.inc

.code
switches dd MyTest1, MyTest2, MyTest3

start: mov ebx, 2
call switches[4*ebx-4]
dec ebx
call switches[4*ebx-4]
add ebx, 2
call switches[4*ebx-4]
inkey "OK?"
exit

MyTest1 proc
  print "proc1", 13, 10
  ret
MyTest1 endp

MyTest2 proc
  print "proc2", 13, 10
  ret
MyTest2 endp

MyTest3 proc
  print "proc3", 13, 10
  ret
MyTest3 endp

end start


[zemtex]

I have coded it like this:

      shl ecx, 2
      add ecx, OFFSET JmpTable
      jmp dword ptr [ecx]

Can you give me a few reasons why you prefer to multiply by 4 inside the brackets instead of shifting it?

[jj2007]

I have coded it like this:

      shl ecx, 2
      add ecx, OFFSET JmpTable
      jmp dword ptr [ecx]

Can you give me a few reasons why you prefer to multiply by 4 inside the brackets instead of shifting it?

25% shorter, see attachment.

[zemtex]

What would you recommend of the two:

Method1:
      xor ecx, ecx
      mov cx, ax
      jmp [4*ecx+OFFSET JmpTable]

Method2:
      movzx ecx, ax
      shl ecx, 2
      add ecx, OFFSET JmpTable
      jmp dword ptr [ecx]

..or even use the Lea instruction here?

[qWord]

what about:

Code Select Expand

and eax,0ffffh
jmp JmpTable[4*eax]
:bg

[zemtex]

I wanted to do that in the first place but I need to conserve the H.O word of eax for the call destination.

[qWord]

I need to conserve the H.O word of eax for the call destination.

a hard problem to solve  :bdg

[zemtex]

.......................Thanks guys!

I'll try different solutions. I havent tried to time any of the methods mentioned in this thread, its kind of problematic to test it in a few minutes because I have to set up a fake jmp table to time the thing.

[zemtex]

btw. I timed these two:

Method 1:
   xor ecx, ecx
   mov cx, ax

Method 2:
   movzx ecx, ax

Method 2 was way faster.
=====================================================

After timing different ways to code it, I found that this code gave the best times:

      movzx ecx, ax
      lea ecx, [4*ecx+JmpTable]
      jmp dword ptr [ecx]

[zemtex]

   call switches[4*ebx-4]

Instead of subtracting 4, add a dummy pointer at index 0 in the jump table. That will save subtraction.

[jj2007]

   call switches[4*ebx-4]

Instead of subtracting 4, add a dummy pointer at index 0 in the jump table. That will save subtraction.

Check it in Olly... with the dummy pointer, your executable will be bloated by 4 extra bytes :wink

[zemtex]

   call switches[4*ebx-4]

Instead of subtracting 4, add a dummy pointer at index 0 in the jump table. That will save subtraction.

Check it in Olly... with the dummy pointer, your executable will be bloated by 4 extra bytes :wink

4 bytes is nothing, it certainly does not affect speed of code. If you dont like it, add a dummy label before the jmptable address and use that as a reference.  :bdg

To be able to add a dummy label it is important that the dword at the dummy label is actually a dword that is used by the program, so that you dont waste a dword.

or even more complicated, use raw numeric offset instead of using labels.

Problem solved and subtraction is eliminated.