Re: Order of function evaluation
From: Chris Torek (nospam_at_elf.eng.bsdi.com)
Date: 10/25/03
- Next message: Tom Potter: "Re: Fundamental Reason for High Achievements of Jews"
- Previous message: Allin Cottrell: "Re: array size"
- In reply to: Glen Herrmannsfeldt: "Re: Order of function evaluation"
- Next in thread: Glen Herrmannsfeldt: "Re: Order of function evaluation"
- Reply: Glen Herrmannsfeldt: "Re: Order of function evaluation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 24 Oct 2003 21:04:39 -0600
In article <uckmb.9426$9E1.44563@attbi_s52>
Glen Herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>I am not at all sure what optimizers are allowed to do.
The short version is "anything you cannot tell they have done,
other than by the fact that your program runs faster". :-)
There is a constraint on this, however: you must write code that
conforms to the appropriate standard (one of the C or Fortran
standards). Suppose you write code that the standard says has
"undefined behavior", and the compiler assumes that you have
not written such code. The optimizer in the compiler is allowed
to run with this assumption and make changes that *are* visible
(other than in terms of execution time). This is, in effect,
"your fault" and not the "compiler's fault".
>At least in Fortran there once was a traditional optimization of
>moving invariant expressions out of loops. ...
This is a typical optimization in any compiled, imperative language.
The theory is that loops -- especially inner loops, when loops are
nested -- contain code that will be run quite a bit, so if there is
some way to move some computation outside the loop and run it just
once, instead of every time, that should help a lot. Another
technique is "strength reduction", in which a "strong" operation
(like a multiplication) is "reduced" to an equivalent "weaker" one
(such as repeated addition) that should go faster:
for i in [0..N1) do
for j in [0..N2) do
op(arr[i;j])
The subscript operation here may (depending on the language) involve
multiplication, but the result will be the sequence {0,4,8,12,16,...}
or some such. Instead of doing a multiply, the two loops can be
replaced with something like:
for ix in [0..N1 * N2) do
op(arr{reinterpreted as one-dimensional}[ix])
which might translate to (non-portable, because the array subscripts
are out of bounds, but the compiler can do it simply by changing the
bounds it applies) C as:
for (ix = 0, iy = N1 * N2; ix < iy; ix++)
op(arr[0][ix])
>One favorite example from Fortran, but translated to C goes something like:
>
>for(i=0;i<n;i++) {
> if(a>0) b[i] *= sqrt(a);
> c[i] *= a;
> }
>
>There were compilers that would evaluate sqrt(a) outside the loop, keep the
>result in a register and use it in the multiply.
C compilers can do this too, because the name sqrt() is reserved
to the implementation, and the compiler can recognize the call.
It gets hairy around the edges though, because if "a" is negative,
each (removed) call to sqrt() must (at least appear to) set errno
to EDOM. (The compiler can hoist the errno-setting if it can prove
that errno is not changed elsewhere in the loop, or move it below
the loop, or even remove it entirely, if it can prove that errno
is not examined. And of course, the problem never comes up if the
compiler can prove that a >= 0.)
>Function calls don't tend to allow that optimization in general, though.
Any function that is known to be a "pure" function -- that is, one
free of "side effects" -- can be hoisted out of a loop. (Indeed,
any "loop invariant" can be so treated. Optimizers thus spend a
lot of effort finding such invariants.) In languages that eliminate
side effects entirely, such as typical functional programming
languages, the test "is function F a pure function" is trivial.
In C, programmers can never declare their functions pure, but in
C99, programmers can expose the entire contents of the function
via the new "inline" keyword, and the compiler can try to figure
this out for itself. In GNUC -- a language almost but not entirely
unlike C [ok, actually a lot like C, and apologies to Douglas Adams
:-) ] -- programmers can use the horrible __attribute__ syntax to
declare a function "pure". Implementors writing their own
implementations know which functions are pure (e.g., strlen(),
provided the contents of the buffer on which it is operating also
remain unchanged) are pure and which are not (e.g., rand() and
strtok()).
In C, however, even knowing that something *is* a pure function is
not always sufficient. The strlen() case is a good example. Just
because strlen("abc") is always 3 does not mean that:
void f(char *p1, char *p2) {
size_t i;
for (i = 0; i < strlen(p1); i++)
do_something(p2[i]);
}
can have its loop transformed into:
for (i = 0, lim = strlen(p1); i < lim; i++)
In particular, if do_something() has access to the same pointer
value stored in p1 in f(), it could modify p1[k] (for some valid
k), changing the result of strlen() partway through the loop. We
need to know that the contents of p1[k] never changes. The "const"
qualifier in C, which sounds like it should mean "constant", does
not do the trick: it is just a promise -- not even an enforceable
one, thanks to casts -- that the programmer will not modify p1[k]
using the variable named "p1". If do_something() has a
non-const-qualified "char *p3" that has the same value as p1, and
do_something writes on p3[k], this (visibly) changes p1[k] as well.
C99 adds a "restrict" qualifier that does the trick (using a rather
large hammer, as it were). Fortran escapes the problem by effectively
declaring *all* array parameters as "restrict"ed, in C99 terms.
Functional programming languages generally escape it by not having
(user-visible) pointers in the first place. :-)
Of course, in any programming language, the programmer can hoist
loop invariants "manually", as it were. If the programmer knows
that strlen(p1) is not going to -- or even just "not supposed to"
-- change inside the loop, the programmer can add a loop-limit
variable and write "i < lim" instead of "i < strlen(p1)". One
difference between C and most other compiled languages here is that
many or even most of C's abstractions are typically quite a bit
"closer to the machine", as it were, and an experienced C programmer
can often tell not only which expressions are invariant, but also
which ones the compiler will fail to discover for itself. But this
can cut both ways: C programmers sometimes tend to do too much of
this, and not enough algorithmic replacement. Or they may have
experience with only one (or a few) machines, and assume too much
about the C standard's virtual machine. (Pointer conversions, to
take just one example, are actually *conversions*, and result in
new and different bit patterns on some hardware, even though many
modern machines have only one pointer format and hence implement
pointer casts with no actual machine instructions.)
-- In-Real-Life: Chris Torek, Wind River Systems Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603 email: forget about it http://67.40.109.61/torek/index.html (for the moment) Reading email is like searching for food in the garbage, thanks to spammers.
- Next message: Tom Potter: "Re: Fundamental Reason for High Achievements of Jews"
- Previous message: Allin Cottrell: "Re: array size"
- In reply to: Glen Herrmannsfeldt: "Re: Order of function evaluation"
- Next in thread: Glen Herrmannsfeldt: "Re: Order of function evaluation"
- Reply: Glen Herrmannsfeldt: "Re: Order of function evaluation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
