abed@saturn.wustl.edu (Abed M. Hammoud) (02/21/91)
Hello, This is probably not a smart question...so please forgive me.. I am new to C, and I have been a couple of times encountering the term lvalue...I looked it up in K&R C book but I still don't get it...could some body please help me with a small description. I also have another small question, please take a look at the two loops below and tell me if there is any difference in speed. for (i=0; i < 100; i++) x += i; As compared to... for (i=0; i < 100; i++) x += (float)i; i.e my question is when I precede a variable by a cast does that add to the amount of work done during run-time ?. a fortran convert.... thanks -------------------------------------------------------------- | Abed M. Hammoud abed@saturn.wustl.edu| | Washington University. office:(314)726-7547 | | Electronic Systems & Signals Research Laboratory. | | Dept. of Electrical/Biomedical Engineering. | | St.Louis Mo U.S.A | --------------------------------------------------------------
gwyn@smoke.brl.mil (Doug Gwyn) (02/22/91)
In article <1991Feb21.040145.8678@cec1.wustl.edu> abed@saturn.wustl.edu (Abed M. Hammoud) writes: > i.e my question is when I precede a variable by a cast does > that add to the amount of work done during run-time ?. It might or might not, depending. Note that the right way to express what you are contemplating is "applying a cast", or "converting to a different type", i.e. a more active notion of what a cast means. In some circumstances the compiler may have had to perform the conversion anyway, so an explicit conversion might not add any burden. There are also some short cuts that are permitted that in some cases could avoid having to "really" do the indicated conversion. My recommendation is to EITHER explicitly cast only where necessary to meet strict typing requirements, OR explicitly cast in those circumstances and also every place that the compiler would otherwise perform an implicit conversion. The latter policy is rather hard for anyone other than a C "language lawyer" to get right, so your best bet is to keep casts to a minimum. In many cases, if a cast is actually necessary it indicates an improper choice of types has been made somewhere.
garry@ceco.ceco.com (Garry Garrett) (02/22/91)
In article <1991Feb21.040145.8678@cec1.wustl.edu>, abed@saturn.wustl.edu (Abed M. Hammoud) writes: > I am new to C, and I have been a couple of times encountering > the term lvalue...I looked it up in K&R C book but I still don't > get it... I used to know. (sorry, I forgot) > > I also have another small question, please take a look at > the two loops below and tell me if there is any difference > in speed. > > for (i=0; i < 100; i++) > x += i; > > As compared to... > > for (i=0; i < 100; i++) > x += (float)i; > Again, I don't know the answer to that either, but the reason that I am responding is that I have some other hints for you to speed up you loop. Consider: for (i=99; i; i--) x += i; I also recomend that you decare i as type "register int" or "register float". This will save you alot of time if there is a free register and you compiler can handle register variable. Why is my for loop faster? Your version must load i into a register, load 100 into a register, compare them - putting the value of this comparision into a register, and execute a BEQ (Branch if EQual) instruction. My version will load i into a register (if it isn't already in one), and execute a BZR (Brand on ZeRo) instruction. Almost no optimizing compiler will be able to make this optimization for you. In C, the value 0 is also logical false, and any other value is true. You can make your programs alot faster if you just choose how to use 0 correctly. In this case, counting "backwards" saves you alot of time. If we consider that each of the above instuctions takes a machine cycle (I know, it may not work out that way) then your version takes twice as long as mine, for each itteration. Comming from fortran, this must all seem a bit strange to you (counting backwards, using variables *as* conditions...) but after you get used to it, it comes easy. Good luck. Garry Garrett
sarima@tdatirv.UUCP (Stanley Friesen) (02/23/91)
In article <409@ceco.ceco.com> garry@ceco.ceco.com (Garry Garrett) writes: >> I am new to C, and I have been a couple of times encountering >> the term lvalue...I looked it up in K&R C book but I still don't >> get it... The official definition (from the ANSI standard) is essentially that an lvalue is an expression that refers to an object in memory (as opposed to an expression that generates a value). If find this quite simple. >> I also have another small question, please take a look at >> the two loops below and tell me if there is any difference >> in speed. >> for (i=0; i < 100; i++) >> x += i; >> As compared to... >> for (i=0; i < 100; i++) >> x += (float)i; On any reasonable compiler these will be identical. Assuming that 'x' is of type float the assignment generates an *implicit* conversion to float, which is merely made explicit by the cast. There is no other semantic difference. [Now if 'x' were of type int...] -- --------------- uunet!tdatirv!sarima (Stanley Friesen)
garry@ceco.ceco.com (Garry Garrett) (02/24/91)
In article <339@smds.UUCP>, rh@smds.UUCP (Richard Harter) writes: > In article <409@ceco.ceco.com>, garry@ceco.ceco.com (Garry Garrett) writes: > > In article <1991Feb21.040145.8678@cec1.wustl.edu>, abed@saturn.wustl.edu (Abed M. Hammoud) writes: > > > > for (i=0; i < 100; i++) > > > x += i; > > > Consider: > > > > for (i=99; i; i--) > > x += i; > > This is better done as > > for (i=100;--i>=0;) > x += i; > I must disagree with you. For starters, consider the situation where i == 0. Your loop adds 0 to x. Secondly, as my discussion that you deleted pointed out, performing "--i>=0" would take more time than "i" The reason is that both i and 0 must be loaded into registers, compared, and a branch instruction executed for your version. My version loads i into a register and performs a branch. 2 steps vs. your 4 steps. Is I pointed out making i a register variable would also speed things up. You did have a good point though about moving the deciment inside of the condition: for(i=100; --i; ) x += i; This would be even faster than my proposed solution. Bear in mind that C is one of the hardest languages in the world to optimize. For instance, in pascal the index of a for loop cannot be referenced outside of that loop, thus the code can be optimized by making that index a register variable. In C, you can reference i later in the code, so the compiler cannot make that assumption for you. You must explicitly ask the compiler to make a varible into a register variable by declairing it as such. There are many reasons why C is harder to optimize, so when you are programming in C, you must not count on an optimizer to clean things up for you. If your computer's CPU's ALU has an option to compare a register to 0, and you assembler has a command to use that option, and your C compiler knows that that option exists, and your C compiler is smart enough to optimize --i>=0 to make use of that assemby instruction, then your method would compile to: load i into a register, compare it to 0, conditional branch. 3 instructions to my 2. Sorry, but my code is still faster. Garry Garrett
pfalstad@phoenix.Princeton.EDU (Paul Falstad) (02/24/91)
garry@ceco.ceco.com (Garry Garrett) wrote: >In article <339@smds.UUCP>, rh@smds.UUCP (Richard Harter) writes: >> This is better done as >> >> for (i=100;--i>=0;) >> x += i; > I must disagree with you. For starters, consider the situation where >i == 0. Your loop adds 0 to x. What he meant was, for(i=0; i <= 100; i++) is not equivalent to for(i=100; i; i--) for a non-trivial loop body. Your version executes the loop 1 less time than his. If you really want to optimize this code, you could just say x = 5050. >pointed out, performing "--i>=0" would take more time than "i" The reason is >that both i and 0 must be loaded into registers, compared, and a branch >instruction executed for your version. My version loads i into a register >and performs a branch. 2 steps vs. your 4 steps. Is I pointed out making i Even without optimization turned on, my compiler was smart enough not to load 0 into a register. It took 2 instructions to do i>=0. > Bear in mind that C is one of the hardest languages in the world to >optimize. For instance, in pascal the index of a for loop cannot be referenced >outside of that loop, thus the code can be optimized by making that index a >register variable. In C, you can reference i later in the code, so the compiler >cannot make that assumption for you. You must explicitly ask the compiler >to make a varible into a register variable by declairing it as such. There What? What difference does it make if i is referenced later? The only reason it might not be possible to make i a register variable is that i might need to be addressable. I don't see what next-use information has to do with it. With optimization turned on, both compilers I tried put i and x in registers. > If your computer's CPU's ALU has an option to compare a register to 0, >and you assembler has a command to use that option, and your C compiler knows >that that option exists, and your C compiler is smart enough to optimize --i>=0 >to make use of that assemby instruction, then your method would compile to: >load i into a register, compare it to 0, conditional branch. 3 instructions to >my 2. Sorry, but my code is still faster. I don't think there will be a large difference. In fact, the Sun SPARC compiler took 5 instructions to do your version, 3 for his. Don't think you're saving any time by writing "i" instead of "i != 0"; some compilers automatically convert "i" to "i != 0" internally. -- Paul Falstad, pfalstad@phoenix.princeton.edu PLink:HYPNOS GEnie:P.FALSTAD I think there should be more race prejudice. <slap> LESS race prejudice. Princeton University apologizes for the content of this article.
dsebbo@dahlia.uwaterloo.ca (David Ebbo) (02/25/91)
> Bear in mind that C is one of the hardest languages in the world to >optimize. For instance, in pascal the index of a for loop cannot be referenced >outside of that loop, thus the code can be optimized by making that index a >register variable. ... > >Garry Garrett No. In Pascal, you can use any integer variable as a for loop index, and it can be referenced outside the loop. However, Ada behaves like you said. The loop index does not have to be explicitly declared. It cannot be used outside the loop. David Ebbo
torek@elf.ee.lbl.gov (Chris Torek) (02/26/91)
In an article whose referent has been deleted (perhaps <414@ceco.cecom.com>?) Garry Garrett writes: >>For instance, in pascal the index of a for loop cannot be referenced >>outside of that loop ... In article <1991Feb25.143544.11950@watdragon.waterloo.edu> dsebbo@dahlia.uwaterloo.ca (David Ebbo) writes: >No. In Pascal, you can use any integer variable as a for loop index, and it >can be referenced outside the loop. Garry Garrett is correct. Pascal (at least `old' Pascal; I have not kept up with the ISO variants) makes three constraints on loop index variables: - they must be local; - they may not be altered inside the loop; - they may not be examined outside the loop. Many compilers do not enforce these restrictions, but program foo; var i : integer; procedure nothing; begin end; begin for i := 1 to 10 do nothing end. is illegal because `i' is global; procedure bar; var i : integer; begin for i := 1 to 10 do i := 3 end; is illegal because `i' is altered inside the loop; and procedure baz; var i : integer; begin for i := 1 to 5 do nothing; writeln('i=5? i=', i) end; is illegal because `i' is used outside the loop without first being redefined. Changing baz to: procedure baz; var i : integer; begin for i := 1 to 5 do nothing; i := 5; writeln('i=', i) end; makes it legal. -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab EE div (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/26/91)
In article <1991Feb25.143544.11950@watdragon.waterloo.edu>, dsebbo@dahlia.uwaterloo.ca (David Ebbo) writes: > No. In Pascal, you can use any integer variable as a for loop index, and it > can be referenced outside the loop. There are three claims involved in this sentence, and all of them are false. (1) Pascal index variables need not be integer variables; they may be of any discrete type (integer, enumeration, subrange of either). (2) It is not the case that *any* variable of an appropriate type may be used, only a variable local to the current block may be used. program xx; var i: integer; procedure p; begin for i := 1 to 2 do ... is *illegal* because 'i' is not local to 'p'. (3) The value of an index variable is *not* defined after a 'for' loop. One Pascal compiler I've used stuffed a special value into index variables after a loop was exited, which value caused a trap if you tried to fetch it (B6700 fans: it was a Tag 6 word). The Pascal standard is clear on this. Some Pascal system may not check (2) and/or (3), but that's like a C system not trapping attempts to dereference NULL, undefined behaviour not allowed in a standard- conforming program is undefined behaviour. Surely C can stand on its own merits without making false claims about another programming notation? -- The purpose of advertising is to destroy the freedom of the market.
torek@elf.ee.lbl.gov (Chris Torek) (02/27/91)
In article <10257@dog.ee.lbl.gov> I claiemd that Pascal for loop index variables `must be local' (which is true) and gave a bogus example: > program foo; > var i : integer; > procedure nothing; begin end; > begin for i := 1 to 10 do nothing end. >is illegal because `i' is global; That should be: program foo; var i : integer; procedure nothing; begin end; procedure p; begin for i := 1 to 10 do nothing end; begin p end. This is illegal because `i' is not local to procedure `p'. -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab EE div (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov
rjc@uk.ac.ed.cstr (Richard Caley) (02/27/91)
In article <414@ceco.ceco.com>, Garry Garrett (gg) writes:
gg> Bear in mind that C is one of the hardest languages in the world
gg> to optimize. For instance, in pascal the index of a for loop
gg> cannot be referenced outside of that loop, thus the code can be
gg> optimized by making that index a register variable.
a) Whether you reference outside will not affect whether it can be
made a regiser variable (though it might affect the advisability).
b) it is amazingly trivial for the compiler to look and see if it is
referenced outside.
gg> You must explicitly ask the compiler to make a varible into
gg> a register variable by declairing it as such.
There is no way to do this. `register' is, at best, a hint. The
compiler will stick what it likes into registers.
gg> There are many reasons why C is harder to optimize,
To coin the old phrase -- name three.
The only ones which comes to mind are pointers and casts, both of
which will only be a problem if you use them, so there is no loss.
gg> so when you are programming in C, you must not count on an
gg> optimizer to clean things up for you.
If any of the trivial micro-optimisations which were listed in that
article make any difference, I think someone needs to kick the
compiler writer:-)
Counting down rather than up is only faster if compare against 0 is
faster on your machine. The compiler is more likely to knowthat than
you.
gg> Sorry, but my code is still faster.
It's only faster if it runs faster, arguing about hypothetical
(broken) compilers on hypothetical machines proves nothing.
--
rjc@cstr.ed.ac.ukbright@nazgul.UUCP (Walter Bright) (03/06/91)
/Bear in mind that C is one of the hardest languages in the world to /optimize. For instance, in pascal the index of a for loop cannot be referenced /outside of that loop, thus the code can be optimized by making that index a /register variable. ... C is hard to optimize, but that is because of the aliasing problem, not identification of loop variables. Standard textbook algorithms exist (see the Dragon Book) which can identify the loop variable(s) from out of a rat's nest of goto's. It is also easilly determined if the loop variable is used after exit of the loop or not. In fact, I'd say it was easier and more reliable than fiddling with the loop constructs in a parse tree... The right way to optimize is to convert everything to a bunch of expressions connected by goto's. Then analyze the goto's to determine the loops and everything else needed. I've implemented these algorithms in Zortech's optimizer, and they do work. They did have to be modified, however, to support the idea that ints and pointers are not the same size!