Minimize function selection and function call overhead?

Question

I have a large array (image) and I need to do many small configurable computations on that data. I'll post an example here. NOTE: This is not the actual problem, but a minimal / hopefully illustrative example of what I need to do.

// different functions that can be called based on the configuration
float func1( float* a )
{
    return (*a) * (*a);
}

float func2( float* a )
{
    return (*a) + (*a);
}

float func3( float* a )
{
    return 2 * (*a) * (*a);
}

// my data
float* data = new float[1024*1024];

// function that manages the configurations
int main(  )
{
    int param1 = 0;
    int param2 = 1;

    for ( int k = 0; k < 1024*1024; k++ )
    {
        if ( param1 == 2 && param2 == 0 )
            data[k] = func1( data + k );
        else if ( param1 == 1 && param2 == 1 )
            data[k] = func2( data + k );            
        else if ( param1 == 0 && param2 == 1 )
            data[k] = func3( data + k );
        else
            continue;

    }
}

In my code, it does not make sense to put the loop inside of each function.

However, param1 and param2 remain constant during the loop and they are known at compile time.

Is there a way to remove the influence of the if/elseif statements?

Mark the variables as `constexpr` (or `const`) and the compiler should be able to optimize away the checks and only call the one function. Look at the generated assembly code if you're unsure. Also, if a function is not called, then there's no overhead. And if the functions you call are small, mark them as `inline` for possibly more optimization alternatives. And mark the arguments as `const` if you do not modify them. And why pass the arguments as pointers? The indirection will add overhead. — Some programmer dude, Mar 19 '15 at 14:30
@JoachimPileborg how do you look at the assembly code? What file is it and how to understand it? — The Vivandiere, Mar 19 '15 at 14:32
Just about all compilers have options to stop and generate assembly code instead of binary object files. The option depends on the compiler of course, on GCC and Clang it's `-S`. — Some programmer dude, Mar 19 '15 at 14:35
would really like to know how "smell configurable computations" are done ;) — Paul Evans, Mar 19 '15 at 14:36
@PaulEvans Cant a man indulge his olfactory senses? What has the world come to these days! ;) — The Vivandiere, Mar 19 '15 at 14:38
@PaulEvans: I meant "smell-configurable computations" :P. It's corrected in the question — S.H, Mar 19 '15 at 15:15

score 2 · Answer 1 · edited May 23 '17 at 12:29

You can move your if-else statement that selects appropriate function to use out of the loop, thus getting to:

#include <functional>
// different functions that can be called based on the configuration
float func1( float* a )
{
    return (*a) * (*a);
}

float func2( float* a )
{
    return (*a) + (*a);
}

float func3( float* a )
{
    return 2 * (*a) * (*a);
}

// my data
float* data = new float[1024*1024];

// function that manages the configurations
int main(  )
{
    int param1 = 0;
    int param2 = 1;

    std::function< float( float* )> functionToUse = nullptr;

    if ( param1 == 2 && param2 == 0 )
        functionToUse = std::function<float(float*)>(func1);
    else if ( param1 == 1 && param2 == 1 )
        functionToUse = std::function<float(float*)>(func2);            
    else if ( param1 == 0 && param2 == 1 )
        functionToUse = std::function<float(float*)>(func3);

    if(functionToUse){
        for ( int k = 0; k < 1024*1024; k++ )
        {
            data[k] = functionToUse( data + k );
        }    
    }
}

As to choosing the function to use during compilation time I'd suggest checking out this question: if/else at compile time?

Also this question might be of interest: Is cutting if statements by using function pointers going to be more efficient?

Isn't this slow due to the function pointer that needs to be resolved at every call? — S.H, Mar 19 '15 at 15:18
Please do read the second link (the one about cutting if statements with function pointers). 'Slow' is a very broad and very inaccurate club of a term - to determine slowness you need to profile. Long story short - modern compilers are very very good at optimization and branching prediction is one of those areas that's optimized very well. It may be more efficient to use if-else inside the loop. But it might as well be not. — pdeschain, Mar 19 '15 at 15:28

Mark B · Answer 2 · 2015-03-20T14:38:07.480

2

As long as the parameters are const OR the compiler can 100% determine that they variables aren't aliased and thus won't change (harder for the compiler) I would completely expect the optimizer to totally remove the runtime branch and do all the work at compile time.

If however you don't prefer to rely on the optimizer you can use templates:

template <int c1, int c2>
float func(float* a)
{
    // No-op.
}

template <>
float func<2, 0>(float* a)
{
    return (*a) * (*a);
}

template <>
float func<1, 1>(float* a)
{
    return (*a) + (*a);
}

template <>
float func<0, 1>(float* a)
{
    return 2 * (*a) * (*a);
}

int main()
{
    const int param1 = 0;
    const int param2 = 1;

    for ( int k = 0; k < 1024*1024; k++ )
    {
        func<param1, param2>(<float ptr>);
    }
}

edited Mar 20 '15 at 14:38

answered Mar 19 '15 at 17:55

Mark B

95,107
10
109
188

In that case, how does your implementation of func and its specializations look like (if they shall be in accordance with my example)? – S.H Mar 20 '15 at 08:42
template<> float func<0,0>( float* a ) { return (*a) * (*a); } something like that – pdeschain Mar 20 '15 at 09:08

stryku · Answer 3 · 2015-03-19T14:58:09.583

Maybe something like this

#include <iostream>
#include <map>
#include <functional>
#include <utility>

typedef std::pair<size_t, size_t> pair;
typedef std::map< pair, std::function<float( float* )>> map;

// different functions that can be called based on the configuration
float func1( float* a )
{
    return ( *a ) * ( *a );
}

float func2( float* a )
{
    return ( *a ) + ( *a );
}

float func3( float* a )
{
    return 2 * ( *a ) * ( *a );
}

// my data
float* data = new float[1024 * 1024];

void init( map &myMap )
{
    myMap.insert( pair, std::function<float( float* )>>
                ( pair( 2, 0 ), std::function< float( float* )>( func1 ) ) );
    myMap.insert( pair, std::function<float( float* )>>
                ( pair( 1, 1 ), std::function< float( float* )>( func2 ) ) );
    myMap.insert( pair, std::function<float( float* )>>
                ( pair( 0, 2 ), std::function< float( float* )>( func3 ) ) );
}

// function that manages the configurations
int main( )
{
    int param1 = 0;
    int param2 = 1;

    map myMap;

    init( myMap );

    for( int k = 0; k < 1024 * 1024; k++ )
    {
        data[k] = myMap[pair( param1, param2 )]( data + k );
    }
}

in init the map gets filled with pairs of ints corresponding to some function and in the loop the function is looked up in map gets executed. It is a poor solution performance-wise - the map is totally redundant as params are known during compilation, it requires pair allocation every iteration of the loop and map lookup (which is O(log(n)) for std::map. — pdeschain, Mar 20 '15 at 09:06

Minimize function selection and function call overhead?

3 Answers3