Avoiding conditional expressions and function calls inside a loop

Question

I have a code that looks like this:

void function(int parameter) { for( ... ) // a big loop { double a = ...; for( ... ) // a big loop { double b = ...; double value; if(parameter == 1) value = some_math_expression_1(a, b); else if(parameter == 2) value = some_math_expression_2(a, b); ... } } } 

The idea is that depending on the parameter, I want to apply a mathematical expression to a and b . This function is performed many times and should be fast, and I wonder if these conditional branches can introduce overheads at each iteration, which I could save.

Right now, I wrote the code as follows:

 void function(int parameter) { if(parameter == 1) function1(); else if(parameter == 2) function2(); else ... } 

So, I can apply the math expression directly if I repeat the code in each functionX() . The obvious problem is that when I want to change part of the code, I have to do this several times (now I have about 10 mathematical expressions).

What approach can be used to avoid overhead in function ?

What if I pass a pointer to some_math_expression_X function on function (I would change the conventions for invocations functions)?

What if I encode the entire function as a macro (uf) and set the math expression as a parameter?

What if I use a template and pass a mathematical expression as a pointer to an inline function (is this possible)?

EDIT : Thanks for your answers. I know that I can use the methods you suggest (pointers to / an array of functions or rely on a branch predictor). However, do you have any idea what would be better in terms of preventing overhead? The math expressions are pretty simple (something like a*b ), and in addition to long loops, function also called many times (branch predictions “survive” between calls?).

Answer 1

You can convert the function to a template:

 void functionT<int PARAMETER>() { for( ... ) // a big loop { double a = ...; for( ... ) // a big loop { double b = ...; double value; if(PARAMETER == 1) //Constant condition!!! value = some_math_expression_1(a, b); else if(PARAMETER == 2) //Constant condition!!! value = some_math_expression_2(a, b); ... } } } 

Since the conditions are always true or always false, the compiler will optimize the condition tree and leave only a real mathematical expression. No branches and no function calls!

Now you can use it only with constant parameters:

 functionT<1>(); 

But not with variables:

 int x = 1; functionT<x>(); //Error 

If you need it, you can make a wrapper:

 void function(int parameter) { switch (parameter) { case 1: functionT<1>(); break; case 2: functionT<2>(); break; } } 

Answer 2

Do not worry. Modern processors have branch predictors, and they will correctly predict the branch.

Answer 3

You can set up a constant array of function pointers and call the function associated with parameter .

But if the math expressions are pretty small, the switch () statement can be even faster.

 switch (parameter) { case 1: value = math expression 1; break; case 2: ... } 

Answer 4

Firstly, I would always say that you need to check / measure how long this process takes right now, because, as always, it can be premature optimization, and you can find out that this is not the part of your code that long time.

But assuming you measured and found that this is a bottleneck in your code, there are a few things that I would do.

First, the thing that is going to kill you the most (assuming your math functions are pretty simple) is branch prediction, as you said. Therefore, to get rid of branching, I would create an array of function pointers and instead of doing

 if(parameter == 1) function1(); if... 

You can simply do:

 array_of_functions[parameter](); 

This will save you from all industry predicates and significantly increase throughput because your pipeline will not be cleaned. The compiler should also be able to embed functions.

Answer 5

It depends on many things, but in general, you might want to make sure that most of the time either the first or second function is executed. This will make the modern processor do this pretty quickly (see Why is it faster to process a sorted array than an unsorted array? ).

You can use array pointers and functions, but this may not speed up, you should try. You can use http://www.boost.org/doc/libs/1_54_0/doc/html/function/tutorial.html#idp59212272 to help, but you don't need static functions.

Answer 6

I think one of the most efficient ways to do this is to create an array of function pointers, and then you can directly pass a function pointer, not just a parameter. This will save any overhead that you would incur when using the if / switch statement in a nested loop.

As an example:

 double expression_0(double a, double b) {...}; double expression_1(double a, double b) {...}; void function(double (*expression)(double, double)) { for (...) { ... double a = ...; for (...) { double b = ...; double result = (*expression)(a, b); } } } int main() { double (*fpointers[2]) (double, double); fpointers[0] = expression_0; fpointers[1] = expression_1; int parameter = ...; function(fpointers[parameter]); } 

Answer 7

If all your functions have the same signature, the simplest thing will be the following:

 void function(int parameter) { double ( *fn )( double, double ); switch( parameter ) { case 1: fn = &some_math_expression_1; break; case 2: fn = &some_math_expression_2; break; ... } for( ... ) // a big loop { double a = ...; for( ... ) // a big loop { double b = ...; double value = fn( a, b ); ... } } }