exhaustive switch bound checking

See the program fragment below.
I have tried it on VC8 x64.

//--------------------------------------------
extern unsigned char fetch_byte();

void dispatch() {
while(true) {
switch(fetch_byte()) {
case 0: ...; break;
case 1: ...; break;
...
case 255: ...; break;
}
}
}
//---------------------------------------------

VC generates a jump table for the switch statement. The case is
exhaustive with respect to the unsigned char type. However, VC generates
a bound check before indexing in the jump table:
movzx r11d, al
cmp r11d, 255 ; 000000ffH
ja SHORT $LL260@dispatch_c
mov edx, DWORD PTR $LN776@dispatch_c[rdi+r11*4]
add rdx, rdi
jmp rdx
The first three lines here can be ommitted.

The question is: how do I make the compiler to omit the checks?

Note, that the same problem appears with an exhausinve switch for an
enum type.

Thanks in advance,
Artem

Alexander
Fri Jun 23 08:43:43 CDT 2006

Does it pose a particular problem? Does it create a measured performance
bottleneck?

"Artem Alimarine" <artem@emulatorsinternational.com> wrote in message
news:1151066484.41369.0@despina.uk.clara.net...
> See the program fragment below.
> I have tried it on VC8 x64.
>
> //--------------------------------------------
> extern unsigned char fetch_byte();
>
> void dispatch() {
> while(true) {
> switch(fetch_byte()) {
> case 0: ...; break;
> case 1: ...; break;
> ...
> case 255: ...; break;
> }
> }
> }
> //---------------------------------------------
>
> VC generates a jump table for the switch statement. The case is exhaustive
> with respect to the unsigned char type. However, VC generates a bound
> check before indexing in the jump table:
> movzx r11d, al
> cmp r11d, 255 ; 000000ffH
> ja SHORT $LL260@dispatch_c
> mov edx, DWORD PTR $LN776@dispatch_c[rdi+r11*4]
> add rdx, rdi
> jmp rdx
> The first three lines here can be ommitted.
>
> The question is: how do I make the compiler to omit the checks?
>
> Note, that the same problem appears with an exhausinve switch for an enum
> type.
>
> Thanks in advance,
> Artem

Tom
Fri Jun 23 09:04:13 CDT 2006

Artem Alimarine wrote:
> See the program fragment below.
> I have tried it on VC8 x64.
>
> //--------------------------------------------
> extern unsigned char fetch_byte();
>
> void dispatch() {
> while(true) {
> switch(fetch_byte()) {
> case 0: ...; break;
> case 1: ...; break;
> ...
> case 255: ...; break;
> }
> }
> }
> //---------------------------------------------
>
> VC generates a jump table for the switch statement. The case is
> exhaustive with respect to the unsigned char type. However, VC generates
> a bound check before indexing in the jump table:
> movzx r11d, al
> cmp r11d, 255 ; 000000ffH
> ja SHORT $LL260@dispatch_c
> mov edx, DWORD PTR $LN776@dispatch_c[rdi+r11*4]
> add rdx, rdi
> jmp rdx
> The first three lines here can be ommitted.
>
> The question is: how do I make the compiler to omit the checks?

You could try playing around with "default:", if the checks are really
hurting your application's performance.

> Note, that the same problem appears with an exhausinve switch for an
> enum type.

Note that such a switch might need 2^32 entries! Valid values for an
enum aren't just the defined enum constants, but all values that fit in
the enum.

Tom

Doug
Fri Jun 23 12:34:52 CDT 2006

On Fri, 23 Jun 2006 19:13:18 +0200, Artem Alimarine
<artem@emulatorsinternational.com> wrote:

>Yes, unfortunately they are hurting the performance and the performance
>is important here.
>
>The problem is that the compiler basically inserts a en empty default
>branch in the program. And I do not see how I can use 'default:' to
>avoid 'default:'.
>
>I just tried the things with GCC 3.4.4 and 4.1. The 3.4.4. produces a
>similar code to that of VC. The 4.1 compiler does not generate the check
>in the case of exhaustive check.

