A critical cycle containing a lot of "ifs" whose output is constant: how to save on state tests?

Question

I have a critical loop in my code with this form:

int myloop(int a, .....){ /* some stuff */ // Critical loop while(...){ /* Some Stuff */ if(a == 1){ // ..... } else if(a == 2){ // ..... } else if(a == 3){ // ..... } else{ // .... } } } 

Since the cycle never touches the value of “a”, the adopted branch will never change, but since this cycle is really heavy, you will need to repeatedly check the value of “a”, which is completely unnecessary. It’s probably best to duplicate the loop so that the “if” can be tested before the start of the loop, but that would mean copying a lot of materials common to both situations and leading to very ugly code ...

Is it possible to request GCC / g ++ to duplicate this code when compiling it? Or any other trick to avoid checking the value so many times?

Thank you for your help!

Nathann

Answer 1

One common way to do this is:

 // make function implementation inline... static inline int myloop_inline(int a, .....){ /* some stuff */ // Critical loop while(...){ /* Some Stuff */ if(a == 1){ // ..... } else if(a == 2){ // ..... } else if(a == 3){ // ..... } else{ // .... } } } // wrapper function which calls myloop_inline with hard-coded values of a int myloop(int a, .....){ { switch (a) { // expand inline function for all performance-critical values of a... case 1: myloop_inline(1); break; case 2: myloop_inline(2); break; case 3: myloop_inline(3); break; ... // for any values of a for which the function is not performance-critical // we can just use a default case... default: myloop_inline(a); break; } } 

Note that since a is passed as a literal constant when myloop_inline() is called the form myloop() , the compiler can optimize all unnecessary tests and dead code when it extends the built-in function.

You might want to take steps to ensure that myloop_inline() indeed embeddable, this includes compilation with optimizations enabled (e.g. -O3 ), and in the case of, for example, gcc, you can add __attribute__ ((always_inline)) .

Answer 2

First of all, you can use the switch here:

 switch(a) { case 0: // handle a==0 break; case 1: // handle a==1 break; default: // handle all other cases } 

This may allow the compiler to produce faster code, i.e. Perform one calculated leap, not multiple checks against a .

this would mean copying a multitude of things common to both situations.

Refactor ! How about adding common code to a separate function, maybe declare it inline and hope the compiler follows the prompt? The inlining function is a good way to allow the compiler to duplicate code (the other two methods are templates and a preprocessor, both of which are obviously not suitable here).

 inline void sharedStuff() {...} int myloop(int a, .....){ /* some stuff */ if (a==1) { while(...){ // code specific to a==1 // do shared stuff sharedStuff(); } } else if ... } 

Of course, it depends on what you do in your cycle, but you should get the basic principle.

And last but not least: profile . Check if the loop is really a performance bottleneck. Look at the generated machine code. Most likely, the compiler already uses most of the proposed optimizations.

Answer 3

You can use the switch :

 while(...) { switch(a) { case 1: // do what you want break; case 2: // do what you want break; case x: // do what you want break; default: //if not matching any previous.. } } 

Answer 4

I would suggest passing "a" as a template parameter, that is

 template< int a > int myloop(.....) { if( a==1 ) { ... } } 

Thus, it will be optimized correctly.

However, you will not be able to pass the variable as a template parameter, so in another place you have to put this switch.

 switch(a) { case 1: myloop<1>(...); break; ... } 

Answer 5

How to define a function that does everything that happens inside a while loop and define it inline ? Then move the while inside each if and call the function there. This will do exactly what you want.

Answer 6

How to make each separate function, and then have a pointer to this function?

 void func_a() { // ... } void func_b() { // ... } int myloop(int a, ...) { void (*func)(); if (a == 1) { func = &func_a; } else if (a == 2) { func = &func_b; } ... while (1) { /* Some stuff */ func(); } } 

Answer 7

 int myloop(int a, ...){ if(a == 1){ myloop1(a, ...); } else if(a == 2){ myloop2(a, ...); } else if(a == 3){ myloop3(a, ...); } else{ myloopelse(a, ...); } } myloop#(int a, ...){ SomeStuffAboveLoop(...) while(...){ SomeStuffInsideLoop(...) //Do what you want for the appropriate # } } 

You can also change the if block to a switch that shows many other answers.

Answer 8

Are the operations performed under each condition the same? In these situations, I usually use if statements to set the value of key objects or pointers to objects, and then use these values ​​in the rest of the code ... basically, make the most of indirect use.

dim x as an object
dim y as a string
If (a == 1), then x = foo.object
y = bar.string
elseif (a == 2)
x = yuk.object
y = yo.string
end if while ... dofunction (x, y)
end rather

But if your operations are very different from each other, then this is already ugly, and you can create several cycles to save clock cycles ...

Answer 9

You can use an array with a pointer to functions if your conditions are mostly contiguous.

 typedef void ( *case_func )( type1 param1, type2 param2 ); void case_func1( type1 param1, type2 param2 ); void case_func2( type1 param1, type2 param2 ); void case_func3( type1 param1, type2 param2 ); void case_func5( type1 param1, type2 param2 ); case_func func_array[] = { &case_func1, &case_func2, &case_func3, NULL, // Just a place holder, for non-contiguous values. &case_func5 }; int myloop(int a, .....){ /* some stuff */ // Critical loop while(...) { if ( func_array[ a ] && a < sizeof( func_array ) ) func_array[ a ]( .... ); } } 

If you can be sure that you will not have holes in your array, and a will never be outside the boundaries of the array, you can omit if ( func_array[ a ] && a < sizeof( func_array ) ) , reducing the code to any comparisons in general.

In any case, this approach may be a little clearer and may be worth it even if it does not give a big gain in performance.

Answer 10

you could also consider moving the loop inside the conditions like this. This damages the size of the code for efficient execution.

 if (a == 0) { while (...) { /* some stuff */ // 0 stuff } } else if (a == 2) { while (...) { /* some stuff */ // 2 stuff } } else if (a == 3) { .... }