Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #4812 > unrolled thread

Short-circuiting in C

Back to article view | Back to comp.lang.c

Contents

  Short-circuiting in C Billy Mays <noway@nohow.com> - 2011-05-26 13:58 -0400
    Re: Short-circuiting in C Ben Pfaff <blp@cs.stanford.edu> - 2011-05-26 11:09 -0700
      Re: Short-circuiting in C Thomas Richter <thor@math.tu-berlin.de> - 2011-05-26 20:22 +0200
        Re: Short-circuiting in C Ben Pfaff <blp@cs.stanford.edu> - 2011-05-26 11:35 -0700
          Re: Short-circuiting in C falk@rahul.net (Edward A. Falk) - 2011-05-31 18:45 +0000
            Re: Short-circuiting in C Nizumzen <chicken@mcnuggets.com> - 2011-05-31 20:31 +0100
        Re: Short-circuiting in C Billy Mays <noway@nohow.com> - 2011-05-26 14:51 -0400
          Re: Short-circuiting in C Billy Mays <noway@nohow.com> - 2011-05-26 15:10 -0400
            Re: Short-circuiting in C Billy Mays <noway@nohow.com> - 2011-05-26 21:35 -0400
              Re: Short-circuiting in C Keith Thompson <kst-u@mib.org> - 2011-05-26 23:38 -0700
                Re: Short-circuiting in C Shao Miller <sha0.miller@gmail.com> - 2011-05-27 09:28 -0400
            Re: Short-circuiting in C falk@rahul.net (Edward A. Falk) - 2011-05-31 19:01 +0000
              Re: Short-circuiting in C falk@rahul.net (Edward A. Falk) - 2011-05-31 19:02 +0000
          Re: Short-circuiting in C Keith Thompson <kst-u@mib.org> - 2011-05-26 12:55 -0700
            Re: Short-circuiting in C Billy Mays <noway@nohow.com> - 2011-05-26 16:17 -0400
              Re: Short-circuiting in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-26 21:28 -0400
                Re: Short-circuiting in C Seebs <usenet-nospam@seebs.net> - 2011-05-27 05:06 +0000
                Re: Short-circuiting in C Noob <root@127.0.0.1> - 2011-05-27 17:48 +0200
                  Re: Short-circuiting in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-27 21:31 -0400
                Re: Short-circuiting in C blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-05-28 03:28 +0000
                  Re: Short-circuiting in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-27 23:43 -0400
                    Re: Short-circuiting in C blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-05-28 19:31 +0000
                    Re: Short-circuiting in C Michael Press <rubrum@pacbell.net> - 2011-05-30 00:28 -0700
                      Re: Short-circuiting in C BGB <cr88192@hotmail.com> - 2011-05-30 23:08 -0700
                        Re: Short-circuiting in C Michael Press <rubrum@pacbell.net> - 2011-05-31 18:30 -0700
                          Re: Short-circuiting in C BGB <cr88192@hotmail.com> - 2011-06-02 09:08 -0700
                  Re: Short-circuiting in C Nobody <nobody@nowhere.com> - 2011-05-28 14:08 +0100
                    Re: Short-circuiting in C BGB <cr88192@hotmail.com> - 2011-05-28 12:52 -0700
                Re: Short-circuiting in C falk@rahul.net (Edward A. Falk) - 2011-05-31 19:22 +0000
                  Re: Short-circuiting in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-31 21:07 -0400
                    Re: Short-circuiting in C Dr Nick <3-nospam@temporary-address.org.uk> - 2011-06-11 17:07 +0100
                      Re: Short-circuiting in C Shao Miller <sha0.miller@gmail.com> - 2011-06-11 12:57 -0500
    Re: Short-circuiting in C "Morris Keesan" <mkeesan@post.harvard.edu> - 2011-05-26 14:36 -0400
    Re: Short-circuiting in C "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-05-26 14:39 -0400
      Re: Short-circuiting in C Keith Thompson <kst-u@mib.org> - 2011-05-26 13:28 -0700
        Re: Short-circuiting in C Urist Sethkab <uristqwerty@gmail.com> - 2011-05-26 15:34 -0700
          Re: Short-circuiting in C "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-05-27 10:08 -0400
            Re: Short-circuiting in C Keith Thompson <kst-u@mib.org> - 2011-05-27 07:56 -0700
            Re: Short-circuiting in C Geoff <geoff@invalid.invalid> - 2011-05-27 20:14 -0700
              Re: Short-circuiting in C Keith Thompson <kst-u@mib.org> - 2011-05-27 20:26 -0700
                Re: Short-circuiting in C Geoff <geoff@invalid.invalid> - 2011-05-27 20:44 -0700
    Re: Short-circuiting in C Nobody <nobody@nowhere.com> - 2011-05-27 00:06 +0100
      Re: Short-circuiting in C Billy Mays <noway@nohow.com> - 2011-05-26 21:34 -0400
        Re: Short-circuiting in C Nobody <nobody@nowhere.com> - 2011-05-27 07:41 +0100
    Re: Short-circuiting in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-26 21:21 -0400
    Re: Short-circuiting in C Shao Miller <sha0.miller@gmail.com> - 2011-05-26 20:41 -0500
      Re: Short-circuiting in C Shao Miller <sha0.miller@gmail.com> - 2011-05-26 21:03 -0500
        Re: Short-circuiting in C Shao Miller <sha0.miller@gmail.com> - 2011-05-26 21:37 -0500
    Re: Short-circuiting in C ImpalerCore <jadill33@gmail.com> - 2011-05-27 09:01 -0700
      Re: Short-circuiting in C Willem <willem@toad.stack.nl> - 2011-05-27 16:08 +0000
        Re: Short-circuiting in C ImpalerCore <jadill33@gmail.com> - 2011-05-27 09:46 -0700
          Re: Short-circuiting in C BGB <cr88192@hotmail.com> - 2011-05-28 13:27 -0700
    Re: Short-circuiting in C James Kuyper <jameskuyper@verizon.net> - 2011-05-28 09:44 -0400
      Re: Short-circuiting in C Keith Thompson <kst-u@mib.org> - 2011-05-28 12:15 -0700
        Re: Short-circuiting in C James Kuyper <jameskuyper@verizon.net> - 2011-05-28 17:07 -0400
    Re: Short-circuiting in C "Herbert Rosenau" <os2guy@pc-rosenau.de> - 2011-05-29 07:25 +0000
    Re: Short-circuiting in C falk@rahul.net (Edward A. Falk) - 2011-05-31 18:40 +0000
      Re: Short-circuiting in C BGB <cr88192@hotmail.com> - 2011-06-02 09:48 -0700
        Re: Short-circuiting in C Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-02 21:05 -0400

