jwp@larry.UUCP (Jeffrey W Percival) (02/14/89)
I have a question about how much optimizing I should worry about when writing programs in C. Suppose I have this code fragment: x = (1 + cos(r)) / (cos(r) * sin(r)); y = (cos(r) - sin(r)) / (1 + sin(r)); I made this up, but the point is the re-use of the sin() and cos() calls. Now, can I expect the compiler to form only one call to sin and cos? Specifically, I am using ULTRIX 2.1 on a VS2000, but my real question is, would *most* compilers optimize this as I'd hope, or *some* compilers, or hardly any? I guess I'm looking for a gut feeling on the general situation rather than in this specific example. If a function is used several times in a routine with an argument that doesn't get assigned to, is the result generally stashed somewhere? And what are the types of operations that interfere with an ongoing optimization, causing calls to be re-made rather than pulled from some stash? -- Jeff Percival (jwp@larry.sal.wisc.edu)
earleh@eleazar.dartmouth.edu (Earle R. Horton) (02/14/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: >I have a question about how much optimizing I should worry about when >writing programs in C. Suppose I have this code fragment: > > x = (1 + cos(r)) / (cos(r) * sin(r)); > y = (cos(r) - sin(r)) / (1 + sin(r)); > >I made this up, but the point is the re-use of the sin() and cos() >calls. Now, can I expect the compiler to form only one call to sin and >cos? No. The compiler has no way of knowing what sin() and cos() do, besides obviously returning a result. Either or both might have side effects, and optimizing out any of the calls prevents the side effects from happening. Earle R. Horton. 23 Fletcher Circle, Hanover, NH 03755--Graduate student. He who puts his hand to the plow and looks back is not fit for the kingdom of winners. In any case, 'BACK' doesn't work.
hascall@atanasoff.cs.iastate.edu (John Hascall) (02/14/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: >I have a question about how much optimizing I should worry about when >writing programs in C. Suppose I have this code fragment: > x = (1 + cos(r)) / (cos(r) * sin(r)); > y = (cos(r) - sin(r)) / (1 + sin(r)); >I made this up, but the point is the re-use of the sin() and cos() >calls. Now, can I expect the compiler to form only one call to sin and >cos? ... I think it will/should call the function each time it appears as the compiler has no way of knowing the "side-effects" of a function call (i.e., file operations, accessing global variables, etc). Imagine: x = (1 + printf(s)) / printf(s); y = printf(s) / (1 - printf(s)); (admittedly a hokey example--but you get the point...) John Hascall ISU Comp Center
gwyn@smoke.BRL.MIL (Doug Gwyn ) (02/14/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: > x = (1 + cos(r)) / (cos(r) * sin(r)); > y = (cos(r) - sin(r)) / (1 + sin(r)); >Now, can I expect the compiler to form only one call to sin and cos? This is an interesting issue. In traditional C implementations, since there was no guarantee that the functions wouldn't have side effects (after all, you might have provided your own definitions for them), the functions had to be called multiple times to make sure that any side effects were properly performed. In a (proposed) ANSI C hosted environment, these functions are known to be provided by the implementation and to conform to the Standard; therefore a sufficiently clever optimizer could take advantage of the fact that they're known to be so-called "pure" functions to avoid calling them multiple times with the same argument. I don't know of any implementations that perform this particular optimization, but I suspect the supercomputer folks will be doing it. There is no standard mechanism for an application to declare its own functions as "pure"; however, if the compiler has access to all files it may be able to make such a determination itself. Note also that ANSI C implementations can #define cos(x) __intrinsic_cos(x) or something along those lines, to allow the compiler to generate in-line code rather than an actual function call for standard functions. There actually is floating-point hardware with SQRT support; I don't know about COS.
karl@haddock.ima.isc.com (Karl Heuer) (02/14/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: > x = (1 + cos(r)) / (cos(r) * sin(r)); > y = (cos(r) - sin(r)) / (1 + sin(r)); Most compilers will *not* optimize this, because they don't recognize that sin() and cos() are pure functions. (Clearly it would be an invalid optimization to do this in general, because of the existence of impure functions such as getchar() and rand().) In this case, the optimization would be legal, if the compiler takes the trouble to observe that the library functions sin() and cos() are pure. It could do the same thing with any user-defined functions that are visible and whose purity can be proven at compile-time (or, perhaps, whose purity is hinted at with a #pragma). I don't know of any compilers that are this smart. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
tim@crackle.amd.com (Tim Olson) (02/14/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: | | x = (1 + cos(r)) / (cos(r) * sin(r)); | y = (cos(r) - sin(r)) / (1 + sin(r)); | | I made this up, but the point is the re-use of the sin() and cos() | calls. Now, can I expect the compiler to form only one call to sin and | cos? Specifically, I am using ULTRIX 2.1 on a VS2000, but my real | question is, would *most* compilers optimize this as I'd hope, or | *some* compilers, or hardly any? I think that very few compilers currently perform this optimization. The problem is that (pre-ANSI) compilers usually have no knowledge about standard library routines -- they look just like other function calls. Therefore, the compiler does not know that sin() or cos() are "true functions", in that they will return the same values for the same inputs, and have no side-effects. ANSI-conforming C compilers will be able to perform this optimization, since the standard library routine names are reserved, and the compiler can have specific knowledge about them. I know of at least one C compiler that is tracking the proposed ANSI standard that will perform this optimization. -- Tim Olson Advanced Micro Devices (tim@crackle.amd.com)
mball@cod.NOSC.MIL (Michael S. Ball) (02/14/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: > x = (1 + cos(r)) / (cos(r) * sin(r)); > y = (cos(r) - sin(r)) / (1 + sin(r)); >Now, can I expect the compiler to form only one call to sin and cos? In K&R C this is impossible, as many have mentioned. The draft ANSI standard makes it possible, though not too many take advantage of it. The Oregon Software C & C++ compiler uses the trick proposed in the standard and uses a macro to convert the math functions to built-in functions. These are known to be pure and are so optimized. In fact, if the target machine has a math chip the simple math functions are compiled inline as single instructions. -Mike Ball- TauMetric Corporation 1094 Cudahy Pl. Ste 302 San Diego, CA 92110 (619)275-6381 mball@cod.nosc.mil
leo@philmds.UUCP (Leo de Wit) (02/14/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: |I have a question about how much optimizing I should worry about when |writing programs in C. Suppose I have this code fragment: | | x = (1 + cos(r)) / (cos(r) * sin(r)); | y = (cos(r) - sin(r)) / (1 + sin(r)); | |I made this up, but the point is the re-use of the sin() and cos() |calls. Now, can I expect the compiler to form only one call to sin and |cos? Try rand() instead of sin(), cos(). Now, you wouldn't want the compiler to form only one call to rand(), would you? Leo.
davidsen@steinmetz.ge.com (William E. Davidsen Jr) (02/14/89)
In article <9648@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: | This is an interesting issue. In traditional C implementations, since | there was no guarantee that the functions wouldn't have side effects ... | ... ... a sufficiently | clever optimizer could take advantage of the fact that they're known to | be so-called "pure" functions to avoid calling them multiple times with | the same argument. I don't know of any implementations that perform | this particular optimization, but I suspect the supercomputer folks | will be doing it. I agree. One solution would be to provide a keyword, perhaps something like 'pure' or 'deterministic', which would indicate that a procedure always returns the same value for a set of given arguments. Note that this is not the same thing a "no side effects," my intent is only that a second call with the same arguments would not change the side effects (such as saving one of the arguments, etc). There must be a good mathmatical term for this, 'pure' has too many overloaded meanings, and 'deterministic' is far too long. I am not sure that having the compiler "know about" library functions is a good idea, since the user could provide functions with identical names if the compile were to be used in a non-hosted application. -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
mcdonald@uxe.cso.uiuc.edu (02/14/89)
>I have a question about how much optimizing I should worry about when >writing programs in C. Suppose I have this code fragment: > x = (1 + cos(r)) / (cos(r) * sin(r)); > y = (cos(r) - sin(r)) / (1 + sin(r)); >I made this up, but the point is the re-use of the sin() and cos() >calls. Now, can I expect the compiler to form only one call to sin and >cos? Doug Gwyn has already posted the answer to part of this: according to ANSI C, the compiler "can" do it to save time. (In general we can assume his answers supercede most others, at least for ANSI compilers). According to my just-performed test, the Microsoft C 5.1 DOES do it. In fact, if the compiler had an 80386/80387 mode it probably should just inline them, as there are machine instructions for sin and cosine, as well as sin AND cos (in one instruction) in an 80387 (but NOT 8087, which does have tan). The book says FSINCOS may not be as accurate as FSIN or FCOS, though. This answers the query in Gwyn's posting. Doug McDonald
henry@utzoo.uucp (Henry Spencer) (02/14/89)
In article <9648@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >... to allow the compiler to generate >in-line code rather than an actual function call for standard >functions. There actually is floating-point hardware with SQRT >support; I don't know about COS. You betcha; the 80x87 and the 6888x implement everything including the kitchen sink, notably the trig functions. Never mind the mundane stuff like cos(): the 68881 has a hyperbolic-arctangent instruction! Of course, the newer and faster FPUs like the MIPS one don't have all this gingerbread, so who knows what next year's FPUs will look like... -- The Earth is our mother; | Henry Spencer at U of Toronto Zoology our nine months are up. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
bowles@eris.berkeley.edu (Jeff A. Bowles) (02/15/89)
In article <13134@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: > I agree. One solution would be to provide a keyword, perhaps something >like 'pure' or 'deterministic', which would indicate that a procedure >always returns the same value for a set of given arguments. Note that >this is not the same thing a "no side effects," my intent is only that a >second call with the same arguments would not change the side effects >(such as saving one of the arguments, etc). One language I read about in ages past had the notion of function versus procedure as defined below: function: Like a mathematical function, is strictly a function of its arguments. (Perhaps the arguments might be put through a "known" transformation, like a table lookup, but this idea tends to support the notion that a set of inputs gives the same output, consistently.) subroutine: fair game. Now, in C, it's harder than you think - because if you pass a pointer to a procedure, it's difficult to keep the procedure from modifying data to which the argument points. Notions like "const" and function prototypes make it a little easier to decide what a procedure DOESN'T do, but it's pretty hard to tell if a procedure will fit the definition of a "function" above. Jeff Bowles case
evil@arcturus.UUCP (Wade Guthrie) (02/15/89)
In article <515@larry.UUCP>, jwp@larry.UUCP (Jeffrey W Percival) writes: > my real question is, would *most* compilers optimize this . . . While we're talking about optimizers (and, since all the furor about optimizing one's code has died down :->), what do most optimizers on most C compilers do? Where is TFM that I should be 'R'ing (and in which FM should I look?) I would expect the following optimizations: 1) constant expression reduction 2) loop inversion 3) reducing things like intval/2 == intval >> 1 when they are faster. I actually saw a programmer write something LAST YEAR that used intval >> n instead of dividing. Scary. What else should I expect? From what compilers? On what machines? In short, what should I do myself and what should I let the *general* optimizer/compiler do? Wade Guthrie evil@arcturus.UUCP Rockwell International Anaheim, CA (Rockwell doesn't necessarily believe / stand by what I'm saying; how could they when *I* don't even know what I'm talking about???)
karl@haddock.ima.isc.com (Karl Heuer) (02/15/89)
In article <13134@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: >One solution would be to provide a keyword ... which would indicate that a >procedure always returns the same value for a set of given arguments. Note >that this is not the same thing a "no side effects," my intent is only that a >second call with the same arguments would not change the side effects (such >as saving one of the arguments, etc). If the concept is to be useful, it had better mean "no observable side effects AT ALL". The (IMHO) useful optimization of extern int __pure abs(); x = abs(t); y = abs(u); z = abs(t); return (z-x); into return (0); seems to be forbidden by your weaker form. >I am not sure that having the compiler "know about" library functions is a >good idea, since the user could provide functions with identical names if the >compile were to be used in a non-hosted application. No problem; such a compiler, when used in freestanding mode, simply disables such knowledge. This is automatic if the "magic" is embedded in the standard header files, via a keyword. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
mesard@bbn.com (Wayne Mesard) (02/15/89)
In article <9648@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >There is no standard mechanism for an application to declare its own >functions as "pure"; however, if the compiler has access to all files >it may be able to make such a determination itself. Anyone want to challenge (by way of counter-example) the hypothesis that A function which is entirely composed of known "pure" operations* is, itself, pure. * Where pure operations is defined as functions that produce no side effects and return deterministic values, and most operators (excluding assignment to dereferenced pointers and globals). Hint: Sleep(3) would, I believe, be labelled "pure" under this definition, so something's still missing. -- unsigned *Wayne_Mesard(); MESARD@BBN.COM BBN, Cambridge, MA
jnh@ece-csc.UUCP (Joseph Nathan Hall) (02/16/89)
In article <954@philmds.UUCP> leo@philmds.UUCP (Leo de Wit) writes: >In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: >|I have a question about how much optimizing I should worry about when >|writing programs in C. Suppose I have this code fragment: >| >| x = (1 + cos(r)) / (cos(r) * sin(r)); >| y = (cos(r) - sin(r)) / (1 + sin(r)); >| >|I made this up, but the point is the re-use of the sin() and cos() >|calls. Now, can I expect the compiler to form only one call to sin and >|cos? > >Try rand() instead of sin(), cos(). Now, you wouldn't want the compiler >to form only one call to rand(), would you? > Now, you know, this is an interesting point. The functions (call them "pure" or "mathematical") that can be optimized in the fashion of redundant subexpressions have to depend SOLELY on their inputs, and furthermore (this is the point) can't have any "memory" of previous state. I think language support for pure functions would be very useful, personally. No static variables, no references to external variables (other than other pure functions). The function rand() would be OK if it required a seed value as a parameter. -- v v sssss|| joseph hall || 201-1D Hampton Lee Court v v s s || jnh@ece-csc.ncsu.edu (Internet) || Cary, NC 27511 v sss || the opinions expressed herein are not necessarily those of my -----------|| employer, north carolina state university . . . . . . . . . . .
rob@kaa.eng.ohio-state.edu (Rob Carriere) (02/16/89)
In article <36034@bbn.COM> mesard@BBN.COM (Wayne Mesard) writes: > A function which is entirely composed of known "pure" operations* > is, itself, pure. > >* Where pure operations is defined as functions that produce no side >effects and return deterministic values, and most operators (excluding >assignment to dereferenced pointers and globals). Hint: Sleep(3) would, >I believe, be labelled "pure" under this definition, so something's >still missing. What seems to be missing is the idea that sleep *does* modify something, namely time. So formally speaking, your compiler should consider sleep to have a side effect on a variable called __time. If you do that, there's no problem. SR
bright@Data-IO.COM (Walter Bright) (02/16/89)
In article <515@larry.UUCP> jwp@larry.UUCP (Jeffrey W Percival) writes: >I have a question about how much optimizing I should worry about when >writing programs in C. > x = (1 + cos(r)) / (cos(r) * sin(r)); > y = (cos(r) - sin(r)) / (1 + sin(r)); >Now, can I expect the compiler to form only one call to sin and >cos? In general, function calls are *not* regarded as common subexpressions, since the compiler usually knows nothing about the function, and it may have side effects. The cases where func() *might* be done only once are: 1) If func() is an inline function, like in C++, and the compiler recognizes the expansions as being common. 2) If func() is a compiler built-in function, so the compiler knows that there are no side effects, and so it's common. 3) If func() is a compiler built-in function, and the target machine implements func() as a small number of machine instructions, and a peephole optimizer in the code generator commons it. Obviously, if func() is a user-defined function, and its implementation is in another file, there is no way that the compiler can recognize it as common. Of course, the best way to determine if the compiler makes it common is to compile it and see!
thor@stout.ucar.edu (Rich Neitzel) (02/16/89)
In article <3684@arcturus> evil@arcturus.UUCP (Wade Guthrie) writes: >While we're talking about optimizers (and, since all the furor about >optimizing one's code has died down :->), what do most optimizers on >most C compilers do? Where is TFM that I should be 'R'ing (and in which >FM should I look?)... > >What else should I expect? From what compilers? On what machines? >In short, what should I do myself and what should I let the *general* >optimizer/compiler do? > In addition, should one let the compiler do optimization? This may not be important in most cases, but for others it can destroy the functioning of the code. For example, many external devices have control/status registers that are cleared only when read. An optimizer might see code: junk = *csr; and since junk is never used again, remove that line. Or how about this: while (i < length) { while (!(*csr & 0x80)); *storage++ = *data_reg; } This loop polls on a done bit and then reads the new data in the data register. An optimizer might decide that since data_reg does not SEEM to change, the value it points to can be put into a register and copied from there on each pass. Optimizing is an uncertain tool unless one knows what the optimizer is doing. Since RISC cpus use heavily optimizing compilers and have assemblers that are nearly impossible to follow, how does one make certain that the optimizer hasn't shafted you? (On my 68020 I can peek at the assembler output.) Even on CISC machines, perhaps compiler vendors should supply a OPT_ON and OPT_OFF set of directives. ------------------------------------------------------------------------------- Richard Neitzel National Center For Atmospheric Research Box 3000 Boulder, CO 80307-3000 303-497-2057 thor@thor.ucar.edu Torren med sitt skjegg Thor with the beard lokkar borni under sole-vegg calls the children to the sunny wall Gjo'i med sitt shinn Gjo with the pelts jagar borni inn. chases the children in. -------------------------------------------------------------------------------
chris@mimsy.UUCP (Chris Torek) (02/16/89)
In article <1420@ncar.ucar.edu> thor@stout.ucar.edu (Rich Neitzel) writes: >In addition, should one let the compiler do optimization? This may not >be important in most cases, but for others it can destroy the >functioning of the code. For example, many external devices have >control/status registers that are cleared only when read. This sort of thing is why `volatile' is in the pANS. I suppose I should put out another rerun: Path: mimsy!chris From: chris@mimsy.UUCP (Chris Torek) Newsgroups: comp.lang.c Subject: volatile: a summary Message-ID: <11837@mimsy.UUCP> Date: 7 Jun 88 06:58:00 GMT Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742 Lines: 87 With any luck, this will be my last article on this topic. READ THE WHOLE THING BEFORE YOU FLAME. What is `volatile'? Two things. It is a keyword in the draft proposed ANSI C standard, and it is an attribute of some kinds of variables. As an attribute, it can be applied to objects such as device registers or shared memory regions, but not to `ordinary memory'. The attribute basically means that there is a hidden entity that may either change values stored in what looks like ordinary memory, or take special actions when values are stored, or both. As a keyword, it can be applied in various places within declarations to label variables (including pointer targets) as having the volatile attribute. Is volatile necessary? This question must be broken down to parts before it can be answered. Is the concept necessary? Is the keyword necessary? Is the keyword useful? Is the keyword a `good thing'? Is the concept necessary? That is, is the `volatility attribute' a real thing? Not always. Many applications have no need for the concept. Programs that compute Fibonacci numbers, or that list files, or do any number of useful things may never care about it. It can be vital to others, such as device drivers. Is the keyword necessary? No. (As an existence proof, consider compilers that do not now have the keyword. Most of them work by not doing much in the way of optimisation. There is more to it, though.) A perfect compiler would know as much as all its programmers combined, and could use whatever rules those programmers would use to detect `real volatility'. Such a compiler would always know when a variable should have the volatility attribute. Of course, no perfect compilers exist, nor are any likely to be written in the foreseeable future. But good compilers do exist, and better ones are conceivable; a very good compiler could use external information to find most (but not all) variables that are certain *not* to have the attribute, and could then assume that all others do, and this would suffice. (Note that computing `real volatility' can be as hard as solving the halting problem. I claim only that the compiler can use the same rules that a programmer would use. If the compiler errs only on the side of caution---attaching `real volatility' where it is unnecessary---this is safe, if not perfectly optimal.) Given that the keyword is not absolutely necessary, is it of any use? Yes. If the keyword exists, compilers are free to assume that any variable not tagged by the keyword is truly not volatile. This is a very easy way to discover which variables should be considered to have the attribute, and, knowing which variables are not volatile, the compiler can make a number of optimisations that might otherwise be unsafe. This is not without its cost: With such a compiler, the programmer must correctly label any variables which do have the volatility attribute. But because the scheme is simple, compilers that use it can be faster than, and need not be as complex as, compilers that attempt to find `real volatility' with less help from the programmer. Being less complex, such compilers are more likely to be correct; being faster, they are more pleasant to use. Is the keyword a `good thing', even given a near-perfect compiler, one that can optimise correctly even without the keyword? I think it is. A certain amount of redundancy helps to avoid errors. A good-but-not-quite-perfect compiler might compute its set of volatile declarations, then compare it with the programmer's, and warn of any mismatch. This would help find errors in both the compiler's rules and the programmer's. Too much redundancy is obscuring, but real volatility is rare enough that I believe this will not be a problem. Summary of the summary: Is the concept necessary? Yes. Is the keyword necessary? No. Is the keyword useful? Yes. Is the keyword a `good thing'? Opinion: yes. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
w-colinp@microsoft.UUCP (Colin Plumb) (02/16/89)
karl@haddock.ima.isc.com (Karl Heuer) wrote: > In article <13134@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: > >One solution would be to provide a keyword ... which would indicate that a > >procedure always returns the same value for a set of given arguments. > > If the concept is to be useful, it had better mean "no observable side effects > AT ALL". > This is automatic if the "magic" is embedded in the standard > header files, via a keyword. Um... Karl, what strange disease has come over your brain to make it suddenly like adding keywords to C? :-) This is a perfect example of a good use for #pragma. In <math.h>, I could just include: #pragma functional double sin(double), cos(double); And the compiler could take that as a hint to use common subexpression elimination (a pretty common optimisation) on sin and cos. A good compiler already knows that things like + and ~ are purely functional, and need only generalise the common subexpression and dead-code eliminators to handle more conventional function calls. This is also an example of the point of having a compiler ignore an unrecognised #pragma. Without this #pragma, the code would compute the same result, just more wastefully. -- -Colin (uunet!microsoft!w-colinp) "Don't listen to me. I never do."
karl@haddock.ima.isc.com (Karl Heuer) (02/16/89)
In article <3684@arcturus> evil@arcturus.UUCP (Wade Guthrie) writes: >I would expect the following optimizations: ... 3) reducing things like >intval/2 == intval >> 1 when they are faster. On most implementations these are not equivalent, unless the compiler can prove that intval >= 0. (Ah, many's the time I've wished I could declare a type `nonnegative', which would be the intersection of signed and unsigned, so the compiler could use whichever happened to be faster...) Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
djones@megatest.UUCP (Dave Jones) (02/16/89)
From article <1398@quanta.eng.ohio-state.edu>, by rob@kaa.eng.ohio-state.edu (Rob Carriere): > > What seems to be missing is the idea that sleep *does* modify > something, namely time. So formally speaking, your compiler should > consider sleep to have a side effect on a variable called __time. If > you do that, there's no problem. > Huh?? % nm a.out | grep __time % Know what I mean? On a time-shared system (such as Unix), does every instruction have a side effect on a variable called __time? Gimme a break. (Or at least a sleep(300).)
peter@ficc.uu.net (Peter da Silva) (02/17/89)
In article <36034@bbn.COM>, mesard@bbn.com (Wayne Mesard) writes: > A function which is entirely composed of known "pure" operations* > is, itself, pure. > * Where pure operations is defined as functions that produce no side > effects and return deterministic values, and most operators (excluding > assignment to dereferenced pointers and globals). Sounds good. > Hint: Sleep(3) would, > I believe, be labelled "pure" under this definition, so something's > still missing. No, since I don't think *any* system call is definable as a pure function. In this case alarm() returns a nondeterministic value *and* produces the side effect of setting a timer in your process table entry. Can anyone think of any pure system calls? ioctl(fd, TCGETA, tbuf)? No, I think a system call should be considered not only a global ref but a volatile one! -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Work: uunet.uu.net!ficc!peter, peter@ficc.uu.net, +1 713 274 5180. `-_-' Home: bigtex!texbell!sugar!peter, peter@sugar.uu.net. 'U` People have opinions. Companies have policy. And typos are my own business.
rob@kaa.eng.ohio-state.edu (Rob Carriere) (02/17/89)
In article <2008@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: >From article <1398@quanta.eng.ohio-state.edu>, by rob@kaa.eng.ohio-state.edu (Rob Carriere): >> What seems to be missing is the idea that sleep *does* modify >> something, namely time. So formally speaking, your compiler should >> consider sleep to have a side effect on a variable called __time. If >> you do that, there's no problem. >Huh?? >% nm a.out | grep __time >Know what I mean? Perfectly. Do you know what I mean? Note the phrase ``formally speqaking'' in the above and insert ``for example'' after ``called''. >On a time-shared system (such as Unix), does every instruction have >a side effect on a variable called __time? Of course. And on any non-time shared system as well. The poster to whom I was replying considered the passage of time a side effect. If that is the case, you'd bloody well better model it as part of the system state. >Gimme a break. (Or at least a sleep(300).) Breaks are free() this week :-) SR
msb@sq.com (Mark Brader) (02/19/89)
> >I would expect the following optimizations: ... 3) reducing things like > >intval/2 == intval >> 1 when they are faster. > > On most implementations these are not equivalent, unless the compiler can > prove that intval >= 0. Quite right, except that it also generally works if the compiler can prove that intval is a multiple of the divisor. However, I have met one compiler that always did the optimization anyway! Accordingly, the expressions a/2 and a/b produced *different answers* when a was negative and b was equal to 2! (No, I don't remember which compiler it was. It was a machine we were porting product to, but I wasn't doing the port myself, I just came in to try to identify why my code was producing wrong answers.) It may be noted that the values produced by / and % on negative numbers, where the dividend is not a multiple of the divisor, are not fully defined by the language, neither in the K&R 1 nor the proposed ANSI versions. This is because there are three identities that are desirable in different situations, namely [1] (-a)/b, a/(-b), -(a/b) are all equal [2] a%b ranges from 0 to b-1 for positive b [3] (a/b) * b equals a - a%b But it isn't possible to satisfy all three. The language does guarantee [3]. Of the others, most implementations choose [1], to the annoyance of mathematical users to whom [2] would be much more preferred; that's because it's the way the underlying hardware typically behaves. Now, it turns out that on a 2's complement machine that chooses to sign- extend on >> (also implementation-defined) *and* which elects to support identity [2], *then* the optimization described above *is* possible. Oh -- I should also mention that in proposed ANSI C the library includes two functions div() and ldiv(), which implement (for ints and longs respectively) a form of / and % that is guaranteed to support identities [1] and [3]. In ANSI C the compiler is allowed to optimize these so that they do not become actual function calls. Mark Brader, SoftQuad Inc., Toronto, utzoo!sq!msb, msb@sq.com A standard is established on sure bases, not capriciously but with the surety of something intentional and of a logic controlled by analysis and experiment. ... A standard is necessary for order in human effort. -- Le Corbusier
scs@adam.pika.mit.edu (Steve Summit) (02/19/89)
In article <13134@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: > I agree. One solution would be to provide a keyword, perhaps something >like 'pure' or 'deterministic', which would indicate... Just Say No to new keywords. This sort of optimization is a fine idea, and it does require a hint to the compiler, for the reasons already discussed. However, outside-the-language mucking around is exactly what #pragmas are for: #pragma pure(sin) (Someone, probably Karl Heuer, already made passing reference to the use of #pragmas for this example.) Extra keywords are messy, even if they do follow the rules and use leading underscores. Steve Summit scs@adam.pika.mit.edu
gateley@m2.csc.ti.com (John Gateley) (02/20/89)
In article <1416@quanta.eng.ohio-state.edu> rob@kaa.eng.ohio-state.edu (Rob Carriere) writes: <In article <2008@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: <>On a time-shared system (such as Unix), does every instruction have <>a side effect on a variable called __time? <Of course. And on any non-time shared system as well. The poster to <whom I was replying considered the passage of time a side effect. If <that is the case, you'd bloody well better model it as part of the <system state. The definition of sleep involves passage of time, but the definition of everything else does not. So, even though sleep has a side effect, if, while, for, etc. do not have the same side effect (though they may have others). John gateley@tilde.csc.ti.com
karl@haddock.ima.isc.com (Karl Heuer) (02/22/89)
In article <667@microsoft.UUCP> w-colinp@microsoft.uucp (Colin Plumb) writes: >karl@haddock.ima.isc.com (Karl Heuer) wrote: >>This is automatic if the "magic" is embedded in the standard >>header files, via a keyword. > >Um... Karl, what strange disease has come over your brain to make it suddenly >like adding keywords to C? :-) I meant this to include not only normal keywords (in the reserved namespace) but also #pragmas. However, using #pragma for this is subject to some of the same objections as using it for volatile: does extern int foo(int, double __pure (*)(double)); have a #pragma equivalent? Btw, it would also be possible to use the existing keyword `const' for this. (I'm sure someone else will mention this if I don't.) It remains unclear whether this would be any less of a mistake than the overloading of `static' and `break'. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
john@frog.UUCP (John Woods) (02/23/89)
In article <9648@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn ) writes: > Note also that ANSI C implementations can > #define cos(x) __intrinsic_cos(x) > or something along those lines, to allow the compiler to generate > in-line code rather than an actual function call for standard > functions. There actually is floating-point hardware with SQRT > support; I don't know about COS. The 68881 chip has FCOS, FSIN, and (gasp) FSINCOS which simultaneously computes cos() and sin() of the same argument. A sufficiently clever compiler could potentially make great use of that. -- John Woods, Charles River Data Systems, Framingham MA, (508) 626-1101 ...!decvax!frog!john, john@frog.UUCP, ...!mit-eddie!jfw, jfw@eddie.mit.edu "He should be put in stocks in Lafeyette Square across from the White House and pelted with dead cats." - George F. Will
john@frog.UUCP (John Woods) (02/23/89)
In article <3121@ficc.uu.net>, peter@ficc.uu.net (Peter da Silva) writes: > Can anyone think of any pure system calls? ioctl(fd, TCGETA, tbuf)? I think that if (getpid() != getpid()) ever evaluated to 1, I would be severely astonished. -- John Woods, Charles River Data Systems, Framingham MA, (508) 626-1101 ...!decvax!frog!john, john@frog.UUCP, ...!mit-eddie!jfw, jfw@eddie.mit.edu "He should be put in stocks in Lafeyette Square across from the White House and pelted with dead cats." - George F. Will
gwyn@smoke.BRL.MIL (Doug Gwyn ) (02/23/89)
In article <1026@frog.UUCP> john@frog.UUCP (John Woods) writes: >The 68881 chip has FCOS, FSIN, and (gasp) FSINCOS which simultaneously >computes cos() and sin() of the same argument. A sufficiently clever >compiler could potentially make great use of that. Well, hurray -- I've wanted that for years! I do hope C implementors will perform this optimization; it could help us computer-graphics types quite a bit.
lvc@cbnews.ATT.COM (Lawrence V. Cipriani) (02/24/89)
In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes: >I think that if > > (getpid() != getpid()) > >ever evaluated to 1, I would be severely astonished. How about if the left hand getpid() is called, and before the right hand getpid() is called a signal comes in, causing a signal handler to be called, then the signal handler does a fork. Then, the interrupt handler returns and the right hand getpid() is called. Voila! -- Larry Cipriani, att!cbnews!lvc or lvc@cbnews.att.com
karl@haddock.ima.isc.com (Karl Heuer) (02/24/89)
In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes: >In article <3121@ficc.uu.net>, peter@ficc.uu.net (Peter da Silva) writes: >>Can anyone think of any pure system calls? > >[What about getpid()?] Nope. register int i = getpid(); if (fork() != 0) exit(0); if (getpid() != i) printf("impure!\n"); Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
barmar@think.COM (Barry Margolin) (02/24/89)
In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes: >I think that if > (getpid() != getpid()) >ever evaluated to 1, I would be severely astonished. Well, how about (pid = getpid(), (void) fork(), pid != getpid()) ? It will evaluate to 0 in the parent process, 1 in the child process. Since fork() changes the value of getpid(), getpid() isn't pure. But it would be wrong to make fork() always prevent common subexpression elimination, since it doesn't modify any of the program's own variables. Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
haahr@phoenix.Princeton.EDU (Paul Gluckauf Haahr) (02/24/89)
In article <3121@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > Can anyone think of any pure system calls? ioctl(fd, TCGETA, tbuf)? trivial examples are getdtablesize() or getpagesize() from bsd, at least in the absence of process migration for heterogenous operating system versions (a safe assumption in 1989). one might want to consider _exit() pure, as there can be no second call, but it's largely irrelevant to optimization. now, who cares?
khera@juliet.cs.duke.edu (Vick Khera) (02/25/89)
In article <9693@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >In article <1026@frog.UUCP> john@frog.UUCP (John Woods) writes: >>The 68881 chip has FCOS, FSIN, and (gasp) FSINCOS which simultaneously >>computes cos() and sin() of the same argument. A sufficiently clever >>compiler could potentially make great use of that. > >Well, hurray -- I've wanted that for years! I do hope C implementors >will perform this optimization; it could help us computer-graphics types >quite a bit. The Sun 3 C compiler will use the intrinsic functions of the 68881 chip if you tell it to compile with the f68881.il inline-expansion file. i beilieve it is located in /usr/lib/f68881/libm.il under 4.0, and in /usr/lib/f68881.il in 3.x. example compile line: cc -o prog prog.c /usr/lib/f68881.il vick. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= ARPA: khera@cs.duke.edu Department of Computer Science CSNET: khera@duke Duke University UUCP: decvax!duke!khera Durham, NC 27706
gwyn@smoke.BRL.MIL (Doug Gwyn ) (02/25/89)
In article <4276@cbnews.ATT.COM> lvc@cbnews.ATT.COM (Lawrence V. Cipriani) writes:
-How about if the left hand getpid() is called, and before the right hand
-getpid() is called a signal comes in, causing a signal handler to be called,
-then the signal handler does a fork. Then, the interrupt handler returns
-and the right hand getpid() is called. Voila!
Anyone who fork()s then returns inside a signal handler deserves to suffer.lvc@cbnews.ATT.COM (Lawrence V. Cipriani) (02/26/89)
In article <9705@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn ) writes: ! In article <4276@cbnews.ATT.COM> lvc@cbnews.ATT.COM (Lawrence V. Cipriani) writes: ! -How about if the left hand getpid() is called, and before the right hand ! -getpid() is called a signal comes in, causing a signal handler to be called, ! -then the signal handler does a fork. Then, the interrupt handler returns ! -and the right hand getpid() is called. Voila! ! ! Anyone who fork()s then returns inside a signal handler deserves to suffer. Yes, but so what. The question basically was "Is getpid() != getpid() ever true." It was not restricted to what was reasonable or common coding practice, or sanctioned by the pANS, or your personal preference, or anything else. It isn't necessary to say something is a bad idea when that wasn't asked, so I didn't. -- Larry Cipriani, att!cbnews!lvc or lvc@cbnews.att.com
richard@aiai.ed.ac.uk (Richard Tobin) (02/28/89)
>one might want to consider _exit() pure
Yeah, that's right, the compiler can put in a call to it at the start
of the program, and save the value it returns :-)
-- Richard
--
Richard Tobin, JANET: R.Tobin@uk.ac.ed
AI Applications Institute, ARPA: R.Tobin%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!R.Tobindg@lakart.UUCP (David Goodenough) (03/01/89)
From article <36662@think.UUCP>, by barmar@think.COM (Barry Margolin):
] In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes:
]>I think that if
]> (getpid() != getpid())
]>ever evaluated to 1, I would be severely astonished.
]
] Well, how about
]
] (pid = getpid(), (void) fork(), pid != getpid())
]
] ? It will evaluate to 0 in the parent process, 1 in the child
] process.
True - but I don't see any references to fork() in Mr.Woods' posting.
What he is stating is that _IN THE ABSENCE_ of fork() calls, getpid()
had better return an unchanging value.
--
dg@lakart.UUCP - David Goodenough +---+
IHS | +-+-+
....... !harvard!xait!lakart!dg +-+-+ |
AKA: dg%lakart.uucp@xait.xerox.com +---+john@frog.UUCP (John Woods) (03/03/89)
In article <453@lakart.UUCP>, dg@lakart.UUCP (David Goodenough) writes: O> From article <36662@think.UUCP>, by barmar@think.COM (Barry Margolin): O> ] In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes: P> ]>I think that if S> ]> (getpid() != getpid()) > ]>ever evaluated to 1, I would be severely astonished. O> ] Well, how about O> ] (pid = getpid(), (void) fork(), pid != getpid()) P> True - but I don't see any references to fork() in Mr.Woods' posting. S> What he is stating is that _IN THE ABSENCE_ of fork() calls, getpid() > had better return an unchanging value. No, what I was stating was that getpid() was a pure function. Pure functions are supposed to be pure functions even in the presense of other function calls. It is that property which allows them to be aggressively optimized. It is obvious that I was mistaken. As I have said to the first two people to point this out, oops. -- John Woods, Charles River Data Systems, Framingham MA, (508) 626-1101 ...!decvax!frog!john, john@frog.UUCP, ...!mit-eddie!jfw, jfw@eddie.mit.edu "He should be put in stocks in Lafeyette Square across from the White House and pelted with dead cats." - George F. Will
djones@megatest.UUCP (Dave Jones) (03/04/89)
From article <1056@frog.UUCP>, by john@frog.UUCP (John Woods): > > It is obvious that I was mistaken. > He says this even in response to a posting which tried to help him weasel out, by saying, "What he *really* meant was.." I am impressed! Dave J.
mouse@mcgill-vision.UUCP (der Mouse) (03/07/89)
In article <1028@frog.UUCP>, john@frog.UUCP (John Woods) writes: > In article <3121@ficc.uu.net>, peter@ficc.uu.net (Peter da Silva) writes: >> Can anyone think of any pure system calls? ioctl(fd, TCGETA, tbuf)? This really belongs in an OS-specific group. Let's see....I just ran through the table of syscalls on this system and getpagesize() and getdtablesize() are the only really pure syscalls I see there. > I think that if > (getpid() != getpid()) > ever evaluated to 1, I would be severely astonished. Signal handlers aside, that's not the point. If I write int pid1; int pid2; pid1 = getpid(); runinchild(); pid2 = getpid(); then I don't want the compiler to decide that it can rewrite the second one to "pid2 = pid1;" because getpid() is pure - presumably runinchild() will fork. Here's a quick test: a function is pure if it can be replaced with a memo-function wrapper without changing the semantics. This is not true of getpid() or sync(), to pick two examples that are tempting. der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu
mouse@mcgill-vision.UUCP (der Mouse) (03/15/89)
In article <453@lakart.UUCP>, dg@lakart.UUCP (David Goodenough) writes: > From article <36662@think.UUCP>, by barmar@think.COM (Barry Margolin): >> In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes: >>> (getpid() != getpid()) [should always be 1] >> Well, how about >> (pid = getpid(), (void) fork(), pid != getpid()) > True - but I don't see any references to fork() in Mr.Woods' posting. > What he is stating is that _IN THE ABSENCE_ of fork() calls, getpid() > had better return an unchanging value. Sure - and in the absence of assignments, variables are constant and can be optimized away. The whole point of this was to find a pure syscall, and a routine isn't pure if calling another routine can cause it to change its return value for a given set of argument values. Thus, fork()'s changing the return value of getpid() means that getpid() can't be considered pure. der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu
bowles@eris.berkeley.edu (Jeff A. Bowles) (03/15/89)
>>> In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes: >>>> (getpid() != getpid()) [should always be 1] >>> Well, how about >>> (pid = getpid(), (void) fork(), pid != getpid()) >> True - but I don't see any references to fork() in Mr.Woods' posting. >> What he is stating is that _IN THE ABSENCE_ of fork() calls, getpid() >> had better return an unchanging value. > >Sure - and in the absence of assignments, variables are constant and >can be optimized away. The whole point of this was to find a pure >syscall, and a routine isn't pure if calling another routine can cause >it to change its return value for a given set of argument values. >Thus, fork()'s changing the return value of getpid() means that >getpid() can't be considered pure. Are we still on this topic? By the bogosity above, nothing is "pure", because you might write a function that changes the behaviour of another function - for example, ftell(3S) (tell you where your file pointer is, in file) is pure, unless there's an fread/fwrite/fseek/fclose/freopen in the vicinity. Now, those named functions are obviously impure, but aren't you pushing it a little far? How about: 1. These functions are pure, i.e. the values returned will not change from one invocation to the next, given that the arguments didn't change: a function that returns the process's pid a function that returns the byte offset of a file pointer a function that returns the file descriptor corresponding to a file pointer (and so on) any function that performs arithmetic operations on its arguments and on the results of "pure" functions it invokes. 2. Any function that deviates by invoking an "impure" function, anywhere along the way, is an "impure" function. (Certain basic blocks might still be "pure" but the function itself isn't. 3. Any function that dereferences a pointer is best though of as "inpure" unless you decide how to describe "the argument passed didn't change in the second invocation of that function" - even if you passed a pointer to the same object, the pointer might be the same, but the object might not. This obviously limits the power within C, and makes a good argument for "const" and the like.... As a result, for (i = 0; i < 100000; i++) pid = getpid(); is a reasonable thing to compress to the single assignment "pid = getpid();" Jeff Bowles
desnoyer@Apple.COM (Peter Desnoyers) (03/21/89)
In article <21652@agate.BERKELEY.EDU> bowles@eris.berkeley.edu (Jeff A. Bowles) writes: >>>> In article <1028@frog.UUCP> john@frog.UUCP (John Woods) writes: >>> [various people arguing whether getpid() is pure] >> >Are we still on this topic? By the bogosity above, nothing is "pure", >because you might write a function that changes the behaviour of another >function - for example, [...] I beg to differ. I would consider that any "pure" function that does not take arguments to be a constant, as otherwise it cannot depend solely on its arguments, but must return a value dependent on state information external to the function. How about these definitions: (note that I am considering "implicit" results, e.g. status = f(arguments,&result) style calls return two results.) pure - if f is pure and f takes arguments Ai and returns results Ri, then for any action B which does not modify A or R: R=f(A),B,R=f(A) is equiv. to R=f(A),B is equiv. to B,R=f(A) conditionally pure - if f is conditionally pure, then one can define a dependency set D such that if B is some action with does not modify A or R, and does not contain any elements of D, then R=f(A),B,R=f(A) is equiv. to R=f(A),B is equiv. to B,R=f(A). It is a lot simpler for a compiler to take advantage of pure functions than conditionally pure ones, because it doesn't have to worry about dependencies. Peter Desnoyers
mouse@mcgill-vision.UUCP (der Mouse) (03/29/89)
In article <21652@agate.BERKELEY.EDU>, bowles@eris.berkeley.edu (Jeff A. Bowles) writes: [many attribution lines seem to have been lost -dM] >>>>> (getpid() != getpid()) [should always be 1] >>>> [how about] (pid = getpid(), (void) fork(), pid != getpid()) >>> What he is stating is that _IN THE ABSENCE_ of fork() calls, >>> getpid() had better return an unchanging value. [this next comment was mine -dM] >> Sure - and in the absence of assignments, variables are constant and >> can be optimized away. [... A] routine isn't pure if calling >> another routine can cause it to change its return value for a given >> set of argument values. > Are we still on this topic? By the bogosity above, nothing is "pure", > because you might write a function that changes the behaviour of > another function - [...example with ftell...] ftell() is of course not pure, as you noted, because there are functions (fread, fseek, fwrite, fclose, etc) that can cause its return value to change. sin(), on the other hand, is: if I call sin() with some argument value, and then call it again with the same value, the second call *will* return the same value, regardless of what other routines I've called in the meantime. This is what I mean (and understand to be meant) by a "pure" function. > 1. These functions are pure, i.e. the values returned will not change > from one invocation to the next, given that the arguments didn't > change: ...and provided that certain other things don't happen between the two invocations, generally calling certain other functions with certain arguments, the set of forbidden functions and arguments varying with the function being considered. This is a much weaker property, but one which may still be useful in some circumstances. Which one should properly be called "pure" is a different argument entirely (and one which I won't argue here except to note that I'll stick with the stronger meaning). der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu