How to create branchless code for this piece of code?

Admin 1
Viewed 1865

I need to generate branchless code for the if statement in the inner loop if(i != j). I am confused how to generate branchless code.

  for (int i = start; i < n; i++)
  {
        results[i] = 999;
        for (int j = 0; j < n; j++)
        {
            if (i != j)
            {
                d = myfunction(x, y, i, j);
                if (d < results[i])
                    results[i] = d;
            }
        }
    }
compiler-optimization micro-optimization computer-science cpu-architecture compiler-construction
2 Answers

A comparison returns 0 (false) or 1 (true) in C++. So you can convert the innermost condition as follows:

int condition = d < results[i] 
results[i] = d * condition + results[i] * !condition;

To skip over i in the inner loop, just add one to the arg at i and beyond:

...
for (int j = 0; j < n - 1; j++) {
    d = myfunction(x, y, i, j + (j >= i));
    int condition = d < results[i] 
    results[i] = d * condition + results[i] * !condition;
}
...

An alternative with fewer comparisons would be to split the inner loop into two loops: 

for (int j = 0; j < i; j++) {
   ...
}
for (int j = i + i; j < n; j++) {
   ...
}

Edit: Complex increment / loop start mangling replaced.

P.S.: An optimizaion option might be to build the minimum in a local variable and assign to results[i] after the inner loop only.

user_14018790

If I understand correctly, you need to operate on an n by n matrix, but excluding the values in a diagonal, i.e:

X O O O
O X O O
O O X O
O O O X

You could reframe the problem by "unrolling" the matrix like so:

. O O O
. . O O O
. . . O O O
. . . . O O O

Then you could correct j in the inner loop:

for (int i = 0; i < n; i++) {
    // ...
    for (int j = i + 1; j < i + n; j++) {
        d = myfunction(x, y, i, j % n);
        // ...
    }
}
user_11421670
Related