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 2 of 3 — ← Prev page 1 [2] 3  Next page →

#4896

On 5/27/2011 11:28 PM, blmblm@myrealbox.com wrote:
> In article<irmuo5$u9t$1@dont-email.me>,
> 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.
>
> Hesitant though I am to argue with someone who generally seems
> far more expert than I am ....

     "My blushes, Watson."  (And don't be too awed by my expertise;
the only reason I'm in the top ten of this group -- on good days --
is that the top twenty have stopped posting.)

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

     He didn't say anything about parallel execution at first, which
is why I gave a rather different response on the initial go-around.
But later he wrote that "On the GPU I am using, threads execute
simultaneously [provided...]," and I understood that as a request for
a C construct that expresses the "provided" and guarantees parallel
execution.  C has conditional constructs that may (*may*) involve no
branches, given smooth seas and a following wind, but has nothing that
can guarantee or even talk about parallel execution, leaving aside
signals and volatiles.

     'course, it's possible I've misunderstood the O.P. or blundered
in some other way, and will be summarily drummed out of the top ten.
Again.  (Anybody recall the Brain Trust of the TV series "Scrubs?"
Them's my guys ...)

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

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

#4925

In article <irpr4j$q20$1@dont-email.me>,
Eric Sosman  <esosman@ieee-dot-org.invalid> wrote:
> On 5/27/2011 11:28 PM, blmblm@myrealbox.com wrote:
> > In article<irmuo5$u9t$1@dont-email.me>,
> > 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.
> >
> > Hesitant though I am to argue with someone who generally seems
> > far more expert than I am ....
> 
>      "My blushes, Watson."  (And don't be too awed by my expertise;
> the only reason I'm in the top ten of this group -- on good days --
> is that the top twenty have stopped posting.)

Well, all right, if that's too much flattery, how about

s/far more expert than I am/very clueful/ 

?

> > 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.
> 
>      He didn't say anything about parallel execution at first, which
> is why I gave a rather different response on the initial go-around.
> But later he wrote that "On the GPU I am using, threads execute
> simultaneously [provided...]," and I understood that as a request for
> a C construct that expresses the "provided" and guarantees parallel
> execution.  

I think what I'm not getting is why you're interpreting his words as
a request to have *a, b, and c* evaluated ....  

Oh, maybe we're talking at cross purposes here!  I understand you to
be saying that he wants the three parts of the conditional executed
concurrently, presumably each in its own thread, and that's what
didn't/doesn't make sense to me.

But maybe in fact you're asking about how he hopes to have multiple
threads concurrently evaluating the whole expression (a && b && c)?
Now *that* would at least make sense as something one might want the
program to do.

But in general I understand him to be saying that the parallelism
(multiple threads operating concurrently, each evaluating the whole
expression) is being provided by some other part of the platform,
and he just wants to know how to come up with an expression whose
evaluation doesn't involve branching.  That seems to me to be entirely
topical for this group and something one might want to do for other
reasons (such as improved performance on a platform where any kind
of branching is slow), though admittedly some of those alleged reasons
might be ill-advised.

> C has conditional constructs that may (*may*) involve no
> branches, given smooth seas and a following wind, but has nothing that
> can guarantee or even talk about parallel execution, leaving aside
> signals and volatiles.

Sure, but I don't think that's what he's asking ....  

>      'course, it's possible I've misunderstood the O.P. or blundered
> in some other way, and will be summarily drummed out of the top ten.
> Again.  (Anybody recall the Brain Trust of the TV series "Scrubs?"
> Them's my guys ...)

No room for error, eh?  :-)?

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

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

#5038

In article <irpr4j$q20$1@dont-email.me>,
 Eric Sosman <esosman@ieee-dot-org.invalid> wrote:

> On 5/27/2011 11:28 PM, blmblm@myrealbox.com wrote:
> > In article<irmuo5$u9t$1@dont-email.me>,
> > 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.
> >
> > Hesitant though I am to argue with someone who generally seems
> > far more expert than I am ....
> 
>      "My blushes, Watson."  (And don't be too awed by my expertise;
> the only reason I'm in the top ten of this group -- on good days --
> is that the top twenty have stopped posting.)
> 
> > 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.
> 
>      He didn't say anything about parallel execution at first, which
> is why I gave a rather different response on the initial go-around.
> But later he wrote that "On the GPU I am using, threads execute
> simultaneously [provided...]," and I understood that as a request for
> a C construct that expresses the "provided" and guarantees parallel
> execution.  C has conditional constructs that may (*may*) involve no
> branches, given smooth seas and a following wind, but has nothing that
> can guarantee or even talk about parallel execution, leaving aside
> signals and volatiles.
> 
>      'course, it's possible I've misunderstood the O.P. or blundered
> in some other way, and will be summarily drummed out of the top ten.
> Again.  (Anybody recall the Brain Trust of the TV series "Scrubs?"
> Them's my guys ...)

I have two coins worth thirty cents total. 
One of them is not a nickel.

-- 
Michael Press

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

#5085

On 5/30/2011 12:28 AM, Michael Press wrote:
> In article<irpr4j$q20$1@dont-email.me>,
>   Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>
>> On 5/27/2011 11:28 PM, blmblm@myrealbox.com wrote:
>>> In article<irmuo5$u9t$1@dont-email.me>,
>>> 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.
>>>
>>> Hesitant though I am to argue with someone who generally seems
>>> far more expert than I am ....
>>
>>       "My blushes, Watson."  (And don't be too awed by my expertise;
>> the only reason I'm in the top ten of this group -- on good days --
>> is that the top twenty have stopped posting.)
>>
>>> 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.
>>
>>       He didn't say anything about parallel execution at first, which
>> is why I gave a rather different response on the initial go-around.
>> But later he wrote that "On the GPU I am using, threads execute
>> simultaneously [provided...]," and I understood that as a request for
>> a C construct that expresses the "provided" and guarantees parallel
>> execution.  C has conditional constructs that may (*may*) involve no
>> branches, given smooth seas and a following wind, but has nothing that
>> can guarantee or even talk about parallel execution, leaving aside
>> signals and volatiles.
>>
>>       'course, it's possible I've misunderstood the O.P. or blundered
>> in some other way, and will be summarily drummed out of the top ten.
>> Again.  (Anybody recall the Brain Trust of the TV series "Scrubs?"
>> Them's my guys ...)
>
> I have two coins worth thirty cents total.
> One of them is not a nickel.
>

errm... "what is a quarter?...".

but, yeah, the GPU is weird that way, as it tends to execute things in 
parallel (rather than the more usual serial execution).

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

#5153

In article <is20q1$sbr$1@news.albasani.net>, BGB <cr88192@hotmail.com> 
wrote:

> On 5/30/2011 12:28 AM, Michael Press wrote:
> > In article<irpr4j$q20$1@dont-email.me>,
> >   Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:

[...]

> >>       'course, it's possible I've misunderstood the O.P. or blundered
> >> in some other way, and will be summarily drummed out of the top ten.
> >> Again.  (Anybody recall the Brain Trust of the TV series "Scrubs?"
> >> Them's my guys ...)
> >
> > I have two coins worth thirty cents total.
> > One of them is not a nickel.
> 
> errm... "what is a quarter?...".
> 
> but, yeah, the GPU is weird that way, as it tends to execute things in 
> parallel (rather than the more usual serial execution).

The riddle I recounted was used in a memorable
episode of _Scrubs_ featuring the Brain Trust.

-- 
Michael Press

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

#5285

On 5/31/2011 6:30 PM, Michael Press wrote:
> In article<is20q1$sbr$1@news.albasani.net>, BGB<cr88192@hotmail.com>
> wrote:
>
>> On 5/30/2011 12:28 AM, Michael Press wrote:
>>> In article<irpr4j$q20$1@dont-email.me>,
>>>    Eric Sosman<esosman@ieee-dot-org.invalid>   wrote:
>
> [...]
>
>>>>        'course, it's possible I've misunderstood the O.P. or blundered
>>>> in some other way, and will be summarily drummed out of the top ten.
>>>> Again.  (Anybody recall the Brain Trust of the TV series "Scrubs?"
>>>> Them's my guys ...)
>>>
>>> I have two coins worth thirty cents total.
>>> One of them is not a nickel.
>>
>> errm... "what is a quarter?...".
>>
>> but, yeah, the GPU is weird that way, as it tends to execute things in
>> parallel (rather than the more usual serial execution).
>
> The riddle I recounted was used in a memorable
> episode of _Scrubs_ featuring the Brain Trust.
>

ok. not seen that show...

would insert another random TV quote, except I can't think of much...
may as well then return to having nano-machines gather up Santa-knowledge...

results in picture of Jabba The Hut with a Santa hat:
"hooo... hooo... hooo... I be Santa Claus..."
little green thing: "te he he he he... Santa Claus...".

gives out a pizza...
"hooo... hooo... hooo... now I be Pizza Hut..."
...


or such...

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

#4907

On Sat, 28 May 2011 03:28:20 +0000, blmblm wrote:

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

I was (initially) under the impression that he wanted consistency between
CPU and GPU performance, and GPUs can't do short-circuit evaluation.

On a SIMD architecture (e.g. a GPU), you only have one program counter for
all processing units, so a branch where the test result can vary between
units cannot be implemented in the conventional manner (by modifying the
program counter). An if-else construct involves executing both branches on
all units; each unit ignores the instructions in one of the branches
depending upon whether the test is true or false on that particular unit.

OTOH, the OP may have just misunderstood what "branches are slow" means in
the context of GPU programming. They're slow in the sense that branching
over a set of instructions takes just as long as executing them. That
doesn't mean that tricks which eliminate branches will necessarily be any
faster.

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

#4930

On 5/28/2011 6:08 AM, Nobody wrote:
> On Sat, 28 May 2011 03:28:20 +0000, blmblm wrote:
>
>> 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).
>
> I was (initially) under the impression that he wanted consistency between
> CPU and GPU performance, and GPUs can't do short-circuit evaluation.
>
> On a SIMD architecture (e.g. a GPU), you only have one program counter for
> all processing units, so a branch where the test result can vary between
> units cannot be implemented in the conventional manner (by modifying the
> program counter). An if-else construct involves executing both branches on
> all units; each unit ignores the instructions in one of the branches
> depending upon whether the test is true or false on that particular unit.
>
> OTOH, the OP may have just misunderstood what "branches are slow" means in
> the context of GPU programming. They're slow in the sense that branching
> over a set of instructions takes just as long as executing them. That
> doesn't mean that tricks which eliminate branches will necessarily be any
> faster.
>

AFAIK, there may be a point of difference between nVidia and ATI GPUs 
here, where nVidia GPUs will in many cases skip over the non-evaluated 
code and ignore the instructions, and ATI GPUs will actually perform the 
branch, but typically go down only one side of the branch at a time 
(having different threads branch differently may mean first evaluating, 
say, all threads where the jump was true, followed by all branches where 
it was false, ...).

also, the GPUs are normally organized into a large number of "cores" 
which operate independently of each other, but each core may operate 
some number of threads in parallel, each thread in turn having to move 
in lock-step with the others.


granted, I am no particular expert on GPUs, and most of my personal 
experience has been with OpenGL and GLSL, rather than OpenCL and its 
modified C-subset (and, sadly, the inability to use function pointers 
would very much hinder many of my usual coding practices). I may use it 
eventually though.

I think I remember hearing at some point about projects trying to run 
both Java-ByteCode and ActionScript on the GPU as well, ...

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

#5143

In article <irmuo5$u9t$1@dont-email.me>,
Eric Sosman  <esosman@ieee-dot-org.invalid> wrote:
>
>     C has no way to express the computation you desire. ...

See my previous post.  OP is working with a cpu that doesn't
have multiple threads of execution, per se, but does have
parallel threads of computation.

Imagine:

	a = x1 * x2 + x3;
	b = y1 * y2 + y3;
	c = z1 * z2 + z3;

I've worked on a CPU that could compute those three expressions
in perfect parallel.  We made sure our compiler recognized cases
like this and optimized accordingly.

I think OP's problem is that the (a && b && c) short-circuiting
is preventing the compiler from computing those values in
parallel.  That's really a failure on the compiler's part, but
OP is hoping there's a way to hint to the compiler that
short-circuiting is not necessary.

And yes, without extending the language, there's no way to
*force* the compiler to compute that stuff in parallel.

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

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

#5152

On 5/31/2011 3:22 PM, Edward A. Falk wrote:
> In article<irmuo5$u9t$1@dont-email.me>,
> Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>>
>>      C has no way to express the computation you desire. ...
>
> See my previous post.  OP is working with a cpu that doesn't
> have multiple threads of execution, per se, but does have
> parallel threads of computation.

     C has no way to express "parallel threads of computation"
(except in the restrictive senses of volatile variables and
asynchronous signals).

> Imagine:
>
> 	a = x1 * x2 + x3;
> 	b = y1 * y2 + y3;
> 	c = z1 * z2 + z3;
>
> I've worked on a CPU that could compute those three expressions
> in perfect parallel.  We made sure our compiler recognized cases
> like this and optimized accordingly.

     Fine: Your compiler made promises that are not made by C and
are not expressible in C.  There's nothing preventing you from
making such promises, and in the right circumstances such promises
are useful and laudable.  But they're *your* promises, not C's,
and compilers other than your own are under no obligation to pay
the slightest heed to them.  C has no way to tell those other
compilers about a desire for parallelism, nor any means to detect
a promise broken.

> I think OP's problem is that the (a&&  b&&  c) short-circuiting
> is preventing the compiler from computing those values in
> parallel.  That's really a failure on the compiler's part, but
> OP is hoping there's a way to hint to the compiler that
> short-circuiting is not necessary.
>
> And yes, without extending the language, there's no way to
> *force* the compiler to compute that stuff in parallel.

     Exactly.  The O.P. needs something other than C, or something
in addition to C.

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

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

#5844

Eric Sosman <esosman@ieee-dot-org.invalid> writes:

> On 5/31/2011 3:22 PM, Edward A. Falk wrote:
>> In article<irmuo5$u9t$1@dont-email.me>,
>> Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>>>
>>>      C has no way to express the computation you desire. ...
>>
>> See my previous post.  OP is working with a cpu that doesn't
>> have multiple threads of execution, per se, but does have
>> parallel threads of computation.
>
>     C has no way to express "parallel threads of computation"
> (except in the restrictive senses of volatile variables and
> asynchronous signals).
>
>> Imagine:
>>
>> 	a = x1 * x2 + x3;
>> 	b = y1 * y2 + y3;
>> 	c = z1 * z2 + z3;
>>
>> I've worked on a CPU that could compute those three expressions
>> in perfect parallel.  We made sure our compiler recognized cases
>> like this and optimized accordingly.
>
>     Fine: Your compiler made promises that are not made by C and
> are not expressible in C.  There's nothing preventing you from
> making such promises, and in the right circumstances such promises
> are useful and laudable.  But they're *your* promises, not C's,
> and compilers other than your own are under no obligation to pay
> the slightest heed to them.  C has no way to tell those other
> compilers about a desire for parallelism, nor any means to detect
> a promise broken.
>
>> I think OP's problem is that the (a&&  b&&  c) short-circuiting
>> is preventing the compiler from computing those values in
>> parallel.  That's really a failure on the compiler's part, but
>> OP is hoping there's a way to hint to the compiler that
>> short-circuiting is not necessary.
>>
>> And yes, without extending the language, there's no way to
>> *force* the compiler to compute that stuff in parallel.
>
>     Exactly.  The O.P. needs something other than C, or something
> in addition to C.

To be fair, and I know I'm coming late to the party, the OP was asking
"is there a way to express what C usually does by a && b && c that
doesn't do the short-circuiting behaviour" and then explained why.  That
seemed an entirely reasonable question about C.  People suggested
several ways and all pointed out that this couldn't guarantee it (and
also that a really good compiler for his platform could cope with a && b
&& c in the way he wanted).
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

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

#5845

On 6/11/2011 11:07 AM, Dr Nick wrote:
>
> To be fair, and I know I'm coming late to the party, the OP was asking
> "is there a way to express what C usually does by a&&  b&&  c that
> doesn't do the short-circuiting behaviour" and then explained why.  That
> seemed an entirely reasonable question about C.  People suggested
> several ways and all pointed out that this couldn't guarantee it (and
> also that a really good compiler for his platform could cope with a&&  b
> &&  c in the way he wanted).

"Couldn't guarantee it" <- what is "it?"  Avoiding the short-circuiting 
behaviour?  Examples were given for constructs which evaluate all of 
'a', 'b', 'c' and then choose a path based on the truth of 'a && b && 
c', even though that expression is not used in the constructs.

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

#4821

On Thu, 26 May 2011 14:17:15 -0400, Stefan Ram <ram@zedat.fu-berlin.de>  
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:
>
>   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 -- mkeesan@post.harvard.edu

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

#4827

"Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message 
news:boolan-20110526201538@ram.dialup.fu-berlin.de...
> 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:
>
>  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 */
    }

-- 
poncho

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

#4836

"Scott Fluhrer" <sfluhrer@ix.netcom.com> writes:
> "Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message 
> news:boolan-20110526201538@ram.dialup.fu-berlin.de...
>> 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:
>>
>>  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) 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]

