Velocity Reviews > Short-circuiting in C

# Short-circuiting in C

Shao Miller
Guest
Posts: n/a

 05-27-2011
On 5/26/2011 12: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.

#include <stdio.h>

#define f(x) ((x) ? 1 : 0)

int main(void) {
int a, b, c = b = a = 0;
if (1 << 2 >> f(a) >> f(b) >> f(c))
puts("Boo.");
else
puts("Yay.");
return 0;
}

Shao Miller
Guest
Posts: n/a

 05-27-2011
On 5/26/2011 8:41 PM, Shao Miller wrote:
> On 5/26/2011 12: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.

Sorry, that was a bad example as GCC was clever and actually produced a
branch. So a better example might be:

#include <stdio.h>

#define f(x) ((x) ? 1 : 0)

int main(void) {
volatile int x = 1, a, b, c = b = a = 2;
if (x << 2 >> f(a) >> f(b) >> f(c))
puts("Boo.");
else
puts("Yay.");
return 0;
}

Shao Miller
Guest
Posts: n/a

 05-27-2011
On 5/26/2011 9:03 PM, Shao Miller wrote:
> On 5/26/2011 8:41 PM, Shao Miller wrote:
>> On 5/26/2011 12: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.

Though the strategy'd grow pretty quickly, maybe even:

#include <stdio.h>

const char * func(int a, int b, int c) {
static const char * const ret[] = {"Boo.", "Yay."};
static const int table[2][2][2] = {{{0,0},{0,0}},{{0,0},{0,1}}};
return table[!!a][!!b][!!c][ret];
}

int main(void) {
puts(func(0, 0, 0));
puts(func(0, 0, 3));
puts(func(0, 5, 0));
puts(func(0, 7, 11));
puts(func(13, 0, 0));
puts(func(17, 0, 1));
puts(func(19, 23, 0));
puts(func(29, 31, 37));
return 0;
}

Stefan Ram
Guest
Posts: n/a

 05-27-2011
Eric Sosman <(E-Mail Removed)> writes:
>You've chosen the wrong implementation language.

Or the wrong newsgroup.

In C, however, sometimes, we can replace branching code with
non-branching code, e.g., under certain circumstances:

a += b ? c : d;

by

a += b * c +( 1 - b )*d;

Stefan Ram
Guest
Posts: n/a

 05-27-2011
Billy Mays <(E-Mail Removed)> writes:
>On 5/26/2011 3:32 PM, Stefan Ram wrote:
>> Billy Mays<(E-Mail Removed)> writes:
>>>if(a&& b&& c) {

>>if(a)if(b)if(c)

>I believe this will work, thanks!

It was just intented to be equivalent, so it should
not work better nor worse than the original.

Seebs
Guest
Posts: n/a

 05-27-2011
On 2011-05-27, Eric Sosman <(E-Mail Removed)> wrote:
> 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.

While this is true, I've seen some cleverness. One of the geo random
number generators replaced:
if (x) {
y += z;
}
with
y += (z * x);
(where x was necessarily 0 or 1) and got a VERY noticeable performance
improvement.

That is generally the path to take for stuff like this, if your compiler
isn't clever enough to do what you mean. (In particular, a compiler which
produces multiple branches in the absence of side effects is not thinking
as clearly as it should, on a system where branches are expensive.)

-s
--
Copyright 2011, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

Keith Thompson
Guest
Posts: n/a

 05-27-2011
Billy Mays <(E-Mail Removed)> writes:
> 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!

You do? The point was to avoid differing branches depending on
differing values of a, b, and c. In the if() form, the branches are,
in some sense, even more explicit than in the && form.

The problem is that the C language defines *behavior*, and you're trying
to control the manner in which that behavior is created, i.e., the
sequence of machine-level operations. There's no 100% reliable way to
do that.

Of course you're going to have *some* inconsistent branching; depending
on the values of a, b, and c, each thread will or will not execute the
body of the if statement. So you're trying to minimize the possible
differences in branching.

I think your best bet is probably to try a few possible solutions and
examine the generated assembly or machine language for each one. If the
compiler knows that branching is expensive, it might optimize
if (a && b && c)
into straight-line code. That's assuming b and c have no side effects,
which you can guarantee by storing their values in temporary variables.

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

Nobody
Guest
Posts: n/a

 05-27-2011
On Thu, 26 May 2011 21:34:24 -0400, Billy Mays wrote:

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

OpenCL may be closer to C than e.g. GLSL, but it still isn't C. And even
if it was, C doesn't define the execution time of any given construct, nor
treat it as significant (i.e. a compiler make whatever optimisations it
likes so long as the code produces the correct result, regardless of the
effect upon execution time).

AFAICT, the only reliable way to prevent short-circuting is to either
ensure that the later expressions have side-effects such that
short-circuiting would change the observable behaviour, or to "hide" their
implementation in a different translation unit so that the compiler cannot
determine whether short-circuiting will change the observable behaviour.

Either approach is likely to impose an unnecessary performance penalty on
either or both implementations (CPU and GPU). I don't know whether the
latter approach is even possible for OpenCL.

Actually, with modern CPUs performing speculative execution, I'm not sure
that the "hiding" approach will work. If the CPU hasn't performed the
calculation by the time it discovers that the result isn't needed, it
will just cancel it.

Shao Miller
Guest
Posts: n/a

 05-27-2011
On 5/27/2011 02:38, Keith Thompson wrote:
> Billy Mays<(E-Mail Removed)> writes:
>> 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!

>
> You do? The point was to avoid differing branches depending on
> differing values of a, b, and c. In the if() form, the branches are,
> in some sense, even more explicit than in the&& form.
>

Agreed. I don't understand exactly what the original poster wants to
achieve, but my impression is that they want "lock-steppedness."

> The problem is that the C language defines *behavior*, and you're trying
> to control the manner in which that behavior is created, i.e., the
> sequence of machine-level operations. There's no 100% reliable way to
> do that.
>

Agreed. But one can make some educated guesses about the timing of
operations. In the table-using code I posted else-thread, if the 'func'
function is called with different arguments simultaneously, those
invocations should return the result simultaneously, barring external
interruptions. Of course, such a table strategy becomes unwieldy as
more parameters are required; heh.

> Of course you're going to have *some* inconsistent branching; depending
> on the values of a, b, and c, each thread will or will not execute the
> body of the if statement. So you're trying to minimize the possible
> differences in branching.
>
> I think your best bet is probably to try a few possible solutions and
> examine the generated assembly or machine language for each one.

Agreed. The 'gcc -save-temps' is handy for examining resulting '.s'
files. This shows that the table-using code doesn't have any branches
(excluding the function calls). Of course, 'gcc' mightn't be applicable
to the original poster's OpenCL needs.

Loops change timing, of course.

Keith Thompson
Guest
Posts: n/a

 05-27-2011
"Scott Fluhrer" <(E-Mail Removed)> writes:
> "Urist Sethkab" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> Wouldn't !(a | b | c) work, then?
>> (Not very experienced, so there could be some obvious reason why not
>> that I can't see)

>
> Well, it has a different meaning:
> a && b && c is true if the three variables are all non-zero
> !(a | b | c) is true if all three variables are zero

!(!a | !b | !c)

But this:

!!a & !!b & !!c

is probably clearer (though still, IMHO, not clear enough).

[...]

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