Velocity Reviews > Short-circuiting in C

# Short-circuiting in C

Stefan Ram
Guest
Posts: n/a

 05-26-2011
Billy Mays <(E-Mail Removed)> 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«).

Keith Thompson
Guest
Posts: n/a

 05-26-2011
Billy Mays <(E-Mail Removed)> writes:
> On 05/26/2011 02:22 PM, Thomas Richter wrote:
>> On 26.05.2011 20:09, Ben Pfaff wrote:
>>> Billy Mays<(E-Mail Removed)> 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.

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.velocityreviews.com/forums/(E-Mail Removed) <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"

Billy Mays
Guest
Posts: n/a

 05-26-2011
On 05/26/2011 03:55 PM, Keith Thompson wrote:
> Billy Mays<(E-Mail Removed)> writes:
>> On 05/26/2011 02:22 PM, Thomas Richter wrote:
>>> On 26.05.2011 20:09, Ben Pfaff wrote:
>>>> Billy Mays<(E-Mail Removed)> 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.

>
>
> 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.

(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

Keith Thompson
Guest
Posts: n/a

 05-26-2011
"Scott Fluhrer" <(E-Mail Removed)> writes:
> "Stefan Ram" <(E-Mail Removed)-berlin.de> wrote in message
> news:(E-Mail Removed)-berlin.de...
>> Billy Mays <(E-Mail Removed)> 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 */
>>>}

>>
>>
>> !!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) (E-Mail Removed) <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"

Urist Sethkab
Guest
Posts: n/a

 05-26-2011
On May 26, 4:28*pm, Keith Thompson <(E-Mail Removed)> wrote:
> "Scott Fluhrer" <(E-Mail Removed)> writes:
> > "Stefan Ram" <(E-Mail Removed)-berlin.de> wrote in message
> >news:(E-Mail Removed)-berlin.de...
> >> Billy Mays <(E-Mail Removed)> 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 */
> >>>}

>

>
> >> !!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) (E-Mail Removed) *<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)

Nobody
Guest
Posts: n/a

 05-26-2011
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.

Eric Sosman
Guest
Posts: n/a

 05-27-2011
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
(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 05-27-2011
On 5/26/2011 4:17 PM, Billy Mays wrote:
> On 05/26/2011 03:55 PM, Keith Thompson wrote:
>> Billy Mays<(E-Mail Removed)> writes:
>>> On 05/26/2011 02:22 PM, Thomas Richter wrote:
>>>> On 26.05.2011 20:09, Ben Pfaff wrote:
>>>>> Billy Mays<(E-Mail Removed)> 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
(E-Mail Removed)d

Billy Mays
Guest
Posts: n/a

 05-27-2011
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
Guest
Posts: n/a

 05-27-2011
On 5/26/2011 3:32 PM, Stefan Ram wrote:
> Billy Mays<(E-Mail Removed)> 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