446,403 Members | 900 Online
Need help? Post your question and get tips & solutions from a community of 446,403 IT Pros & Developers. It's quick & easy.

# f() + g() * h()

 P: n/a In http://c-faq.com/expr/precvsooe.html in the answer to "comp.lang.c FAQ list · Question 3.4" The following appears: Operator precedence and explicit parentheses impose only a partial ordering on the evaluation of an expression. In the expression f() + g() * h() although we know that the multiplication will happen before the addition, there is no telling which of the three functions will be called first. In other words, precedence only partially specifies order of evaluation, where ``partially'' emphatically does not cover evaluation of operands. MY QUESTION: Only within the same precedence group, the order of evaluation of operands is not specified. Here multiplication has higher precedence and addition has lower precedence. So shouldn't the functions g() and h() be called before f() to do the multiplication first ? Where am I going wrong ? Thanks Mar 16 '07 #1
27 Replies

 P: n/a su**************@yahoo.com, India said: In http://c-faq.com/expr/precvsooe.html in the answer to "comp.lang.c FAQ list · Question 3.4" The following appears: Operator precedence and explicit parentheses impose only a partial ordering on the evaluation of an expression. In the expression f() + g() * h() although we know that the multiplication will happen before the addition, Wait a minute. What we *actually* know is only that no operator can do its work until the values of its operands are known. MY QUESTION: Only within the same precedence group, the order of evaluation of operands is not specified. Here multiplication has higher precedence and addition has lower precedence. Precedence does *not* determine order of evaluation. It determines which operands belong to which operators. So shouldn't the functions g() and h() be called before f() to do the multiplication first ? Where am I going wrong ? Consider the following code, which calculates f() * g() + h(): t1 = f(); t2 = g(); t3 = h(); result = t1 * t2 * t3; Okay, how about this? t3 = h(); t2 = g(); t1 = f(); result = t1 * t2 * t3; Or, of course, any of four other combinations. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Mar 16 '07 #2

 P: n/a su**************@yahoo.com, India wrote: In http://c-faq.com/expr/precvsooe.html in the answer to "comp.lang.c FAQ list Â· Question 3.4" The following appears: Operator precedence and explicit parentheses impose only a partial ordering on the evaluation of an expression. In the expression f() + g() * h() although we know that the multiplication will happen before the addition, there is no telling which of the three functions will be called first. In other words, precedence only partially specifies order of evaluation, where ``partially'' emphatically does not cover evaluation of operands. MY QUESTION: Only within the same precedence group, the order of evaluation of operands is not specified. Here multiplication has higher precedence and addition has lower precedence. So shouldn't the functions g() and h() be called before f() to do the multiplication first ? No. Nothing stops `f` being called first. Indeed, in the boring and obvious straightforward translation of this expression, `f` /is/ called first. Because the obvious translation produces code that can often be bettered by calling `f` later (and hence not having to save its result while `g() * h()` is evaluated), C says the order is unspecified and hence allows the compiler more room to manoeuver [1]. Where am I going wrong ? You're confusing precedence with order of evaluation. [1] My /personal/ view is that less things bite your bus if the language specifies the evaluation order and the compiler can reorder only if it can prove it makes no difference to the result. But that makes assumptions about how much computing power the compiler has, and what the costs of less-than-excellent code generation are, that were far less true twenty years ago than they are now. Although I had this opinion twenty years ago too ... -- Chris "aging like fine wine" Dollin Meaning precedes definition. Mar 16 '07 #3

 P: n/a su**************@yahoo.com, India wrote: In http://c-faq.com/expr/precvsooe.html in the answer to "comp.lang.c FAQ list · Question 3.4" The following appears: Operator precedence and explicit parentheses impose only a partial ordering on the evaluation of an expression. In the expression f() + g() * h() although we know that the multiplication will happen before the addition, there is no telling which of the three functions will be called first. In other words, precedence only partially specifies order of evaluation, where ``partially'' emphatically does not cover evaluation of operands. MY QUESTION: Only within the same precedence group, the order of evaluation of operands is not specified. Here multiplication has higher precedence and addition has lower precedence. So shouldn't the functions g() and h() be called before f() to do the multiplication first ? Where am I going wrong ? See others' replies. For a concrete example of why there might be a compelling reason to call f() first, let's flesh things out a bit: y = 0; for (i = 0; i < 1000000; ++i) y += sqrt(2) + g(i) * h(i); Here, the anonymous f() has been replaced with something more recognizable. But look: The compiler knows (or can know) that sqrt() is a "pure" function, one that has no side-effects and always returns the same value for the same arguments. So the code can be made faster if the compiler rewrites it as y = 0; double __temp == sqrt(2); for (i = 0; i < 1000000; ++i) y += __temp + g(i) * h(i); By calling f() -- that is, sqrt() -- before g() and h(), the compiler has eliminated almost a million function calls. Is that something you would like your compiler to do for you, hmm? A sufficiently smart compiler might even calculate sqrt(2) at compilation time, thus "calling" f() before the program even starts running. An extremely smart compiler might even rewrite the code as y = 1.4142135623730950488016887242097e6; for (i = 0; i < 1000000; ++i) y += g(i) * h(i); .... although this transformation is a bit dubious because of the approximate nature of floating-point arithmetic. Anyhow, the point of this illustration is to show that there are circumstances where you *want* the compiler to have a good deal of freedom to rearrange the order of evaluation. -- Eric Sosman es*****@acm-dot-org.invalid Mar 16 '07 #4

 P: n/a Chris Dollin wrote, On 16/03/07 10:46: [1] My /personal/ view is that less things bite your bus if the language specifies the evaluation order and the compiler can reorder only if it can prove it makes no difference to the result. But that makes assumptions about how much computing power the compiler has, and what the costs of less-than-excellent code generation are, that were far less true twenty years ago than they are now. Although I had this opinion twenty years ago too ... I'm of the opposite opinion. I think that within an expression the language should allow the compiler to take liberties in the order of evaluation since otherwise where it makes a difference to efficiency the person writing the software has to worry about it instead of leaving it up to the compiler. If you have not yet written the functions that are called from within the expression the compiler cannot tell whether reordering the calls will have an effect, but it does know if it can save the need for an extra temporary! -- Flash Gordon Mar 16 '07 #5

 P: n/a Flash Gordon wrote: [Now going so far OT that this will be my last posting on this (for a while at least ...)] Chris Dollin wrote, On 16/03/07 10:46: >[1] My /personal/ view is that less things bite your bus if the language specifies the evaluation order and the compiler can reorder only if it can prove it makes no difference to the result. But that makes assumptions about how much computing power the compiler has, and what the costs of less-than-excellent code generation are, that were far less true twenty years ago than they are now. Although I had this opinion twenty years ago too ... I'm of the opposite opinion. I think that within an expression the language should allow the compiler to take liberties in the order of evaluation since otherwise where it makes a difference to efficiency the person writing the software has to worry about it Well, that's part of the basis for my opinion: very often they /don't/ have to worry about it. To find out if it's important, they profile. Then they change the bits that are slow. I don't think the differences of efficiency that pre-defined-order vs compiler-picks-order make are significant enough that it's a no-brainer. instead of leaving it up to the compiler. If you have not yet written the functions that are called from within the expression the compiler cannot tell whether reordering the calls will have an effect, but it does know if it can save the need for an extra temporary! It can't know whether the order of evaluation is important. It is (IMAO) /far/ more important that the program behaviour be predictable than that we can save the odd temporary here and there. But then, I've always treated computer resources as things that are there to help me write effective code; I'm prepared to burn (some) cycles for my programming convenience. Which doesn't stop me obsessing on how to compile constructs in my preferred language(s) efficiently. -- Chris "meta" Dollin "We did not have time to find out everything we wanted to know." - James Blish, /A Clash of Cymbals/ Mar 16 '07 #6

 P: n/a "su**************@yahoo.com, India" wrote: > In http://c-faq.com/expr/precvsooe.html in the answer to "comp.lang.c FAQ list · Question 3.4" The following appears: Operator precedence and explicit parentheses impose only a partial ordering on the evaluation of an expression. In the expression f() + g() * h() [...] MY QUESTION: Only within the same precedence group, the order of evaluation of operands is not specified. Here multiplication has higher precedence and addition has lower precedence. So shouldn't the functions g() and h() be called before f() to do the multiplication first ? Where am I going wrong ? Consider a stack-based implementation which produces the following pseudo-code: CALL f PUSH result CALL g PUSH result CALL h PUSH result CALL multiply ; pops top 2 stack items and multiplies them PUSH result CALL add ; pops top 2 stack items and adds them ; "result" holds the value f() + g() * h() -- +-------------------------+--------------------+-----------------------+ | Kenneth J. Brody | www.hvcomputer.com | #include | | kenbrody/at\spamcop.net | www.fptech.com | Mar 16 '07 #7

 P: n/a On Mar 16, 12:33 pm, Eric Sosman

 P: n/a Fr************@googlemail.com wrote: So what about sqrt? It's a function defined by the Standard, so the compiler knows everything it wants to know about it, including the answers it gives for particular values. -- Chris "electric hedgehog" Dollin "It's just the beginning we've seen" - Colosseum, /Tomorrow's Blues/ Mar 16 '07 #9

 P: n/a On Mar 16, 5:08 pm, Chris Dollin

 P: n/a Fr************@googlemail.com writes: So what about sqrt? This is in libm, and probably the source code for that library isn't installed, even if the compiler wanted to consult it. So how could the compiler ever know that the implementation of sqrt that the linker would eventually link in didn't use some perverse algorithm that maintained state in a static variable or had some strange side effect? I suppose it could pretend to be the linker, find the sqrt() function and try to see whether the machine code for sqrt was "safe", but this seems like it would be very hard to do reliably. sqrt probably *does* have a side effect, on the value of errno. -- Go not to Usenet for counsel, for they will say both no and yes. Mar 16 '07 #11

 P: n/a Fr************@googlemail.com wrote: On Mar 16, 5:08 pm, Chris Dollin Francine.Ne...@googlemail.com wrote: So what about sqrt? It's a function defined by the Standard, so the compiler knowseverything it wants to know about it, including the answers itgives for particular values. But it surely doesn't know of any side effects calling it may or may not have in any particular implementation? It knows about all the ones the Standard says it has, and it knows what implementation it's targetting. If that implementation isn't conformant, well, that's a problem anyway. -- Chris "electric hedgehog" Dollin "We did not have time to find out everything we wanted to know." - James Blish, /A Clash of Cymbals/ Mar 16 '07 #12

 P: n/a Ben Pfaff wrote On 03/16/07 13:22,: Fr************@googlemail.com writes: >>So what about sqrt? This is in libm, and probably the source code forthat library isn't installed, even if the compiler wanted to consultit. So how could the compiler ever know that the implementation ofsqrt that the linker would eventually link in didn't use some perversealgorithm that maintained state in a static variable or had somestrange side effect? I suppose it could pretend to be the linker, findthe sqrt() function and try to see whether the machine code for sqrtwas "safe", but this seems like it would be very hard to do reliably. sqrt probably *does* have a side effect, on the value of errno. Yes, but in the context at hand y += sqrt(2) + g(i) * h(i); .... the side-effect is not "observable" because it may (or may not) be overwritten by g() and h(), depending on the evaluation order. As for Francine's wider question, Chris Dollin's answer is right: The compiler is allowed to have "private knowledge" of the Standard library functions. Compilers do in fact use such knowledge when they emit a memory-move instruction instead of a call to memcpy(), or use a square root instruction instead of calling sqrt(), or replace printf("%s\n", msg) with puts(msg). This is one of the reasons you can't (reliably) substitute your own functions for Standard library functions: you might stir up the wrath of the Calibans who make the Compiler Magic work. -- Er*********@sun.com Mar 16 '07 #13

 P: n/a On 16 Mar 2007 10:27:01 -0700, in comp.lang.c , Fr************@googlemail.com wrote: >On Mar 16, 5:08 pm, Chris Dollin Francine.Ne...@googlemail.com wrote: So what about sqrt? It's a function defined by the Standard, so the compiler knowseverything it wants to know about it, including the answers itgives for particular values. But it surely doesn't know of any side effects calling it may or maynot have in any particular implementation? Its not allowed to have any, other than those defined in the Standard. -- Mark McIntyre "Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." --Brian Kernighan Mar 16 '07 #14

 P: n/a Fr************@googlemail.com wrote: > .... snip ... > How could the compiler prove that a function is safe to precompute at compile time? If it's in the same file then it could certainly do that, but if it's got external linkage, how can the compiler proceed? My understanding is that all the compiler does is say "here's a call here to function extfunc(), which I know takes 2 arguments and returns a char because I've seen its prototype in some header file, but that's all I know about the function - it's up to the linker to figure out where the function actually lives". So what about sqrt? This is in libm, and probably the source code for that library isn't installed, even if the compiler wanted to consult it. So how could the compiler ever know that the implementation of sqrt that the linker would eventually link in didn't use some perverse algorithm that maintained state in a static variable or had some strange side effect? I suppose it could pretend to be the linker, find the sqrt() function and try to see whether the machine code for sqrt was "safe", but this seems like it would be very hard to do reliably. But the action of sqrt is prescribed by the standard, and it is also undefined behaviour to redefine the sqrt function. So the implementation knows, a-priori, the complete characteristics of that function. Now you know why such redefinition is not allowed. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. -- Posted via a free Usenet account from http://www.teranews.com Mar 16 '07 #15

 P: n/a On Mar 16, 5:29 pm, Chris Dollin

 P: n/a On Mar 16, 11:15 pm, Francine.Ne...@googlemail.com wrote: I don't follow this... Just because I'm using gcc, I don't have to also use the GNU stdlib, do I? gcc is not a C implementation. gcc plus a suitable library plus a suitable linker are a C implementation (or they would be if a few bugs were fixed and the right compiler options are used). In the case of functions like memcpy or strcpy, these functions are defined well enough that the compiler can know exactly what they do, unless the C library is broken, and in that case bets are off anyway. In case of sqrt, in many implementations sqrt is supposed to be IEEE 754 conformant, so the compiler can _know_ what sqrt (2) is. In any case, it can know how sqrt (2) affects errno and it can know that sqrt (2) always returns the same value. Mar 17 '07 #17

 P: n/a On Mar 16, 12:14 pm, Francine.Ne...@googlemail.com wrote: My way of thinking of this is the following. When can the compiler precompute a function? Well, if it's a "safe" function that only modifies its arguments (which of course it gets by value, so it can't do any harm there) and/or any automatic variables it defines. If a function touches a static or extern variable or performs a file operation etc., then it's not safe. How could the compiler prove that a function is safe to precompute at compile time? If it's in the same file then it could certainly do that, but if it's got external linkage, how can the compiler proceed? My understanding is that all the compiler does is say "here's a call here to function extfunc(), which I know takes 2 arguments and returns a char because I've seen its prototype in some header file, but that's all I know about the function - it's up to the linker to figure out where the function actually lives". Many compilers allow the code generation step to be deferred until the link step, so external linkage might well not be an issue. Mar 17 '07 #18

 P: n/a On 16 Mar, 17:14, Francine.Ne...@googlemail.com wrote: My way of thinking of this is the following. When can the compiler precompute a function? Well, if it's a "safe" function that only modifies its arguments (which of course it gets by value, so it can't do any harm there) and/or any automatic variables it defines. If a function touches a static or extern variable or performs a file operation etc., then it's not safe. How could the compiler prove that a function is safe to precompute at compile time? With gcc, you can tell it in the declaration: int foo(int) __attribute__((pure)); /* or "const" */ Is this gcc-specific? -- Bill Pursell Mar 17 '07 #19

 P: n/a ro***********@yahoo.com wrote: On Mar 16, 12:14 pm, Francine.Ne...@googlemail.com wrote: >My way of thinking of this is the following. When can the compilerprecompute a function? Well, if it's a "safe" function that onlymodifies its arguments (which of course it gets by value, so it can'tdo any harm there) and/or any automatic variables it defines. If afunction touches a static or extern variable or performs a fileoperation etc., then it's not safe.How could the compiler prove that a function is safe to precompute atcompile time? If it's in the same file then it could certainly dothat, but if it's got external linkage, how can the compiler proceed?My understanding is that all the compiler does is say "here's a callhere to function extfunc(), which I know takes 2 arguments and returnsa char because I've seen its prototype in some header file, but that'sall I know about the function - it's up to the linker to figure outwhere the function actually lives". Many compilers allow the code generation step to be deferred until the link step, so external linkage might well not be an issue. Surely the compiler and linker are separate programs. Code generation will be done before the compiler exits and before linking begins. -- Joe Wright "Everything should be made as simple as possible, but not simpler." --- Albert Einstein --- Mar 17 '07 #20

 P: n/a Joe Wright wrote: ro***********@yahoo.com wrote: >Many compilers allow the code generation step to be deferred until thelink step, so external linkage might well not be an issue. Surely the compiler and linker are separate programs. They often are, but it's not a requirement, and there's certainly precedent for all-in-one-lump implementations of programming languages. Code generation will be done before the compiler exits and before linking begins. Code generation /can/ be done then. But linkers can do work on the code after the compiler has finished with it. An obvious example is fixing up external jumps on machines with varying lengths of jump instruction. Indeed, there are languages where the compiler routinely generates skeletal code that doesn't get turned into actual machine instructions until the code is /running/, never mind being linked. -- Other Hedgehog "It took a very long time, much longer than the most generous estimates." - James White, /Sector General/ Mar 17 '07 #21

 P: n/a Richard Heathfield wrote: > Consider the following code, which calculates f() * g() + h(): t1 = f(); t2 = g(); t3 = h(); result = t1 * t2 * t3; [...] t3 = h(); t2 = g(); t1 = f(); result = t1 * t2 * t3; ITYM, result = t1 * t2 + t3; -- Denis Kasak Mar 19 '07 #22

 P: n/a Denis Kasak said: Richard Heathfield wrote: >>Consider the following code, which calculates f() * g() + h():t1 = f();t2 = g();t3 = h();result = t1 * t2 * t3; [...] >t3 = h();t2 = g();t1 = f();result = t1 * t2 * t3; ITYM, result = t1 * t2 + t3; Bleargh! Yes, I did mean that, in each case. Sorry. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Mar 19 '07 #23

 P: n/a On Mar 17, 8:26 am, "Bill Pursell"

 P: n/a On Mar 17, 12:25 pm, Chris Dollin

 P: n/a ro***********@yahoo.com wrote: On Mar 17, 12:25 pm, Chris Dollin Joe Wright wrote: Surely the compiler and linker are separate programs. They often are, but it's not a requirement, and there'scertainly precedent for all-in-one-lump implementationsof programming languages. It doesn't need to be "all-in-one-lump." Sorry: I didn't mean to imply that was the only way to have the linker doing "compiler-like" work, just to allude to examples where "the compiler and linker are separate programs" was false [1]. A common implementation of link-time code generation is (fx:snip) I'd be interested in examples, but for the sake of less offtopicality, if you'd email names/google strings/URLs to me I'd be grateful (no obligation intended). [1] I was specifically thinking of Watfor and Algol W. -- Chris "a-sitting on a gate" Dollin There' no hortage of vowel on Uenet. Mar 20 '07 #26

 P: n/a On Mar 20, 4:33 am, Chris Dollin

 P: n/a >On Mar 16, 5:29 pm, Chris Dollin >It [in this case, "it" is, or may be and we will assume it is, "gcc"] >>knows about all the ones the Standard says it has, and it knowswhat implementation it's targetting. In article <11*********************@d57g2000hsg.googlegroups. com> I don't follow this... Just because I'm using gcc, I don't have toalso use the GNU stdlib, do I? No: but if you use some other library, you must tune gcc appropriately. In other words, when you compile gcc (whether with gcc or with some other compiler), you must set various compile-time switches to tell it what to assume about the library or libraries that it will use. In general, the more assumptions you allow it to make, the better code it can generate (where "better" may mean "smaller", "faster", "more colorful", or whatever). >The question seems to be whether the implementation is allowed toproduce side effects not explicitly mentioned in the standard. If not,that does seem to be binding implementors' hands a bit, doesn't it? Indeed. This is why the C standards tend to give implementors a fair bit of latitude. As an implementor, I must do what the Standard says: If it does not say anything, I may do whatever I like. If it does say something, I must do at least that much. If it says a whole lot in great detail, and says that nothing else happens, then -- and only then -- I must do that and only that. -- 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://web.torek.net/torek/index.html Reading email is like searching for food in the garbage, thanks to spammers. Mar 26 '07 #28

### This discussion thread is closed

Replies have been disabled for this discussion.