How to combine if() so that a function is called only one time to avoid branch miss?

Question

This is a c++ coding problem.

  if (condition)
            initialize arg2;

 for loop
 {
      if (condition)
            f(arg1, arg2[loop_index]);
      else  
            f(arg1, 0); 

 }

How to combine the if() to call f() only one time ?

arg2 may consume a lot of memory, if condition is false, we do not need to initialize it.

Any help will be appreciated.

Have you put your code through a profiler? Your compiler will probably make whatever optimization is suggested to you automatically. — dupersuper, Nov 07 '12 at 16:25
Loop unswitching. If you don't know what that means and don't immediately recognize it when looking it up, you're most likely wasting your time trying to optimize at this level of abstraction. — , Nov 07 '12 at 16:25
What do you mean by "avoid branch miss"? Whether `condition` is true or false, you will definitely be calling `f()`, so any changes you make will only be stylistic. — Brandon, Nov 07 '12 at 16:26

score 2 · Answer 1 · edited Nov 07 '12 at 16:31

2

 if (condition)
       initialize arg2;

 for loop
 {
     f(arg1, condition?arg2[loop_index]:0);
 }

edited Nov 07 '12 at 16:31

amit

175,853
27
231
333

answered Nov 07 '12 at 16:21

tillerstarr

2,616
1
21
35

2

There still going to be a branch in the binary code I assume, ternary operator is not magic. – amit Nov 07 '12 at 16:22
@amit: A single branch won't have the same penalty as one branch per loop iteration. This does not mean there won't be *any* branch, but it gives a simple approach where a branches will have little to no impact. – David Rodríguez - dribeas Nov 07 '12 at 16:23
@DavidRodríguez-dribeas: But the branch using the trenary operator is still within the loop. what's the difference? – amit Nov 07 '12 at 16:24
this is trivial and not c++ specific. – didierc Nov 07 '12 at 16:27
@amit: I have tested that in the past. It depends on the architecture, but in intel that particular construct will not create a branch, it generates a test for the condition and then one instruction that will copy to the register if the condition was met or do nothing. There is no branch, and no branch miss prediction. – David Rodríguez - dribeas Nov 07 '12 at 16:28
@DavidRodríguez-dribeas: I see, this is a different story then if it does it. But I assume it is indeed compiler & hardware specific. I guess to make sure it happens one should use direct assembly code, or is there a way to guarantee it in the language itself? (assuming of course `condition` can be changed between iterations) – amit Nov 07 '12 at 16:31
@amit: You must trust that your compiler will use the best it can from the hardware. You might want to verify this by inspecting the generated code if there is a performance bottleneck, but the compiler usually knows the architecture better than we do. You might want to look [here](http://stackoverflow.com/a/7186810/36565) – David Rodríguez - dribeas Nov 07 '12 at 16:33
1

@DavidRodríguez-dribeas: Generally speaking - yes. But when the question specifically asks for optimizing the branch - questions should be asked and compilers should not be *automatically* trusted. – amit Nov 07 '12 at 16:34
@amit: The code in this answer optimizes the branch on intel platforms. You can trust that :) You can use more convoluted approaches: `(!!(condition)*arg2[loop_index])` for example will also avoid the branch. (The extra `!!` are just in case `condition` yields a number and not a `bool`). Also note that the question is based on the premise that the condition does not change inside the loop (or else it would be accessing uninitialized values in `arg2`) – David Rodríguez - dribeas Nov 07 '12 at 16:36
@David Rodríguez, a bool times a double, the result is still a double ? thanks ! – runner frank Nov 07 '12 at 16:45
condition is a bool. What if I want to avoid !! operator, because the loop{} is on time critical path. I try to reduce any unnecessary operations in side the loop. Thanks ! – runner frank Nov 07 '12 at 17:58

Blagovest Buyukliev · Answer 2 · 2012-11-07T16:42:17.340

1

You could easily take the branch out of the loop and have two loops in outer branches instead:

if (condition) {
  initialize arg2;

  for loop {
    f(arg1, arg2[loop_index]);
  }
} else {
  for loop {
    f(arg1, 0);
  }
}

edited Nov 07 '12 at 16:42

answered Nov 07 '12 at 16:24

Blagovest Buyukliev

42,498
14
94
130

Nice work around, if `condition` cannot be changed between iterations.+1 However, thanks to branch prediction, if it is indeed the case, the overhead of the branch in each iteration should be minor anyway. – amit Nov 07 '12 at 16:25
NB this (the 'moving the condition out of the loop' part; then combining the duplicate condition should be even easier) is an old and basic compiler optimization. – Nov 07 '12 at 16:28

score 0 · Answer 3 · answered Nov 14 '12 at 13:39

the simplest of all, make a variable say flag form 0 to 1,if executed 1 time. make flag as globle variable.

int flag=0;
main(){//code}

  if (condition&&flag==0)
        f(arg1, arg2[loop_index]);
  else  
        f(arg1, 0);

inside f()

f(){
flag=1;
//rest code
}

How to combine if() so that a function is called only one time to avoid branch miss?

3 Answers3