Short-circuiting in C

Discussion in 'C Programming' started by Billy Mays, May 26, 2011.

  1. Billy Mays

    Billy Mays Guest

    Hey CLC,

    I was wondering if there is a way to avoid the C short circuiting for
    boolean expressions such as the following:

    if(a && b && c) {
    /* Do stuff */
    }

    I am currently doing GPU programming and it would be better to evaluate
    the entire condition, even if a is 0, since branches are slow.

    --
    Bill Mays
     
    Billy Mays, May 26, 2011
    #1
    1. Advertising

  2. Billy Mays

    Ben Pfaff Guest

    Billy Mays <> writes:

    > I was wondering if there is a way to avoid the C short circuiting for
    > boolean expressions such as the following:
    >
    > if(a && b && c) {
    > /* Do stuff */
    > }


    x = a;
    y = b;
    z = c;
    if (x && y && z) {
    /* Do stuff */
    }
    --
    Ben Pfaff
    http://benpfaff.org
     
    Ben Pfaff, May 26, 2011
    #2
    1. Advertising

  3. Billy Mays

    Stefan Ram Guest

    Billy Mays <> writes:
    >I was wondering if there is a way to avoid the C short
    >circuiting for boolean expressions such as the following:


    In C, there are no »boolean expressions«. The conditional
    evaluation is related to certain operators, not to the
    programming language. The following is a statement.

    >if(a && b && c) {
    > /* Do stuff */
    >}


    What about

    !!a & !!b & !!c

    ?
     
    Stefan Ram, May 26, 2011
    #3
  4. On 26.05.2011 20:09, Ben Pfaff wrote:
    > Billy Mays<> writes:
    >
    >> I was wondering if there is a way to avoid the C short circuiting for
    >> boolean expressions such as the following:
    >>
    >> if(a&& b&& c) {
    >> /* Do stuff */
    >> }

    >
    > x = a;
    > y = b;
    > z = c;
    > if (x&& y&& z) {
    > /* Do stuff */
    > }


    Sorry, I fail to see how this should work. Actually, a sufficiently
    smart compiler would reduce this to just the above, and in fact, a
    compiler can modify the code always on the basis of the "as-if" rule.

    So the question goes back to the OP what the intent of disabling the
    short-circuiting is. If it is to avoid two branches, then if a,b and c
    are always 0 or 1 (or any other number, identical for all three
    variables), you could simply write:

    if (a & b & c) {
    }

    If the intent is that an actual access of the variables happen, probably
    because they are hardware registers, then you would also suggest to
    declare them as volatile.

    However, typically the impact of such micro-optimizations is negligible.
    Question to the OP: Did you actually measure?

    Greetings,
    Thomas
     
    Thomas Richter, May 26, 2011
    #4
  5. Billy Mays

    Ben Pfaff Guest

    Thomas Richter <-berlin.de> writes:

    > On 26.05.2011 20:09, Ben Pfaff wrote:
    >> Billy Mays<> writes:
    >>
    >>> I was wondering if there is a way to avoid the C short circuiting for
    >>> boolean expressions such as the following:
    >>>
    >>> if(a&& b&& c) {
    >>> /* Do stuff */
    >>> }

    >>
    >> x = a;
    >> y = b;
    >> z = c;
    >> if (x&& y&& z) {
    >> /* Do stuff */
    >> }

    >
    > Sorry, I fail to see how this should work. Actually, a sufficiently
    > smart compiler would reduce this to just the above, and in fact, a
    > compiler can modify the code always on the basis of the "as-if" rule.


    The code that I presented always evaluates all of 'a', 'b', and
    'c', which is what the OP said that he wanted.
    --
    Ben Pfaff
    http://benpfaff.org
     
    Ben Pfaff, May 26, 2011
    #5
  6. On Thu, 26 May 2011 14:17:15 -0400, Stefan Ram <-berlin.de>
    wrote:

    > Billy Mays <> writes:
    >> I was wondering if there is a way to avoid the C short
    >> circuiting for boolean expressions such as the following:

    >
    > In C, there are no »boolean expressions«. The conditional
    > evaluation is related to certain operators, not to the
    > programming language. The following is a statement.
    >
    >> if(a && b && c) {
    >> /* Do stuff */
    >> }

    >
    > What about
    >
    > !!a & !!b & !!c


    I find it easier to read as

    if ((a != 0) & (b != 0) & (c != 0))

    The meaning of (a != 0) is more immediately obvious to me than !!a, which
    I have to think about for a couple of seconds.

    --
    Morris Keesan --
     
    Morris Keesan, May 26, 2011
    #6
  7. Billy Mays

    Stefan Ram Guest

    "Morris Keesan" <> writes:
    >The meaning of (a != 0) is more immediately obvious to me than !!a, which
    >I have to think about for a couple of seconds.


    »!!« is a C idiom.
     
    Stefan Ram, May 26, 2011
    #7
  8. Billy Mays

    Billy Mays Guest

    On 05/26/2011 02:22 PM, Thomas Richter wrote:
    > On 26.05.2011 20:09, Ben Pfaff wrote:
    >> Billy Mays<> writes:
    >>
    >>> I was wondering if there is a way to avoid the C short circuiting for
    >>> boolean expressions such as the following:
    >>>
    >>> if(a&& b&& c) {
    >>> /* Do stuff */
    >>> }

    >>
    >> x = a;
    >> y = b;
    >> z = c;
    >> if (x&& y&& z) {
    >> /* Do stuff */
    >> }

    >
    > Sorry, I fail to see how this should work. Actually, a sufficiently
    > smart compiler would reduce this to just the above, and in fact, a
    > compiler can modify the code always on the basis of the "as-if" rule.
    >
    > So the question goes back to the OP what the intent of disabling the
    > short-circuiting is. If it is to avoid two branches, then if a,b and c
    > are always 0 or 1 (or any other number, identical for all three
    > variables), you could simply write:
    >
    > if (a & b & c) {
    > }
    >
    > If the intent is that an actual access of the variables happen, probably
    > because they are hardware registers, then you would also suggest to
    > declare them as volatile.
    >
    > However, typically the impact of such micro-optimizations is negligible.
    > Question to the OP: Did you actually measure?
    >
    > Greetings,
    > Thomas



    I did not, but I suspect using an & instead of an && would fail if a was
    1 and b was 2. The programming guide I was using mentioned that the
    short-circuiting behavior would force all the threads to serialize
    rather than run in lockstep.

    --
    Bill
     
    Billy Mays, May 26, 2011
    #8
  9. Billy Mays

    Stefan Ram Guest

    Billy Mays <> writes:
    >I did not, but I suspect using an & instead of an && would fail if a was
    >1 and b was 2. The programming guide I was using mentioned that the
    >short-circuiting behavior would force all the threads to serialize
    >rather than run in lockstep.


    Which threads?

    BTW, I forgot to mention that there is another difference
    between »&&« and »&«: »&« has no sequence-point, so when you
    need a certain sequence, you can't rely on »&«.
     
    Stefan Ram, May 26, 2011
    #9
  10. Billy Mays

    Billy Mays Guest

    On 05/26/2011 03:03 PM, Stefan Ram wrote:
    > Billy Mays<> writes:
    >> I did not, but I suspect using an& instead of an&& would fail if a was
    >> 1 and b was 2. The programming guide I was using mentioned that the
    >> short-circuiting behavior would force all the threads to serialize
    >> rather than run in lockstep.

    >
    > Which threads?
    >
    > BTW, I forgot to mention that there is another difference
    > between »&&« and »&«: »&« has no sequence-point, so when you
    > need a certain sequence, you can't rely on »&«.
    >


    On the GPU I am using, threads execute simultaneously as long as they
    all execute the exact same instructions (ie, they all take the branch).
    If one of the threads takes a different execution path, then each
    thread has to run in serial which means the parallel speed gain is lost.

    It would be cheaper to evaluate the whole expression rather than
    short-circuit since it would mean that all the threads could take the
    same path.

    For example,

    if(a && b && c) {
    /* Do stuff */
    }

    Thread 1: a = 1, b = 2, c = 0

    Thread 2: a = 0, b = 1, c = 2

    Neither thread will execute the body of the if statement, but Thread 2
    would branch away while Thread 1 would still be evaluating b and c.

    --
    Bill
     
    Billy Mays, May 26, 2011
    #10
  11. Billy Mays

    Stefan Ram Guest

    Billy Mays <> writes:
    >For example,
    >if(a && b && c) {
    > /* Do stuff */
    >}
    >Neither thread will execute the body of the if statement, but Thread 2
    >would branch away while Thread 1 would still be evaluating b and c.


    Yes. The above is

    if(a)if(b)if(c)
    {}

    (as long as not followed by an »else«).
     
    Stefan Ram, May 26, 2011
    #11
  12. Billy Mays <> writes:
    > On 05/26/2011 02:22 PM, Thomas Richter wrote:
    >> On 26.05.2011 20:09, Ben Pfaff wrote:
    >>> Billy Mays<> writes:
    >>>
    >>>> I was wondering if there is a way to avoid the C short circuiting for
    >>>> boolean expressions such as the following:
    >>>>
    >>>> if(a&& b&& c) {
    >>>> /* Do stuff */
    >>>> }
    >>>
    >>> x = a;
    >>> y = b;
    >>> z = c;
    >>> if (x&& y&& z) {
    >>> /* Do stuff */
    >>> }

    >>
    >> Sorry, I fail to see how this should work. Actually, a sufficiently
    >> smart compiler would reduce this to just the above, and in fact, a
    >> compiler can modify the code always on the basis of the "as-if" rule.
    >>
    >> So the question goes back to the OP what the intent of disabling the
    >> short-circuiting is. If it is to avoid two branches, then if a,b and c
    >> are always 0 or 1 (or any other number, identical for all three
    >> variables), you could simply write:
    >>
    >> if (a & b & c) {
    >> }
    >>
    >> If the intent is that an actual access of the variables happen, probably
    >> because they are hardware registers, then you would also suggest to
    >> declare them as volatile.
    >>
    >> However, typically the impact of such micro-optimizations is negligible.
    >> Question to the OP: Did you actually measure?

    >
    > I did not, but I suspect using an & instead of an && would fail if a was
    > 1 and b was 2. The programming guide I was using mentioned that the
    > short-circuiting behavior would force all the threads to serialize
    > rather than run in lockstep.


    What threads?

    In the code you posted, the subexpressions all appear to be simple
    variable references, and short circuiting won't make any difference
    unless they're volatile. If they're stand-ins for more complex
    expressions (function calls?), then it could matter what those
    expressions look like.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, May 26, 2011
    #12
  13. Billy Mays

    Billy Mays Guest

    On 05/26/2011 03:55 PM, Keith Thompson wrote:
    > Billy Mays<> writes:
    >> On 05/26/2011 02:22 PM, Thomas Richter wrote:
    >>> On 26.05.2011 20:09, Ben Pfaff wrote:
    >>>> Billy Mays<> writes:
    >>>>
    >>>>> I was wondering if there is a way to avoid the C short circuiting for
    >>>>> boolean expressions such as the following:
    >>>>>
    >>>>> if(a&& b&& c) {
    >>>>> /* Do stuff */
    >>>>> }
    >>>>
    >>>> x = a;
    >>>> y = b;
    >>>> z = c;
    >>>> if (x&& y&& z) {
    >>>> /* Do stuff */
    >>>> }
    >>>
    >>> Sorry, I fail to see how this should work. Actually, a sufficiently
    >>> smart compiler would reduce this to just the above, and in fact, a
    >>> compiler can modify the code always on the basis of the "as-if" rule.
    >>>
    >>> So the question goes back to the OP what the intent of disabling the
    >>> short-circuiting is. If it is to avoid two branches, then if a,b and c
    >>> are always 0 or 1 (or any other number, identical for all three
    >>> variables), you could simply write:
    >>>
    >>> if (a& b& c) {
    >>> }
    >>>
    >>> If the intent is that an actual access of the variables happen, probably
    >>> because they are hardware registers, then you would also suggest to
    >>> declare them as volatile.
    >>>
    >>> However, typically the impact of such micro-optimizations is negligible.
    >>> Question to the OP: Did you actually measure?

    >>
    >> I did not, but I suspect using an& instead of an&& would fail if a was
    >> 1 and b was 2. The programming guide I was using mentioned that the
    >> short-circuiting behavior would force all the threads to serialize
    >> rather than run in lockstep.

    >
    > What threads?
    >
    > In the code you posted, the subexpressions all appear to be simple
    > variable references, and short circuiting won't make any difference
    > unless they're volatile. If they're stand-ins for more complex
    > expressions (function calls?), then it could matter what those
    > expressions look like.
    >



    The processor is SIMD so each thread runs the same code, but they modify
    their own data. As long as each thread executes the same instruction,
    the processor can simultaneously work on each thread's data.

    However, if one of the threads branches then the processor degrades
    (SISD?) and loses a lot of the parallelism.

    The goal here is to ensure each thread does exactly the same thing, even
    if it is slightly wasteful.

    Note: These are not OS threads; they are similar but lighter weight.

    --
    Bill
     
    Billy Mays, May 26, 2011
    #13
  14. "Scott Fluhrer" <> writes:
    > "Stefan Ram" <-berlin.de> wrote in message
    > news:-berlin.de...
    >> Billy Mays <> writes:
    >>>I was wondering if there is a way to avoid the C short
    >>>circuiting for boolean expressions such as the following:

    >>
    >> In C, there are no »boolean expressions«. The conditional
    >> evaluation is related to certain operators, not to the
    >> programming language. The following is a statement.
    >>
    >>>if(a && b && c) {
    >>> /* Do stuff */
    >>>}

    >>
    >> What about
    >>
    >> !!a & !!b & !!c
    >>
    >> ?

    >
    > On some compilers, the expression !!x causes the compiler to emit a
    > conditional jump; on others it doesn't. The OP would be wise to test this
    > on his platform.
    >
    > On the other hand, if the OP knows that a, b, c will be limited to the
    > values (0, 1), we have this code:
    >
    > if (a & b & c) {
    > /* Do stuff */
    > }


    And that will quietly break if any of them takes on a value other than 0
    or 1, perhaps in a later version of the program. "&&" and "&" are not
    interchangeable except in very narrow circumstances.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, May 26, 2011
    #14
  15. On May 26, 4:28 pm, Keith Thompson <> wrote:
    > "Scott Fluhrer" <> writes:
    > > "Stefan Ram" <-berlin.de> wrote in message
    > >news:-berlin.de...
    > >> Billy Mays <> writes:
    > >>>I was wondering if there is a way to avoid the C short
    > >>>circuiting for boolean expressions such as the following:

    >
    > >>  In C, there are no »boolean expressions«. The conditional
    > >>  evaluation is related to certain operators, not to the
    > >>  programming language. The following is a statement.

    >
    > >>>if(a && b && c) {
    > >>>     /* Do stuff */
    > >>>}

    >
    > >>  What about

    >
    > >> !!a & !!b & !!c

    >
    > >>  ?

    >
    > > On some compilers, the expression !!x causes the compiler to emit a
    > > conditional jump; on others it doesn't.  The OP would be wise to testthis
    > > on his platform.

    >
    > > On the other hand, if the OP knows that a, b, c will be limited to the
    > > values (0, 1), we have this code:

    >
    > >     if (a & b & c) {
    > >         /* Do stuff */
    > >     }

    >
    > And that will quietly break if any of them takes on a value other than 0
    > or 1, perhaps in a later version of the program.  "&&" and "&" are not
    > interchangeable except in very narrow circumstances.
    >
    > --
    > Keith Thompson (The_Other_Keith)  <http://www.ghoti.net/~kst>
    > Nokia
    > "We must do something.  This is something.  Therefore, we must do this."
    >     -- Antony Jay and Jonathan Lynn, "Yes Minister"


    Wouldn't !(a | b | c) work, then?
    (Not very experienced, so there could be some obvious reason why not
    that I can't see)
     
    Urist Sethkab, May 26, 2011
    #15
  16. Billy Mays

    Nobody Guest

    On Thu, 26 May 2011 13:58:59 -0400, Billy Mays wrote:

    > I was wondering if there is a way to avoid the C short circuiting for
    > boolean expressions such as the following:
    >
    > if(a && b && c) {
    > /* Do stuff */
    > }
    >
    > I am currently doing GPU programming and it would be better to evaluate
    > the entire condition, even if a is 0, since branches are slow.


    How does GPU programming relate to C programming?

    Sure, GLSL/HLSL/Cg are "C-like" languages, but they aren't C.
     
    Nobody, May 27, 2011
    #16
  17. Billy Mays

    Eric Sosman Guest

    On 5/26/2011 1:58 PM, Billy Mays wrote:
    > Hey CLC,
    >
    > I was wondering if there is a way to avoid the C short circuiting for
    > boolean expressions such as the following:
    >
    > if(a && b && c) {
    > /* Do stuff */
    > }
    >
    > I am currently doing GPU programming and it would be better to evaluate
    > the entire condition, even if a is 0, since branches are slow.


    You will take one branch if a or b or c is zero, none if all
    are nonzero. You will never take more than one branch. So no
    rearrangement can help unless a branch-not-taken has significant
    cost.

    If it's still worth proceeding, consider replacing && with &:

    if (a & b & c) ...

    This is not quite equivalent to the original, because it can only
    work with integer operands and only then if a,b,c have suitable
    values (consider 1,7,32, for example). But you can fix that:

    if ((a != 0) & (b != 0) & (c != 0)) ...

    or more briefly:

    if ( !(!a | !b | !c)) ...

    or if you find that hard to read:

    if (!!a & !!b & !!c) ...

    Of course, the question of what all these alternatives compile
    to and which is fastest in your particular situation is something
    that you'll have to answer yourself, preferably by measurement.

    --
    Eric Sosman
    d
     
    Eric Sosman, May 27, 2011
    #17
  18. Billy Mays

    Eric Sosman Guest

    On 5/26/2011 4:17 PM, Billy Mays wrote:
    > On 05/26/2011 03:55 PM, Keith Thompson wrote:
    >> Billy Mays<> writes:
    >>> On 05/26/2011 02:22 PM, Thomas Richter wrote:
    >>>> On 26.05.2011 20:09, Ben Pfaff wrote:
    >>>>> Billy Mays<> writes:
    >>>>>
    >>>>>> I was wondering if there is a way to avoid the C short circuiting for
    >>>>>> boolean expressions such as the following:
    >>>>>>
    >>>>>> if(a&& b&& c) {
    >>>>>> /* Do stuff */
    >>>>>> }

    > [...]
    > The processor is SIMD so each thread runs the same code, but they modify
    > their own data. As long as each thread executes the same instruction,
    > the processor can simultaneously work on each thread's data.
    >
    > However, if one of the threads branches then the processor degrades
    > (SISD?) and loses a lot of the parallelism.
    >
    > The goal here is to ensure each thread does exactly the same thing, even
    > if it is slightly wasteful.


    C has no way to express the computation you desire. C's abstract
    machine has only one flow of control, if we ignore the rather mysterious
    effects of asynchronous signals and `volatile' variable. There is no
    C construct that will evaluate a,b,c in parallel execution paths and
    then somehow combine the three results into a single test. You've
    chosen the wrong implementation language.

    --
    Eric Sosman
    d
     
    Eric Sosman, May 27, 2011
    #18
  19. Billy Mays

    Billy Mays Guest

    On 5/26/2011 7:06 PM, Nobody wrote:
    > On Thu, 26 May 2011 13:58:59 -0400, Billy Mays wrote:
    >
    >> I was wondering if there is a way to avoid the C short circuiting for
    >> boolean expressions such as the following:
    >>
    >> if(a&& b&& c) {
    >> /* Do stuff */
    >> }
    >>
    >> I am currently doing GPU programming and it would be better to evaluate
    >> the entire condition, even if a is 0, since branches are slow.

    >
    > How does GPU programming relate to C programming?
    >
    > Sure, GLSL/HLSL/Cg are "C-like" languages, but they aren't C.
    >
    >



    I'm using OpenCL's library which then invokes the GPU. The programming
    is done in a subset of C.

    --Bill
     
    Billy Mays, May 27, 2011
    #19
  20. Billy Mays

    Billy Mays Guest

    On 5/26/2011 3:32 PM, Stefan Ram wrote:
    > Billy Mays<> writes:
    >> For example,
    >> if(a&& b&& c) {
    >> /* Do stuff */
    >> }
    >> Neither thread will execute the body of the if statement, but Thread 2
    >> would branch away while Thread 1 would still be evaluating b and c.

    >
    > Yes. The above is
    >
    > if(a)if(b)if(c)
    > {}
    >
    > (as long as not followed by an »else«).
    >


    I believe this will work, thanks!

    --
    Bill
     
    Billy Mays, May 27, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Pho Bo Vien

    Short circuiting validation controls

    Pho Bo Vien, Apr 28, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    377
  2. ram

    Short circuiting..

    ram, Apr 3, 2004, in forum: C Programming
    Replies:
    3
    Views:
    434
  3. Dave Opstad
    Replies:
    16
    Views:
    467
    Duncan Booth
    Mar 11, 2005
  4. kj
    Replies:
    11
    Views:
    476
    Jean-Michel Pichavant
    Mar 23, 2010
  5. Andrea Crotti

    avoid import short-circuiting

    Andrea Crotti, Mar 16, 2012, in forum: Python
    Replies:
    0
    Views:
    127
    Andrea Crotti
    Mar 16, 2012
Loading...

Share This Page