RE: short-circuit control forms

RE: short-circuit control forms

[Beard, Frank]

-----Original Message-----
From: James A. Krzyzanowski [mailto:James_A_Krzyzanowski@raytheon.com]

> Our software engineers believe that using short-circuit control forms
> will make our software more efficient (speed-wise).  So, they have been
> replacing every "and" with "and then" and every "or" with "or else".

I've heard this before, as well.  And it makes sense, unless there is
some problem or inefficiency with generating the underlying branch
statements.

It seems to me that the "and" and "or" should have been implemented
in the short circuit form to begin with, instead of requiring 
"and then" and "or else".  As soon as one of the conditions is FALSE
for "and" or TRUE for "or", there is no need to check the remaining
arguments.

Frank Beard

Re: RE: short-circuit control forms

[Ted Dennison]

In article <mailman.993066684.13202.comp.lang.ada@ada.eu.org>, Beard, Frank
says...
>"and then" and "or else".  As soon as one of the conditions is FALSE
>for "and" or TRUE for "or", there is no need to check the remaining
>arguments.

That's assuming the conditional expressions have no side-efects. Questions of
the wisdom of making boolean ops with side effects aside (and much of the Win32
API is implemented this way), it would be a very Bad Thing to go blindly
converting conditionals to the short circuit form in existing Ada code, without
first carefully analyzing the conditions to verify that things will still work
properly if the later condition doesn't get executed. 

I can't find anything in the LRM that says that compilers *can't* optimize away
unneeded conditions in the way you describe (any language lawyers in the
house?), but it wouldn't shock me to find loads of code that assumes it won't
happen. I'm not sure what the LRM's silence on a subject means in this case. But
assuming it means "all bets are off", then it looks to me like compilers are
perfectly free to short-circuit, or even reorder and short-circuit normal
conditional expressions.

--
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: short-circuit control forms

[Marin David Condic]

Consider the following:

if (Some_Boolean_Function (X) and then Another_Boolean_Function (Y)) then
    Do_Some_Stuff ;
end if ;

If the *first* function almost always evaluates to False, then you almost
never call the second function. This is efficient - a good thing sometimes.
However, if the second function sometimes generates a Constraint_Error
because of a programmer mistake, and it only sometimes gets called, you may
have an error condition that makes it out into the field - which is A Bad
Thing (tm).

Another consideration is timing. Nominally, you only call the first function
and not the second. In some corner cases, you call the second and this may
consume some excessive amount of time. It may blow the timing budget
altogether. Lots of hard realtime systems insist that you always execute the
worst-case path just to make sure this sort of thing doesn't happen. This is
the same reason why lots of realtime systems don't like cache on a chip - it
leads to non-deterministic behavior that you may not find until it is too
late.

Better to have the short-circuit things optional so you can manually enable
and disable the behavior as needed. Most of the time the extra efficiency is
likely to be a) too small to sweat and b) not an issue because it isn't a
hard realtime system.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Beard, Frank" <beardf@spawar.navy.mil> wrote in message
news:mailman.993066684.13202.comp.lang.ada@ada.eu.org...
> I've heard this before, as well.  And it makes sense, unless there is
> some problem or inefficiency with generating the underlying branch
> statements.
>
> It seems to me that the "and" and "or" should have been implemented
> in the short circuit form to begin with, instead of requiring
> "and then" and "or else".  As soon as one of the conditions is FALSE
> for "and" or TRUE for "or", there is no need to check the remaining
> arguments.

Re: short-circuit control forms

[Jeffrey Carter]

Ted Dennison wrote:
> 
> I can't find anything in the LRM that says that compilers *can't* optimize away
> unneeded conditions in the way you describe (any language lawyers in the
> house?), but it wouldn't shock me to find loads of code that assumes it won't
> happen. I'm not sure what the LRM's silence on a subject means in this case. But
> assuming it means "all bets are off", then it looks to me like compilers are
> perfectly free to short-circuit, or even reorder and short-circuit normal
> conditional expressions.

IANAL, nor do I play one on TV. However, "and" and "or" are normal
subprograms (you can overload them), and the semantics for subprograms
state that all actual parameters are evaluated, and the order of
evaluation is not specified by the language (ARM 6.4). Thus, it is
illegal for a compiler to convert them to short-circuit forms.