Page 1 of 3  [1] 2 3  Next page →

#4812 — Short-circuiting in C

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

[toc] | [next] | [standalone]

#4814

Billy Mays <noway@nohow.com> 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

[toc] | [prev] | [next] | [standalone]

#4818

On 26.05.2011 20:09, Ben Pfaff wrote:
> Billy Mays<noway@nohow.com>  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

[toc] | [prev] | [next] | [standalone]

#4820

Thomas Richter <thor@math.tu-berlin.de> writes:

> On 26.05.2011 20:09, Ben Pfaff wrote:
>> Billy Mays<noway@nohow.com>  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

[toc] | [prev] | [next] | [standalone]

#5136

In article <87hb8htims.fsf@blp.benpfaff.org>,
Ben Pfaff  <blp@cs.stanford.edu> wrote:
>Thomas Richter <thor@math.tu-berlin.de> writes:
>
>>> x = a;
>>> y = b;
>>> z = c;
>>> if (x&&  y&&  z) {
>>>      /* Do stuff */
>>> }
>>
>The code that I presented always evaluates all of 'a', 'b', and
>'c', which is what the OP said that he wanted.

A sufficiently smart compiler would realize that if y and z have no
side-effects, then their computation can be deferred until they're needed.
The above code would be optimized back to the original.

