Short-circuiting in C

[Billy Mays]

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.

 

[Ben Pfaff]

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 */
}

 

[Stefan Ram]

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

?

 

[Thomas Richter]

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

 

[Ben Pfaff]

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.

 

[Morris Keesan]

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.


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.

 

[Stefan Ram]

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.

 

[Billy Mays]

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.

 

[Stefan Ram]

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 »&«.

 

[Billy Mays]

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.

 

[Stefan Ram]

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]

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.

 

[Billy Mays]

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.

 

[Keith Thompson]

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.

 

[Urist Sethkab]

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 address 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]

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]

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]

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

 

[Billy Mays]

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]

Yes. The above is

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

(as long as not followed by an »else«).

I believe this will work, thanks!