www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Fast switch statement

reply "Steve Kucera" <stevenkucera gmail.com> writes:
Hi,

I am using DMD 2.062 on Windows 7 64-bit.

I am writing performance critical functions that need switch 
statements to use an indirect jump table... current I'm analysing 
the assembly dump, and the code is compiled to nested ifs 
instead. This happens with switch and final switch. Is there any 
way to force the compiler to use a jump table?

Steve
Apr 03 2013
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, April 04, 2013 03:06:44 Steve Kucera wrote:

 Hi,
 
 I am using DMD 2.062 on Windows 7 64-bit.
 
 I am writing performance critical functions that need switch
 statements to use an indirect jump table... current I'm analysing
 the assembly dump, and the code is compiled to nested ifs
 instead. This happens with switch and final switch. Is there any
 way to force the compiler to use a jump table?


If you have performance-critical code, then use gdc or ldc (probably ldc, 
since you're on Windows). dmd's optimizer is nowhere near as good as theirs 
are. dmd is very well optimized for compiling quickly, but it fails in 
optimizing the code that it generates. It's okay at it, but it really doesn't 
compare to gdc or ldc (which use gcc and LLVM as their backends respectively). 
And dmd doesn't have much in the way of switches which affect optimization, so 
if neither -O, -inline, or -release gets you jump tables, then I expect that 
there's no way that dmd is going to give you jump tables.

- Jonathan M Davis
Apr 03 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Steve Kucera:


 I am using DMD 2.062 on Windows 7 64-bit.

 I am writing performance critical functions that need switch 
 statements to use an indirect jump table... current I'm 
 analysing the assembly dump, and the code is compiled to nested 
 ifs instead. This happens with switch and final switch. Is 
 there any way to force the compiler to use a jump table?


What kind of switch do you have? Are you switching on strings?

Here I am not seeing nested ifs, this is efficient enough:


import core.stdc.stdio: puts;
void main(string[] args) {
     switch (args.length) {
         case 0: puts("0"); break;
         case 1: puts("1"); break;
         case 2: puts("2"); break;
         case 3: puts("3"); break;
         default: puts("default"); break;
     }
}




main:
L0:     push    EAX
         push    EBX
         mov EBX,0Ch[ESP]
         cmp EBX,3
         push    ESI
         ja  L53
         jmp dword ptr FLAT:_DATA[018h][EBX*4]

         mov ESI,offset FLAT:_DATA
         push    ESI
         call    near ptr _puts
         add ESP,4
         jmp short   L61

         mov EDX,offset FLAT:_DATA[4]
         push    EDX
         call    near ptr _puts
         add ESP,4
         jmp short   L61

         mov ECX,offset FLAT:_DATA[8]
         push    ECX
         call    near ptr _puts
         add ESP,4
         jmp short   L61

         mov EAX,offset FLAT:_DATA[0Ch]
         push    EAX
         call    near ptr _puts
         add ESP,4
         jmp short   L61

L53:        mov EBX,offset FLAT:_DATA[010h]
         push    EBX
         call    near ptr _puts
         add ESP,4

L61:        pop ESI
         xor EAX,EAX
         pop EBX
         pop ECX
         ret


Bye,
bearophile
Apr 03 2013
prev sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 4 April 2013 at 01:06:45 UTC, Steve Kucera wrote:

 Hi,

 I am using DMD 2.062 on Windows 7 64-bit.

 I am writing performance critical functions that need switch 
 statements to use an indirect jump table... current I'm 
 analysing the assembly dump, and the code is compiled to nested 
 ifs instead. This happens with switch and final switch. Is 
 there any way to force the compiler to use a jump table?

 Steve


Ldc or gdc may be able to do this for you if dmd cannot.

Other than that, the inline asm in dmd is easy enough to use.
Apr 04 2013
next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 4 April 2013 at 09:51:15 UTC, John Colvin wrote:

 On Thursday, 4 April 2013 at 01:06:45 UTC, Steve Kucera wrote:

 Hi,

 I am using DMD 2.062 on Windows 7 64-bit.

 I am writing performance critical functions that need switch 
 statements to use an indirect jump table... current I'm 
 analysing the assembly dump, and the code is compiled to 
 nested ifs instead. This happens with switch and final switch. 
 Is there any way to force the compiler to use a jump table?

 Steve


 Ldc or gdc may be able to do this for you if dmd cannot.

 Other than that, the inline asm in dmd is easy enough to use.


Sorry, inline asm in D, not just dmd.
Apr 04 2013
prev sibling parent reply "Steven Kucera" <stevenkucera gmail.com> writes:
Hi,

OK thanks guys. LDC compiled a jump table. The code runs ~15% 
faster than dmd2, even though checking the ASM it did not inline 
functions it could have, and core.bitop.bsf compiled to a 
function call instead of an ASM instruction.

Can you force a function to be inline, and/or make core.bitop.bsf 
an instruction with ldc? (in the latter case, maybe the last 
resort is to dip into assembly?)

Steve

On Thursday, 4 April 2013 at 09:51:15 UTC, John Colvin wrote:

 On Thursday, 4 April 2013 at 01:06:45 UTC, Steve Kucera wrote:

 Hi,

 I am using DMD 2.062 on Windows 7 64-bit.

 I am writing performance critical functions that need switch 
 statements to use an indirect jump table... current I'm 
 analysing the assembly dump, and the code is compiled to 
 nested ifs instead. This happens with switch and final switch. 
 Is there any way to force the compiler to use a jump table?

 Steve


 Ldc or gdc may be able to do this for you if dmd cannot.

 Other than that, the inline asm in dmd is easy enough to use.
Apr 05 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Steven Kucera:


 and core.bitop.bsf compiled to a function call instead of an 
 ASM instruction.


It used to be an intrinsics. I don't know if in the meantime
things have changed for LDC2.



 Can you force a function to be inline, and/or make 
 core.bitop.bsf an instruction with ldc?


In LDC there are two different ways to inline asm, see the LDC
docs.

Bye,
bearophile
Apr 05 2013