Try this in VC++:

default :
__assume(0);

--
Doug Harrison
Visual C++ MVP

Artem
Fri Jun 23 13:09:38 CDT 2006

> Try this in VC++:
>
> default :
> __assume(0);
>

Thank you! This works!

Alexander
Sat Jun 24 19:30:59 CDT 2006

I suppose you did profiling to make sure that single nanosecond (yes, one
nanosecond) to execute two unnecessary instructions does bring significant
performance hit?

"Artem Alimarine" <artem@emulatorsinternational.com> wrote in message
news:1151081813.94139.0@demeter.uk.clara.net...
> Alexander Grigoriev wrote:
>> Does it pose a particular problem? Does it create a measured performance
>> bottleneck?
>>
>
> Yes, this dispatch is done in a loop. This is the most performance
> critical part of the application. So, it will slowdown the performance
> noticably. I expect it can eat several percents of performance. In my case
> performance is very it is important.
>
> This problem is common for interpreter-like applications that read run a
> loop wher an opcode is read and chosen what to do using a switch
> statement. Normally the opcode switch is exhaustive because you handle all
> possible opcodes. This check is then a waste of time for every step of the
> interpreter.

Alexander
Sat Jun 24 19:31:42 CDT 2006

How much better is performance now?

"Artem Alimarine" <alimarine@zonnet.nl> wrote in message
news:31629$449c2e65$513b8192$26890@news.versatel.net...
>> Try this in VC++:
>>
>> default :
>> __assume(0);
>
> Thank you! This works!

adebaene
Mon Jun 26 06:19:17 CDT 2006


Artem Alimarine a =E9crit :

> Alexander Grigoriev wrote:
> > Does it pose a particular problem? Does it create a measured performance
> > bottleneck?
> >
>
> Yes, this dispatch is done in a loop. This is the most performance
> critical part of the application. So, it will slowdown the performance
> noticably. I expect it can eat several percents of performance. In my
> case performance is very it is important.

You "expect" but you haven't done any measurement, right? "Premature
optimization is the root of all evil". Do not EVER optimize code
without a factual proof that it is worth optimizing....

Just my 2 cents...

Arnaud
MVP - VC

Artem
Mon Jun 26 13:04:54 CDT 2006

Alexander Grigoriev wrote:
> I suppose you did profiling to make sure that single nanosecond (yes, one
> nanosecond) to execute two unnecessary instructions does bring significant
> performance hit?
>

Unfortunately, I do not have the application yet to profile. Currently
the project is in a prototyping stage. I estimate an average path
through the case statement in the cycle is about 50-100 instructions.
This means 2-4 percents improvement for just a small inconvenience.

This is important because it is the main cycle of an interpreter, not a
switch statement in a windows message dispatch function. If optmizations
and performance tuning are ever needed, this is such a case.

You do not need to step on a rake to know that it will hurt.

At this point I was experimenting to choose between a function pointer
table and a jump table generated by a switch.

Artem
Mon Jun 26 13:07:45 CDT 2006

adebaene@club-internet.fr wrote:
> You "expect" but you haven't done any measurement, right? "Premature
> optimization is the root of all evil". Do not EVER optimize code
> without a factual proof that it is worth optimizing....

Yes, this is definitely true. However, it is equally bad to delay the
optmizations if you know they will be needed in this place. Hear the
subject of optimizations is the main loop of an interpreter. You do not
have to think a long time before you know that this thing is performance
critical.

Jerry
Mon Jun 26 14:19:59 CDT 2006

In article <51560$44a02278$513b8192$10266@news.versatel.net>,
alimarine@zonnet.nl says...
> adebaene@club-internet.fr wrote:

[ ... ]

> > Do not EVER optimize code
> > without a factual proof that it is worth optimizing....
>
> Yes, this is definitely true.

It's not definitely true -- rather, it's usually reasonable.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Artem
Tue Jun 27 12:24:03 CDT 2006

Alexander Grigoriev wrote:
> How much better is performance now?
>

It is about 2% on the prototype.