Now if y and z do have side-effects, then this would indeed generate
different code, forcing them to be evaluated when they might not have
been in the original.

Note that OP wanted to force evaluation of y and z in order to remove
some expensive branches.  However, I think that any analysis would show
that the branches are cheaper than evaluating y and z in almost all cases.

-- 
	-Ed Falk, falk@despams.r.us.com
	http://thespamdiaries.blogspot.com/

[toc] | [prev] | [next] | [standalone]

#5144

On 2011-05-31 19:45:55 +0100, Edward A. Falk said:
> 
> Note that OP wanted to force evaluation of y and z in order to remove
> some expensive branches.  However, I think that any analysis would show
> that the branches are cheaper than evaluating y and z in almost all cases.

Not on a GPU.

Branching on a GPU kills everything. Don't do it unless you really, 
really, really need too.

Although this begs the question why he is using C as both OpenCL and 
CUDA have their own C like languages for handling the code that 
actually runs on the GPU neither of which follows C's rules exactly as 
far as I am aware (most likely for this very reason).

[toc] | [prev] | [next] | [standalone]

#4823

On 05/26/2011 02:22 PM, Thomas Richter wrote:
> On 26.05.2011 20:09, Ben Pfaff wrote:
>> Billy Mays<noway@nohow.com> 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

[toc] | [prev] | [next] | [standalone]

#4829

On 05/26/2011 03:03 PM, Stefan Ram wrote:
> Billy Mays<noway@nohow.com>  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

[toc] | [prev] | [next] | [standalone]

#4855

On 5/26/2011 3:32 PM, Stefan Ram wrote:
> Billy Mays<noway@nohow.com>  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

[toc] | [prev] | [next] | [standalone]

#4866

Billy Mays <noway@nohow.com> writes:
> On 5/26/2011 3:32 PM, Stefan Ram wrote:
>> Billy Mays<noway@nohow.com>  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) kst-u@mib.org  <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"

[toc] | [prev] | [next] | [standalone]

#4875

On 5/27/2011 02:38, Keith Thompson wrote:
> Billy Mays<noway@nohow.com>  writes:
>> On 5/26/2011 3:32 PM, Stefan Ram wrote:
>>> Billy Mays<noway@nohow.com>   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.

[toc] | [prev] | [next] | [standalone]

#5140

In article <irm8kv$hgm$1@speranza.aioe.org>,
Billy Mays  <noway@nohow.com> wrote:
>
>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.

Wow.  I'm curious as to what GPU this is, and what compiler you're
using that takes advantage of this.

<woolgathering>
I worked on Sun's "Majik" architecture (I may have the spelling wrong)
back in the day.  It effectively had four 32-bit cpus, running in tandem.
The first cpu was more general-purpose than the other three, and had a full
set of control and branch instructions.  The other three could only do
arithmetic, and operated in lock-step with the primary cpu.

If the calculations of a, b, and c in the original code were all
identical, then the compiler would typically arrange for them to
be computed in parallel and the three secondary cpus and the results
combined at the end.  I wouldn't really call these separate threads,
but they were definitely parallel computations.
</woolgathering>

Sounds like you're describing some sort of similar vector processor,
in which case, yes, I see why you would want the compiler to
compile (a && b && c) without short-circuiting.

Of course, a sufficiently smart compiler would recognize that b and c can
be computed without harm even if their values wouldn't be needed after
all.

Have you actually compiled your code and determined that the compiler
is not using parallelism?

-- 
	-Ed Falk, falk@despams.r.us.com
	http://thespamdiaries.blogspot.com/

[toc] | [prev] | [next] | [standalone]

#5141

In article <is3dtk$cp1$4@blue.rahul.net>,
Edward A. Falk <falk@rahul.net> wrote:
>
>Sounds like you're describing some sort of similar vector processor,
>in which case, yes, I see why you would want the compiler to
>compile (a && b && c) without short-circuiting.

