My question is can we avoid the if conditions?

Viewed 177

I have a code condition such as following

for(int i=0;i<Number;i++)
{     
     int* pIn = pInputArr[i];
     int* pOut = pOutputArr[i];
      
     for(int Input_number =0;Input_number<100;Input_number++)
         {
            Some_fun(pIn,pOut );
            if (Input_number % 2 == 0)
            {
               pIn = pOutputArr[i];
               pOut = pInputArr[i];
            }
            else
           {
               pOut =  pOutputArr[i];
               pIn = pInputArr[i];
           }
      }
 }    

I wanted to replace it with a more efficient way in embedded programming since I was told that branch operations are costly in embedded programming. Is there a cleaner way to achieve this using bit operations and without the if conditions?. Also without using any built-in functions such as swap and others.

Based on the odd and even condition I am swapping the role of the buffers that are being as arguments in the Some_func. I checked similar queries in several posts but didn't find them useful. Any suggestions will be highly appreciated.

7 Answers

You don't need to check the evenness if you want to alternate – just swap.

for(int Input_number =0;Input_number<3;Input_number++)
{
    Some_fun(pIn, pOut);
    std::swap(pIn, pOut);
}

What you need is more of a formula that takes the condition value and does something with it. In your scenario, you can create an array with pInputArr[i] and pOutputArr[i], then use the condition value (0 or 1) to make the assignment. I would also prefer bitwise anding with 1 over modulo-checking since it is a single-operation expression:

int arr = {pInputArr[i], pOutputArr[i]};
bool cond = Input_number & 1;
pIn = arr[!cond];
pOut = arr[cond];

In order to go brancheless you would do something like:

int isInputNumberOdd = Input_number % 2; 
pIn  = (pOutputArr[i] * isInputNumberOdd) + (pInputArr[i] * (1 - isInputNumberOdd));
pOut = (pOutputArr[i] * (1 - isInputNumberOdd)) + (pInputArr[i] * isInputNumberOdd);

You'll alway have one term of you addition multuplied by zero, effectivly setting the value to the other one.

You could just loop input_number half the times and call the function twice instead.

for(int i = 0; i < Number; ++i) {     
     for(int Input_number = 0; Input_number < 100 / 2; ++Input_number) {
        Some_fun(pInputArr[i], pOutputArr[i]);
        Some_fun(pOutputArr[i], pInputArr[i]);
    }
}

or if your compiler isn't able to optimize the above to only do the subscripting in each array once:

int* pIn;
int* pOut;
for(int i = 0; i < Number; ++i) {     
     for(int Input_number = 0; Input_number < 100 / 2; ++Input_number) {
        pIn = pInputArr[i];
        pOut = pOutputArr[i];
        Some_fun(pIn, pOut);
        Some_fun(pOut, pIn);
    }
}

No doubt your algorithm can be improved, but you are sweating the small stuff if you are worrying about branch instructions - let the compiler optimiser worry about that and concentrate of efficient algorithms over instruction-level optimisations.

For example you could simply "unroll" the loop:

for( int Input_number = 0;  Input_number < 100; Input_number += 2 )
{
    Some_fun(pIn,pOut );
    pIn = pOutputArr[i];
    pOut = pInputArr[i];
    
    Some_fun(pIn,pOut );
    pOut =  pOutputArr[i];
    pIn = pInputArr[i];
}

Then there is no test for odd/even and if-else. You cannot eliminate branching in computing, the for loop involves branching as does the function call. You can however have efficient algorithms with fewer branches, but more importantly eliminating unnecessary expression evaluation.

Further you can eliminate the assignments:

for( int Input_number = 0;  Input_number < 100; Input_number += 2 )
{
    Some_fun( pInputArr[i], pOutputArr[i] ) ;
    Some_fun( pOutputArr[i], pInputArr[i] ) ;
}

The point is there are two things to avoid in optimisation:

  • Premature optimising - spending time making something faster that is already fast enough
  • Micro-optimisation - worrying about how the compiler will translate your code to machine instructions and second-guessing it.

You have probably attempted both here. What you should concentrate on is intrinsically efficient algorithms and data structures, and leave instruction generation to the compiler.

You could create a 2-element array to hold the pointers you want to swap, and then use the result of your calculation as an index into that array, eg:

int** pArr[2];
int *pIn, *pOut;

for(int i = 0; i < Number; ++i)
{     
    pArr[0] = &pInputArr[i];
    pArr[1] = &pOutputArr[i];

    pIn = *pArr[0];
    pOut = *pArr[1];

    for(int Input_number = 0; Input_number < 100; ++Input_number)
    {
        Some_fun(pIn, pOut);
        bool isEven = (Input_number % 2 == 0);
        pIn = *pArr[isEven];
        pOut = *pArr[!isEven];
    }
}    

Alternatively, since you know the result of the calculation will toggle on each loop iteration, then just get rid of the calculation altogether. eg:

int** pArr[2];
int *pIn, *pOut;
bool isEven;

for(int i = 0; i < Number; ++i)
{     
    pArr[0] = &pInputArr[i];
    pArr[1] = &pOutputArr[i];

    pIn = *pArr[0];
    pOut = *pArr[1];

    isEven = true;

    for(int Input_number = 0; Input_number < 100; ++Input_number)
    {
        Some_fun(pIn, pOut);
        pIn = *pArr[isEven];
        pOut = *pArr[!isEven];
        isEven = !isEven;
    }
}    

Note that in both examples above, I am using a pointer-to-pointer to determine each array element to pass to Some_fun(). This is because your original code re-indexes into the pInputArr[] and pOutputArr[] arrays on each iteration, and it is not clear whether or not Some_fun() can change what those arrays are pointing at on each iteration. If they don't change, then as @molbdnilo suggested, you can just swap the local pointers on each iteration instead, eg:

for(int i = 0; i < Number; ++i)
{     
    int *pIn = pInputArr[i];
    int *pOut = pOutputArr[i];

    for(int Input_number = 0; Input_number < 100; ++Input_number)
    {
        Some_fun(pIn, pOut);

        int *pTmp = pIn;
        pIn = pOut;
        pOut = pTmp;
    }
}    

If your sure that you will be running 100 times, and that each some_fun() should alternate the arguments, you can ditch the if statements altogether,

for(int Input_number = 0; Input_number < 50; Input_number++)
{
    Some_fun(pIn, pOut);
    Some_fun(pOut, pIn);
}

This way you don't need to swap the two or use if statements.

Related