Re: Removing bound checks from a switch statement

Re: Removing bound checks from a switch statement

[Henrik Mannerström]

Hello,

Below is a short program that illustrates my problem. The variable R  
is of type enum reactions so the compiler should know that it does not  
need to check it's value in the switch statement on line 10. The  
assembler output shows that a check is nevertheless inserted. %ebx  
contains the value or R and .L9 the address of the jump table.  
Compiled with g++ -S -g -dA -O2 swloop.cc on a X86_64 machine.

Should not the type system ensure that R is within bounds?

Regards,
Henrik

<from the asm-output>
# swloop.cc:10
.loc 1 10 0
cmpl	$5, %ebx
ja	.L2
# basic block 4
mov	%ebx, %eax
jmp	*.L9(,%rax,8)
</from the asm-output>

enum reactions {R0 = 0, R1, R2, R3, R4, R5};

#include <cstdio>

int main() {
   const enum reactions next_reaction[] = {R1, R2, R3, R4, R5};
   enum reactions R = R0;

   while (R != R5) {
     switch (R) { /* This is line 10 */
     case R0:
       printf("R0\n");
       break;
     case R1:
       printf("R1\n");
       break;
     case R2:
       printf("R2\n");
       break;
     case R3:
       printf("R3\n");
       break;
     case R4:
       printf("R4\n");
       break;
     case R5:
       printf("R5\n");
       break;
     }
     R = next_reaction[R];
   }
}

Re: Removing bound checks from a switch statement

[Jeff Law]

On 02/17/10 10:55, Henrik Mannerström wrote:
> Hello,
>
> Below is a short program that illustrates my problem. The variable R 
> is of type enum reactions so the compiler should know that it does not 
> need to check it's value in the switch statement on line 10. The 
> assembler output shows that a check is nevertheless inserted. %ebx 
> contains the value or R and .L9 the address of the jump table. 
> Compiled with g++ -S -g -dA -O2 swloop.cc on a X86_64 machine.
>
> Should not the type system ensure that R is within bounds?
No.  The standard allows defining values that are not part of the 
enumeration.

Jeff

Re: Removing bound checks from a switch statement

[Henrik Mannerström]

Quoting "Christoph Groth" <cwg@falma.de>:

> I do not know how to solve the problem you described, but another way of
> speeding up a switch statement might be using the GCC extension "Labels
> as Values".
>
> http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

Thank you very much! This was exactly what I was looking for.

I made a completely non-standard, spaghettisized version of the  
program and luckily it did not run any faster than the switch-based  
one, so I can stick to my -ansi option. The earlier reported speedup  
was probably just an outlier in the performance test.

Many thanks! Now I can put this behind me and work on other aspects.
Henrik

Re: Removing bound checks from a switch statement

[Christoph Groth]

I do not know how to solve the problem you described, but another way of
speeding up a switch statement might be using the GCC extension "Labels
as Values".

http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

You can retain compatibility to standard C by writing two versions of
the code, one which uses GCC extension and which does not.

Your reaction_t would be an enum for standard C and a void * for gcc.

I am using this trick for my python-like Generator class with iterator
interface (http://vc.falma.de/cfc/tree/cfc/generator.hh)

Would this help?

Christoph

Removing bound checks from a switch statement

[Henrik Mannerström]

Hello,

I have an event driven simulator that uses a switch statement for  
executing the next event. Currently, the loop is so tight that  
removing the bound checks from the switch increased performance by  
10%. This I observed halfway in converting from ints to enums for the  
reactions. However, there were bugs at that point and with these  
removed the checks were there again (I verified this by looking at the  
asm).

The code is too big for this post, but I define the reaction type as follows:
enum reaction_T {RDEF=0, R1=1, R2=2, R3=3, R4=4, R5=5, R6=6};
The program has a const array of the above type to store the  
dependency graph (that is why I define the values of the enums) and  
two switch statements that lists all the cases.

The program compiles without warnings on a x86_64: g++ (Ubuntu  
4.3.2-1ubuntu12) 4.3.2 with
g++ -Wall -Winline -ftree-vectorizer-verbose=0 -pedantic -ansi -O3  
-mtune=native -march=native -fno-strict-aliasing -lm -c sim.cc

The program seems to by type safe so the bounds checks should be  
removed. Is there any way enforce the removal of the bound checks or  
some compiler switch that could give a hint of what is wrong?

Best regards,
Henrik Mannerström