Can I replace my if-statements to save running time?

Question

I am currently trying to improve the speed of my program.

I was wondering whether it would help to replace all if-statements of the type:

bool a=1;
int b=0;
if(a){b++;}

with this:

bool a=1;
int b=0;

b+=a;

I am unsure whether the conversion from bool to int could be a problem time-wise.

Answer 1

Compilers are allowed to assume that the underlying value of a bool isn't messed up, so optimizing compilers can avoid the branch.

If we look at the generated code for this artificial test

int with_if_bool(bool a, int b) {
    if(a){b++;}
    return b;
}

int with_if_char(unsigned char a, int b) {
    if(a){b++;}
    return b;
}

int without_if(bool a, int b) {
    b += a;
    return b;
}

clang will exploit this fact and generate the exact same branchless code that sums a and b for the bool version, and instead generate actual comparisons with zero in the unsigned char case (although it's still branchless code):

with_if_bool(bool, int): # @with_if_bool(bool, int)
  lea eax, [rdi + rsi]
  ret
with_if_char(unsigned char, int): # @with_if_char(unsigned char, int)
  cmp dil, 1
  sbb esi, -1
  mov eax, esi
  ret
without_if(bool, int): # @without_if(bool, int)
  lea eax, [rdi + rsi]
  ret

gcc will instead treat bool just as if it was an unsigned char, without exploiting its properties, generating similar code as clang's unsigned char case.

with_if_bool(bool, int):
  mov eax, esi
  cmp dil, 1
  sbb eax, -1
  ret
with_if_char(unsigned char, int):
  mov eax, esi
  cmp dil, 1
  sbb eax, -1
  ret
without_if(bool, int):
  movzx edi, dil
  lea eax, [rdi+rsi]
  ret

Finally, Visual C++ will treat the bool and the unsigned char versions equally, just as gcc, although with more naive codegen (it uses a conditional move instead of performing arithmetic with the flags register, which IIRC traditionally used to be less efficient, don't know for current machines).

a$ = 8
b$ = 16
int with_if_bool(bool,int) PROC ; with_if_bool, COMDAT
  test cl, cl
  lea eax, DWORD PTR [rdx+1]
  cmove eax, edx
  ret 0
int with_if_bool(bool,int) ENDP ; with_if_bool

a$ = 8
b$ = 16
int with_if_char(unsigned char,int) PROC ; with_if_char, COMDAT
  test cl, cl
  lea eax, DWORD PTR [rdx+1]
  cmove eax, edx
  ret 0
int with_if_char(unsigned char,int) ENDP ; with_if_char

a$ = 8
b$ = 16
int without_if(bool,int) PROC ; without_if, COMDAT
  movzx eax, cl
  add eax, edx
  ret 0
int without_if(bool,int) ENDP ; without_if

In all cases, no branches are generated; the only difference is that, on most compilers, some more complex code is generated that depends on a cmp or a test, creating a longer dependency chain.

That being said, I would worry about this kind of micro-optimization only if you actually run your code under a profiler, and the results point to this specific code (or to some tight loop that involve it); in general you should write sensible, semantically correct code and focus on using the correct algorithms/data structures. Micro-optimization comes later.

---

In my program, this wouldn't work, as a is actually an operation of the type: b+=(a==c)

This should be even better for the optimizer, as it doesn't even have any doubt about where the bool is coming from - it can just decide straight from the flags register. As you can see, here gcc produces quite similar code for the two cases, clang exactly the same, while VC++ as usual produces something that is more conditional-ish (a cmov) in the if case.

Answer 2

One rule of thumb when programming is to not micro-optimise.

Another rule is to write clear code.

But in this case, another rule applies. If you are writing optimised code then avoid any code that can cause branches, as you can cause unwanted cpu pipeline dumps due to failed branch prediction.

Bear in mind also that there are not bool and int types as such in assembler: just registers, so you will probably find that all conversions will be optimised out. Therefore

b += a;

wins for me; it's also clearer.