-- 
Jeffrey Carter

Re: short-circuit control forms

[Dale Stanbrough]

Ted Dennison wrote:

>  I'm not sure what the LRM's silence on a subject means in this case. But
> assuming it means "all bets are off", then it looks to me like compilers 
> are
> perfectly free to short-circuit, or even reorder and short-circuit normal
> conditional expressions.


The LRM guarentees order of execution for short circuit form, which is
from left to right.

Not all short circuit forms need be faster, this can depend on the 
architecture that is being compiled for. For example the following
code

   if x = 2 and y = 3 then

could have both comparisons scheduled on a modern processor with 
numerous integer units so that they occur simultaneously.

As always, measure before you optimise.

Dale

Re: short-circuit control forms

[Mark Lundquist]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3B312495.15258B18@boeing.com...
>
> IANAL, nor do I play one on TV. However, "and" and "or" are normal
> subprograms (you can overload them), and the semantics for subprograms
> state that all actual parameters are evaluated, and the order of
> evaluation is not specified by the language (ARM 6.4). Thus, it is
> illegal for a compiler to convert them to short-circuit forms.

I don't think that's correct...

The compiler can do whatever it wants, as long as it's equivalent [RM
1.1.3].

-- mark

Re: short-circuit control forms

[Keith Thompson]

"Beard, Frank" <beardf@spawar.navy.mil> writes:
[...]
> It seems to me that the "and" and "or" should have been implemented
> in the short circuit form to begin with, instead of requiring 
> "and then" and "or else".  As soon as one of the conditions is FALSE
> for "and" or TRUE for "or", there is no need to check the remaining
> arguments.

If I were designing a language from scratch, I might do something
like the following:

For an "and" operation, it's unspecified whether the right operand is
evaluated if the left operand is false.  It's also unspecified whether
the left operand is specified if the right operand is false.  Order of
evaluation is unspecified.  Side effects in either operand are
strongly discouraged.  Compilers should do whatever results in the
most efficient generated code.  Most code should use "and" unless
there's a good reason not to.

For an "and then" operation, the left operand is always evaluated; the
right operand is evaluted only if the left operand is true (just like
Ada's "and then").

Finally a third form would specify that both operands are always
evaluated (subject to optimization rules).  Perhaps something like
and(lhs, rhs).

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Cxiuj via bazo apartenas ni.

Re: short-circuit control forms

[Wes Groleau]

> IANAL, nor do I play one on TV. However, "and" and "or" are normal
> subprograms (you can overload them), and the semantics for subprograms
> state that all actual parameters are evaluated, and the order of
> evaluation is not specified by the language (ARM 6.4). Thus, it is
> illegal for a compiler to convert them to short-circuit forms.

However, the RM discussion of 'and' and 'or' implies that
redefined (overloaded) versions have different rules
than the "originals"

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: short-circuit control forms

[Jeffrey Carter]

Mark Lundquist wrote:
> 
> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> news:3B312495.15258B18@boeing.com...
> >
> > IANAL, nor do I play one on TV. However, "and" and "or" are normal
> > subprograms (you can overload them), and the semantics for subprograms
> > state that all actual parameters are evaluated, and the order of
> > evaluation is not specified by the language (ARM 6.4). Thus, it is
> > illegal for a compiler to convert them to short-circuit forms.
> 
> I don't think that's correct...
> 
> The compiler can do whatever it wants, as long as it's equivalent [RM
> 1.1.3].

Since preserving side effects is part of "equivalent", and deciding if
functions have side effects is "hard" (I'm not aware of any compilers
that do this), this is true in theory but irrelevant in practice. If a
function with a side effect is (part of) an operand of "and" or "or", a
compiler must generate code that calls the function. In real compilers,
that seems to mean that both operands are always evaluated. Is anyone
aware of a compiler that optimizes away evaluation of an operand to
"and" or "or" when neither operand has a function call? In cases where
one of the operands has a function call? Both operands?

As I said, IANAL. It would be nice to hear from Robert Duff, Tucker
Taft, or Robert Dewar about this.

-- 
Jeffrey Carter