logic optimization

This is a discussion on logic optimization within the C Programming forums, part of the General Programming Boards category; I'm sorry if this is a silly or stupid question, but I couldn't find anything in the faq, and I'm ...

  1. #1
    Registered User NeonBlack's Avatar
    Join Date
    Nov 2007
    Posts
    435

    logic optimization

    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

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User NeonBlack's Avatar
    Join Date
    Nov 2007
    Posts
    435
    Thanks mats.
    It makes me happy that I don't have to compromise readability and efficiency (or crashes as in your second example).

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    This is called Short-circuit evaluation
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by vart View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by vart View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    you are talking about logical AND
    in a second code is a binary AND - it works different
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I believe that compiler will generate different code for...
    Yes, logical and bitwise operators are two different things.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by vart View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    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)
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by vart View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Quote Originally Posted by vart View Post
    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:\>

  15. #15
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Turn Off Optimization?
    By danlee58 in forum C Programming
    Replies: 6
    Last Post: 12-10-2008, 02:52 AM
  2. need reading material for c++ database optimization
    By elninio in forum C++ Programming
    Replies: 0
    Last Post: 07-24-2008, 11:32 PM
  3. Digital Logic
    By strokebow in forum Tech Board
    Replies: 3
    Last Post: 12-09-2006, 12:05 PM
  4. Optimization settings
    By Roaring_Tiger in forum C Programming
    Replies: 4
    Last Post: 02-23-2005, 01:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21