#4850

On May 26, 4:28 pm, Keith Thompson <ks...@mib.org> wrote:
> "Scott Fluhrer" <sfluh...@ix.netcom.com> writes:
> > "Stefan Ram" <r...@zedat.fu-berlin.de> wrote in message
> >news:boolan-20110526201538@ram.dialup.fu-berlin.de...
> >> Billy Mays <no...@nohow.com> 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) ks...@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"

Wouldn't !(a | b | c) work, then?
(Not very experienced, so there could be some obvious reason why not
that I can't see)

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

#4876

"Urist Sethkab" <uristqwerty@gmail.com> wrote in message 
news:b406e486-dafb-49d5-a9dd-5940f5e78965@a26g2000vbo.googlegroups.com...

> 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


On the other hand, if we assume a two's complement machine (and a, b, c are 
all the same integer type, so we don't have to worry about promotions), then 
the expression:

   (a | -a) & (b | -b) & (c | -c)

should work, and it would appear unlikely that a compiler will generate a 
conditional jump to evaluate it.  If none of the clearer expressions work 
for the OP's compiler, this might do it.

-- 
poncho

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

#4877

"Scott Fluhrer" <sfluhrer@ix.netcom.com> writes:
> "Urist Sethkab" <uristqwerty@gmail.com> wrote in message 
> news:b406e486-dafb-49d5-a9dd-5940f5e78965@a26g2000vbo.googlegroups.com...
>> 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) 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]

