Re: Benefit of not defining the order of execution
- From: user923005 <dcorbit@xxxxxxxxx>
- Date: Mon, 16 Feb 2009 13:51:08 -0800 (PST)
On Feb 12, 8:40 pm, Han from China <autistic-pedan...@xxxxxxxxxxx>
wrote:
user923005 wrote:
Consider things like common subexpression elimination.
Consider things like:
y = a * (2*b + c) + a * (d * e - b) + a * f;
rewritten by the compiler as:
y = a * (b + c + d * e + f);
Even with a strict order of evaluation, the Rationale's "as if" rule would
still give the compiler such provisions for optimization.
In other words, given
y = a + b + c;
with a strict order of evaluation, the compiler may still be allowed to
reorder evaluation and rewrite expressions. The standard *does* provide
*some* helpful guarantees with the order of evaluation -- namely, that if
evaluating the above as
y = a + (b + c);
would produce a different result (such as with floating point arithmetic
in certain cases), then such "regrouping" is prohibited. This wasn't the
case with K&R C, where such "regrouping" was allowed. But ignoring those
pathological cases, we can see that a strict order of evaluation wouldn't
inhibit the compiler from evaluating c, then a, then b, then (b + c), then
a + (b + c) if it can get away with doing so.
I submit that this is impossible to achieve (IOW, it cannot be known
if a+(b+c)==(a+b)+c).
Allow me to expand:
Suppose that a,b,c are doubles and a is 2.0 and b and c are
DBL_EPSILON.
Then (a+b)+ c is 2.0, whereas a+(b+c) is larger than 2 by
DBL_EPSILON*2.
A strict order of evaluation would help only with expressions such
as
f() + g()
*if* there are clashing side-effects. Without clashing side-effects, there
would still be the "as if" rule, and so the compiler is at liberty to
evaluate g() before f().
On a related note, the "as if" rule allows the compiler to jump across
sequence points as well -- many forms of optimization depend on this
ability. My point is that imposing a strict order of evaluation and/or
throwing in more sequence points won't necessarily prohibit optimization.
That leads me to believe the decision to be loose on evaluation order may
have had more to do with, as Kenny says, codifying existing practice than
anything else.
The Rationale introduces what I believe to be a more helpful term for this
kind of discussion than "sequence points": "agreement points". The
Rationale describes agreement points as those points where the state of an
object in the actual machine agrees with the state of the object in the
abstract machine. Not all sequence points need be agreement points. It's
this fact that allows aggressive optimization.
C is not deterministic. Neither are Fortran, C++, Java or any other
language that I am familiar with.
It is a terrible mistake to imagine that they are deterministic or
even that you will get the same result from a computation if you
perform it twice with the same inputs.
For instance, some Intel chips have an 80 bit float register. Some
compilers will use this register if you ask them to. But if an
interrupt occurs, the bottom precision bits will get scrubbed off and
you will be left with 64 correct bits instead of 80.
Some compilers may have a mode to maximize reproducibility. For
instance, one compiler that I use has these options:
/fp:<except[-]|fast|precise|strict> choose floating-point model:
except[-] - consider floating-point exceptions when generating
code
fast - "fast" floating-point model; results are less predictable
precise - "precise" floating-point model; results are predictable
strict - "strict" floating-point model (implies /fp:except)
Here is a funny thing:
When you call a math function from your math library, it is *very*
unlikely to be correctly rounded unless you are using:
"CRlibm: a Library of Elementary Functions with Correct Rounding"
I do think that correctness is a very laudable goal. But it is also
important to consider that all floating point computations have a ball
of fuzz around them, no matter how careful we are.
It is usually a good idea to shrink the size of the ball of fuzz as
much as possbile. But it may be that it costs so much to shrink the
fuzzy ball that it would be much better to leave it alone.
For instance, we could perform all computations using MPFR with 1000
digits of precision. But to do a large matrix multiplication that way
may be so expensive (or consume so much memory) that it would be
infeasible. Or it could also be that our inputs into the system are
so imprecise that the 16 digits or so of our floating point pale in
comparison to the 5 digits of precision given in the inputs and
carrying out computations with extended precision would not buy us
anything.
Ideally, we want calculations that are fast, correct, and repeatable.
Sometimes, we have to compromise a bit to be able to perform the
operations at all (in fact all floating point computations are a
compromise since we cannot carry them out in infinite precision).
IMO-YMMV.
.
- References:
- Re: Benefit of not defining the order of execution
- From: user923005
- Re: Benefit of not defining the order of execution
- From: Han from China
- Re: Benefit of not defining the order of execution
- Prev by Date: Re: Look for open source C library for text manipulation
- Next by Date: Re: va_list * and function parameters?
- Previous by thread: Re: Benefit of not defining the order of execution
- Next by thread: Re: Benefit of not defining the order of execution
- Index(es):
Relevant Pages
|
