Arrangement of 2 by 2 condition in if statement in C-family language

Question

When programming, I'm usually dealing with two sets of conditions combined together, like:

if (A && B){...}
else if (!A && B){...}
else if (A && !B){...}
else if (!A && !B){...}

It can also be resolved using nested if statements.

if (A){
    if (B) {...}
    else {...}
}
else {
    if (B) {...}
    else {...}
}

EDIT: Some new thoughts, what about I firstly evaluate both A and B and store as temporary variable (then do as the first approach) in case that the evaluation of A and B both have no side-effect?

So my question is there any performance difference between them and what about their readability?

I code in C++, if matters.

A decent compiler would give you the same object code for this. Good to the check the assembly code generated in this case — sjsam, Aug 03 '16 at 03:50
Please Read: http://stackoverflow.com/questions/38532160/does-short-circuiting-make-execution-of-the-program-faster-and-is-analysing-whi — Omid CompSCI, Aug 03 '16 at 03:51
You can guess at it, but you can't be *sure* unless you try it both ways and check the performance of your program. — , Aug 03 '16 at 03:52
@sjsam, is that what g++'s `-fif-conversion` do? The document is not clear about it. — YiFei, Aug 03 '16 at 03:53
It may depend on the statistical distribution of A and B. If both are more likely to be true, then you get 2 evaluations and one branch. If both are likely to be false, then....you might consider re-ordering your expressions. Though the compiler will decide, but the processor's branch prediction may be able to figure things out and preload instructions on the most likely code path and eliminate any advantages the that compiler might provide. Code for clarity and intent before you optimize — Arunas, Aug 03 '16 at 04:00
@YiFei For the very basic applications of both the styles [\[ code1 \]](http://pastebin.com/raw/QUyimUtE) & [\[ code 2\]](http://pastebin.com/raw/MJMqY4x2) when compiled with `g++ -O2 -S -masm=intel -fif-conversion` gave me the same [\[ assembly \]](http://pastebin.com/VHcUmjF9)except for the change in filename — sjsam, Aug 03 '16 at 04:46
@YiFei : And the g++ manpage is pretty clear about `-fif-conversion` which says `-fif-conversion Attempt to transform conditional jumps into branch-less equivalents. This includes use of conditional moves, min, max, set flags and abs instructions, and some tricks DOABLE by standard arithmetics.` Also the `doable` may be a hint that this may not work for complex cases. — sjsam, Aug 03 '16 at 04:49

Robᵩ · Accepted Answer · 2016-08-03T03:58:08.287

5

The two cases are not the same. In the second case, A and B will each be evaluated exactly once. In the first case, A and B will evaluated a number of times, depending upon their value.

While this almost certainly won't affect the optimization of the typical case, it will matter if A or B have side effects.

edited Aug 03 '16 at 03:58

answered Aug 03 '16 at 03:53

Robᵩ

163,533
20
239
308

Question is Similar: : http://stackoverflow.com/questions/38532160/does-short-circuiting-make-execution-of-the-program-faster-and-is-analysing-whi – Omid CompSCI Aug 03 '16 at 03:55
Yes, that is similar to OP's performance question, but not his readability question. But bear in mind that my answer only addresses his unasked question: "are they semantically equivalent?" – Robᵩ Aug 03 '16 at 03:57
Why wouldn't the compiler generate some code that use the previously evaluated value? – YiFei Aug 03 '16 at 03:58
@Robᵩ, yes I agree with your answer! – Omid CompSCI Aug 03 '16 at 03:59
Wouldn't B evaluated twice? – CIsForCookies Aug 03 '16 at 04:00
@YiFei, to some extent some of these condition statements can be solved by branch prediction. To boost performance. – Omid CompSCI Aug 03 '16 at 04:00
1

@YiFei - Because the language doesn't allow it. Suppose your `A`, for example, is a function call. The compiler must invoke the function each time it is listed, potentially with side effects. OTOH, if `A` has no visible side effects, then the compiler can optimize both cases to the same code. – Robᵩ Aug 03 '16 at 04:00
1

@noob - No, `B` is evaluated only once. It might be evaluated in the `A == true` branch, or it might be evaluated in the `A == false` branch, but either way exactly once. – Robᵩ Aug 03 '16 at 04:01
1

@noob, how can B be evaluated twice? It only enters the first statement if A is true, – Omid CompSCI Aug 03 '16 at 04:01
Aha, then doesn't the second approach potentially more optimiz-able? – YiFei Aug 03 '16 at 04:01
@YiFei, No it is not, it is only optimizable if you guessed correctly that the first statement has a higher chance of failing since it is an &&, and in this case it would completely skip the inside of the if statement, if you guessed correctly. – Omid CompSCI Aug 03 '16 at 04:02

score 2 · Answer 2 · answered Aug 03 '16 at 03:54

2

There's no way to predict which code generation strategy the compiler will choose in cases like that (and it can actually depend on surrounding context). This makes your question unanswerable in general case. One should normally expect the compiler to be smart enough to recognize the equivalence of both of your constructs (assuming they are indeed equivalent) and choose the most optimal one automatically.

The most optimal code generation strategy might be something else altogether, e.g.

// Assuming A and B are either 0 or 1 
switch ((A * 2) + B) {
  case 0: ...; break;
  case 1: ...; break;
  case 2: ...; break;
  case 3: ...; break;
}

Just choose whatever makes your code more readable.

answered Aug 03 '16 at 03:54

AnT stands with Russia

312,472
42
525
765

1

Just a thought: use bit shift instead of multiplying seems better :) – YiFei Aug 03 '16 at 03:59
@YiFei: Bit shift is not better in this context. – AnT stands with Russia Aug 03 '16 at 04:01
Then yes because of the plus sign. – YiFei Aug 03 '16 at 04:03
`switch(bool(A)*2 + bool(B)) {` makes the assumption unnecessary. Or, to us an idiom that predates the `bool` type: `switch ( (!!A)*2 + (!!B) ) {`. – Robᵩ Aug 03 '16 at 04:03
@YiFei I totally agree! `(A << 1) | B` looks so much more beautify! – mash Aug 03 '16 at 04:12
@Robᵩ: The point was not to dive into the domain of compiler optimizations too deeply. If the compiler wanted to go in that direction it would implement the normalization as `!A*2 + !B` (there's no real need for double negation), but for a human this just makes things progressively more and more difficult to read. I didn't want to go too far in that direction, since it wasn't the main point of my answer. – AnT stands with Russia Aug 03 '16 at 04:56
Actually, it's better to leave this transform to the compiler. The reason is hidden in the `...`. Those cases might be folded, but the folding might only be possible if the compiler used e.g. `switch (A*3+B) { case 4: ...` – MSalters Aug 03 '16 at 12:35

score 0 · Answer 3 · edited Aug 03 '16 at 04:53

It's a hard question; honestly, I think everyone looks at this a little bit differently. As people have mentioned here it does not matter as a compiler should generate the same output for both (should! not necessarily will — it honestly depends on the code).

Yet, for example, let's look at this code:

int  Nested(int a)
{       
    if(a > 0)
    {
        if( a > 1)
        {
            if( a % 2 == 0)
            {
                if( a % 10 == 4)
                {
                    printf("a is valid");
                    return 1;
                }
                else
                {               
                    printf("a's last digit inst 4");
                }
            }
            else
            {
                printf(" a is not odd");
            }    
        }
        else
        {
            printf(" a is not bigger than 1");
        }
    }
    else
    {
        printf(" a is not bigger than 0");
    }

    return 0;

}

int NotNested(int a)
{
    if(a <= 0)
    {
        printf(" a is not bigger than 0");
        return 0;
    }

    if(a <= 1)
    {
        printf(" a is not bigger than 1");
        return 0;
    }

    if(a % 2 != 0)
    {
        printf(" a is not odd");
        return 0;
    }

    if( a % 10 != 4)
    {
        printf("a's last digit inst 4");
        return 0;
    }

    printf("a is valid");

    return 1;

}

I personally think that NotNested in my example is much more readable, yet it's my personal opinion and both of these functions should do the same.

So yeah, in terms, of readability try to avoid nesting.

Arrangement of 2 by 2 condition in if statement in C-family language

3 Answers3