Ahh, never mind.  Saw your other post.  I guessed right.

-- 
	-Ed Falk, falk@despams.r.us.com
	http://thespamdiaries.blogspot.com/

[toc] | [prev] | [next] | [standalone]

#4833

Billy Mays <noway@nohow.com> writes:
> On 05/26/2011 02:22 PM, Thomas Richter wrote:
>> On 26.05.2011 20:09, Ben Pfaff wrote:
>>> Billy Mays<noway@nohow.com> 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) kst-u@mib.org  <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"

[toc] | [prev] | [next] | [standalone]

#4834

On 05/26/2011 03:55 PM, Keith Thompson wrote:
> Billy Mays<noway@nohow.com>  writes:
>> On 05/26/2011 02:22 PM, Thomas Richter wrote:
>>> On 26.05.2011 20:09, Ben Pfaff wrote:
>>>> Billy Mays<noway@nohow.com>  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

[toc] | [prev] | [next] | [standalone]

#4853

On 5/26/2011 4:17 PM, Billy Mays wrote:
> On 05/26/2011 03:55 PM, Keith Thompson wrote:
>> Billy Mays<noway@nohow.com> writes:
>>> On 05/26/2011 02:22 PM, Thomas Richter wrote:
>>>> On 26.05.2011 20:09, Ben Pfaff wrote:
>>>>> Billy Mays<noway@nohow.com> 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
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#4865

On 2011-05-27, Eric Sosman <esosman@ieee-dot-org.invalid> 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 / usenet-nospam@seebs.net
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.

[toc] | [prev] | [next] | [standalone]

#4879

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

How about changing

  if (a && b && c)

into

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

This will always evaluate a, b, and c (in an unspecified order).

[toc] | [prev] | [next] | [standalone]

#4889

On 5/27/2011 11:48 AM, Noob wrote:
> Eric Sosman 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.
>
> How about changing
>
>    if (a&&  b&&  c)
>
> into
>
>    if ((a != 0)&  (b != 0)&  (c != 0))
>
> This will always evaluate a, b, and c (in an unspecified order).

     Unspecified, yes.  Simultaneously, no.  Even if a particular
implementation finds it can run each `x != 0' (or each `x' and
each `0', for that matter) in parallel, I repeat: C has no way to
express a requirement for parallelism.

     If you think C has such expressive power, pray exhibit some
fragment of C that *requires* parallel execution (other than hand-
waving about `volatile' variables and asynchronous signals, already
mentioned up-thread and dismissed as not germane to the O.P.'s wish).

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#4894

In article <irmuo5$u9t$1@dont-email.me>,
Eric Sosman  <esosman@ieee-dot-org.invalid> wrote:
> On 5/26/2011 4:17 PM, Billy Mays wrote:
> > On 05/26/2011 03:55 PM, Keith Thompson wrote:
> >> Billy Mays<noway@nohow.com> writes:
> >>> On 05/26/2011 02:22 PM, Thomas Richter wrote:
> >>>> On 26.05.2011 20:09, Ben Pfaff wrote:
> >>>>> Billy Mays<noway@nohow.com> 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.

Hesitant though I am to argue with someone who generally seems
far more expert than I am ....

I don't get the impression at all that the OP wants a, b, and
c evaluated in parallel.  As I understand it, he just wants to
be sure that there is no branching involved in the evaluation
of the condition (a && b && c).  I admit I don't have a clear
understanding of the platform he's targeting, but it sounds like
it somehow involves multiple processing elements [*] executing the
same compiled code, and under those circumstances I can vaguely
imagine that performance might be better if all these processing
elements execute exactly the same instructions (i.e., no branches).

[*] The ones that put the "MD" in "SIMD" is what I'm thinking here,
though admittedly not with as much clarity as I might like.

-- 
B. L. Massingill
ObDisclaimer:  I don't speak for my employers; they return the favor.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web