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.
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.
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.
Here is a very simple example. It is definitely smaller than a huge .if .elseif .endif chain, but less flexible of course...
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
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?
Quote from: zemtex on January 14, 2011, 04:50:17 PM
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.
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?
what about:
and eax,0ffffh
jmp JmpTable[4*eax]
:bg
I wanted to do that in the first place but I need to conserve the H.O word of eax for the call destination.
Quote from: zemtex on January 14, 2011, 05:42:29 PM
I need to conserve the H.O word of eax for the call destination.
a hard problem to solve :bdg
.......................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.
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]
Quote from: jj2007 on January 14, 2011, 05:01:15 PM
call switches[4*ebx-4]
Instead of subtracting 4, add a dummy pointer at index 0 in the jump table. That will save subtraction.
Quote from: zemtex on January 17, 2011, 11:15:04 AM
Quote from: jj2007 on January 14, 2011, 05:01:15 PM
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
Quote from: jj2007 on January 17, 2011, 11:32:04 AM
Quote from: zemtex on January 17, 2011, 11:15:04 AM
Quote from: jj2007 on January 14, 2011, 05:01:15 PM
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.
A much more delicate way to do it is to use (OFFSET JmpTable-4) so that the calculation is done at assembly time. When you use [-4] in brackets, the calculation is done at execution time and will waste cycles.
This will calculate at runtime: call switches[4*ebx-4]
This (The subtraction part) will calculate at assembly time: lea ecx, [4*ecx+(OFFSET JmpTable-4)]
It is a much more delicate way to do it.
EDIT: I tried it in olly, it seems like your solution calculated at assembly time after all. Then it would be the same.
FF149D FC3FEC00 CALL DWORD PTR DS:[EBX*4+0EC3FFC]
and here is mine:
8D0C8D FC3FEC00 LEA ECX,[ECX*4+0EC3FFC]
Can never be too careful :P
Quote from: zemtex on January 17, 2011, 11:51:35 AM
EDIT: I tried it in olly, it seems like your solution calculated at assembly time after all. Then it would be the same.
Yes indeed :bg