logic optimization

**NeonBlack** · 01-09-2008

I'm sorry if this is a silly or stupid question, but I couldn't find anything in the faq, and I'm not quite sure what search terms to use to find something like this:

Say I have two functions, f() and g(). We'll say they either return 0 or 1. f() is very fast, and has a low likely hood of being true and g() is much slower than f().

Consider the statement

Code:

if (f() && g())
{
...
}

Obviously, if i know f() is false, I'm wasting my time checking g().
Does the if statement break as soon as it sees that f() is false? Or does is run all the functions first and then check the logic later? If it does then it would be faster (maybe just a little less readable) to write

Code:

if (f())
{
     if (g())
     {
     ...
     }
}

Or maybe the compiler optimizes it? Does it depend on the compiler? Thanks in advance

nb

**matsp** · 01-09-2008

The compiler can and will optimize any conditional expression - in fact it's part of the standard, so you can do things like this:

Code:

if (p != NULL && p->blah ....)

Since we check for NULL first, we are guaranteed that the pointer is non-NULL when it does the p->blah access, and thus [supposedly] a valid pointer.

Likewise:

Code:

if (x != 0 && y / x > z) ...

will not ever divide by zero.

--
Mats

**NeonBlack** · 01-09-2008

Thanks mats.
It makes me happy that I don't have to compromise readability and efficiency (or crashes as in your second example).

**anon** · 01-09-2008

This is called Short-circuit evaluation

**vart** · 01-09-2008

not always 2 branching conditions will result in more effitient code than one braching on the resulting logical value...

what you get - there is no need to evaluate g()
what you loose - the branch misprediction rate is increased

You cannot be sure always in the result without profiling of the critical section of the code

So do not start preemptive optimisation if you are not sure that the portion of the code realy is a performance bottleneck.

Focus on the readability of your code first

**matsp** · 01-09-2008

Originally Posted by vart

not always 2 branching conditions will result in more effitient code than one braching on the resulting logical value...

what you get - there is no need to evaluate g()
what you loose - the branch misprediction rate is increased

You cannot be sure always in the result without profiling of the critical section of the code

So do not start preemptive optimisation if you are not sure that the portion of the code realy is a performance bottleneck.

Focus on the readability of your code first

Do you actually believe that the compiler will generate different code for

Code:

if (f() && g()) {
...
}

than for

Code:

if (f()) {
   if (g()) {
     ...
   }
}

I would suggest that this is not the case.

--
Mats

**vart** · 01-09-2008

I believe that compiler will generate different code for

Code:

if (f() && g() )
{
}

and

Code:

if(f() & g() )
{
}

first code has 2 branching points
second code has 1 branching point but calculates g() always

**matsp** · 01-09-2008

Originally Posted by vart

I believe that compiler will generate different code for

Code:

if (f() && g() )
{
}

and

Code:

if(f() & g() )
{
}

first code has 2 branching points
second code has 1 branching point but calculates g() always

No, it won't - in fact it's not allowed to do that - as explained above, the compiler MUST short-circuit any logical operations, so that you can construct code like I described above, where you check one condition and then a second one that REQUIRES the first condition to be true. And the compiler must also not re-order the operations in an if-statement, so g() can not be called before f() has been called.

--
Mats

**vart** · 01-09-2008

you are talking about logical AND
in a second code is a binary AND - it works different

**anon** · 01-09-2008

I believe that compiler will generate different code for...

Yes, logical and bitwise operators are two different things.

**matsp** · 01-09-2008

Originally Posted by vart

you are talking about logical AND
in a second code is a binary AND - it works different

Yes, of course - sorry, my mistake.

But unless the g() function is extremely short [to the point where it inlines], it probably doesn't run faster than the branches version - only if the predictability of (f() & g()) is better than f() and g() on their own. It is however a "good" way to force the compiler to perform both functions in the if-statement.

You also have to watch for the precedence of & vs && - they are almost at opposite ends of the scale.

--
Mats

**vart** · 01-09-2008

My point was not HOW to optimize the expression
Rather - YOU SHOULD NOT optimize till you are sure

- the code HAVE to be optimized
- the resulting code gives a better results

So in regular case - readability should be the main concern of the programmer for the resulting code structure (and leave the optimization issue to compiler)

**matsp** · 01-09-2008

Originally Posted by vart

My point was not HOW to optimize the expression
Rather - YOU SHOULD NOT optimize till you are sure

- the code HAVE to be optimized
- the resulting code gives a better results

So in regular case - readability should be the main concern of the programmer for the resulting code structure (and leave the optimization issue to compiler)

I completely agree with that [and probably should have said so in the first post].

--
Mats

**robwhit** · 01-09-2008

Originally Posted by vart

I believe that compiler will generate different code for

Code:

if (f() && g() )
{
}

and

Code:

if(f() & g() )
{
}

first code has 2 branching points
second code has 1 branching point but calculates g() always

It is also different functionally:

Code:

C:\>type c.c
#include <stdio.h>

int func1()
{
    return 1;
}

int func2()
{
    return 2;
}

int main()
{
    if (func1() & func2())
        puts("True");
    else
        puts("False");

    if (func1() && func2())
        puts("True");
    else
        puts("False");

    return 0;
}

C:\>gcc c.c -Wall -Werror -ansi -pedantic

C:\>a
False
True

C:\>

**vart** · 01-09-2008

It is also different functionally

You should know what you do when you apply this trick...
You can always add !! when you should & some not 1 values

Thread: logic optimization

Thread Tools

Search Thread

Display

logic optimization

Similar Threads

Turn Off Optimization?

need reading material for c++ database optimization

Digital Logic

Optimization settings