#4892

On Fri, 27 May 2011 10:08:58 -0400, "Scott Fluhrer"
<sfluhrer@ix.netcom.com> wrote:

>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

This looks suspiciously like De Morgan's theorem but the correct
expression of it would have been:

!(!a || !b || !c)

Why is everyone changing a logical operator into a bitwise operator
for this functionality without consideration for the values of the
operands?

If we take the OP at face value and say, "how to short-circuit the
evaluation" of:

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

It seems to me the correct answer is:

{
     /* Do stuff */
}

Because if multiple threads or parallel processors are expected to
operate unconditionally on chunks of data with the same chunk of code
regardless of the values of three input variables then there is no
reason to initially evaluate the variables because they won't
influence the order of execution.

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

#4893

Geoff <geoff@invalid.invalid> writes:
> On Fri, 27 May 2011 10:08:58 -0400, "Scott Fluhrer"
> <sfluhrer@ix.netcom.com> wrote:
>
>>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
>
> This looks suspiciously like De Morgan's theorem but the correct
> expression of it would have been:
>
> !(!a || !b || !c)
>
> Why is everyone changing a logical operator into a bitwise operator
> for this functionality without consideration for the values of the
> operands?

Not everyone is; most of us are specifically allowing for the
possibility of values other than 0 and 1.

> If we take the OP at face value and say, "how to short-circuit the
> evaluation" of:
>
> if(a && b && c) {
>      /* Do stuff */
> }
>
> It seems to me the correct answer is:
>
> {
>      /* Do stuff */
> }
>
> Because if multiple threads or parallel processors are expected to
> operate unconditionally on chunks of data with the same chunk of code
> regardless of the values of three input variables then there is no
> reason to initially evaluate the variables because they won't
> influence the order of execution.

I think the OP is trying to minimize branching, not eliminate it
altogether.  An ideal solution to his problem would be an operator
that acts like && except that it doesn't short-circuit (if C had
such an operator).  The branching implied by the "if" is unavoidable.

Hmm.

static inline int and(x, y) { return !!x & !!y; }

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

(untested)

On the other hand, the OP had said this code is running on a GPU,
and he's using a specialized compiler for a language very similar to
C, but not quite C.  It could be that others have run into similar
issue, and that the tools he's already using provide better solutions
than anything we C folks can come up with.

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

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

csiph-web