C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Sutter's for loop optimization Goto page 1, 2, 3  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Brandt Dusthimer Guest Posted: Thu Jan 20, 2005 12:21 pm    Post subject: Sutter's for loop optimization Hello. I recently got Herb Sutter's Exceptional C++ and have a question about one of the statements in it. The book says that we should do something like so for 'for' loops: vector<T>::const_iterator end = vec.end(); for (vector<T>::const_iterator iter = vec.begin(); iter != end; ++iter) { // something here } instead of just for (vector<T>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) { // something here } So that every time we iterate through the loop we don't have to call vec.end(). My question is, aren't most compilers smart enough to do the optimizations themselves or, as seems to be the general C/C++ rule, is this not done because you did not specifically say to have it done? Thanks, Brandt Dusthimer [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Matthew D Moss Guest Posted: Thu Jan 20, 2005 6:27 pm    Post subject: Re: Sutter's for loop optimization The condition is checked every time through the loop, and the compiler can't know that vec.end() is the same every time. Personally, I prefer to keep the end scoped the same as the iterator, and tend to write my loops like: <pre> for (vector<T>::const_iterator iter = vec.begin(), end = vec.end(); iter != end; ++iter) </pre> [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Joe Guest Posted: Thu Jan 20, 2005 6:32 pm    Post subject: Re: Sutter's for loop optimization In general it is not done because the STL is a library and not a part of the language itself. In general, the compiler has no idea what vec.end() might be doing, so how can it eliminate the call? Now, we all know what it is likely to be doing, but if I were weird enough, I might have written my own class to replace the compiler's vector and it might have some side effect like incrementing a mutable variable to count the number of times end() was called. Ok, so it's not a likely scenereo, but the point is that there are replacement STL implementations and the compiler can't make any real assumptions about what calls are actually doing. Code elimination is usually found in constructs where all the elements are language features and the compiler could expect to know what you are doing. The answer in this case would be to use std::for_each(). Then you don't need to worry about it. joe [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top jarl Guest Posted: Thu Jan 20, 2005 6:33 pm    Post subject: Re: Sutter's for loop optimization Hi Brandt, Unless the "vector::end" method gets inlined (in the for-loop) I doubt if the compiler is able to do much intelligent optimization for you. Global- or profile guided-optimization might aid the compiler in figuring out that the "end" call is cacheable (or not) but normal optimizers would struggle. Jarl Brandt Dusthimer wrote: Quote: Hello. I recently got Herb Sutter's Exceptional C++ and have a question about one of the statements in it. The book says that we should do something like so for 'for' loops: vector<T>::const_iterator end = vec.end(); for (vector<T>::const_iterator iter = vec.begin(); iter != end; ++iter) { // something here } instead of just for (vector<T>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) { // something here } So that every time we iterate through the loop we don't have to call vec.end(). My question is, aren't most compilers smart enough to do the optimizations themselves or, as seems to be the general C/C++ rule, is this not done because you did not specifically say to have it done? Thanks, Brandt Dusthimer [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alberto Barbati Guest Posted: Thu Jan 20, 2005 6:43 pm    Post subject: Re: Sutter's for loop optimization Brandt Dusthimer wrote: Quote: Hello. I recently got Herb Sutter's Exceptional C++ and have a question about one of the statements in it. The book says that we should do something like so for 'for' loops: vector<T>::const_iterator end = vec.end(); for (vector<T>::const_iterator iter = vec.begin(); iter != end; ++iter) { // something here } instead of just for (vector<T>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) { // something here } So that every time we iterate through the loop we don't have to call vec.end(). My question is, aren't most compilers smart enough to do the optimizations themselves or, as seems to be the general C/C++ rule, is this not done because you did not specifically say to have it done? Well, it depends a great deal on what "something here" is. If the loop body is "simple enough" then I expect a smart compiler to be able to move the invariant code outside the loop and to produce equivalent assembly for both examples. For example VC71 lies in this category. The question is: how simple is "simple enough"? "Simple enough" means that the compiler shall be able to detect that there are *no* possible side-effects on the value of vec.end(). That means: *very* simple, unless the compiler is *very* smart. Just put any non-inlined call and it may be already too much. Even in a simple case like: for (vector<T>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) { iter->Do(); } if Do() is non-inline the compiler will probably not be able to perform the optimization. Even if Do() is inline, then it should not call any non-inline function, or we would be again in a bad position. With compilers that supports link-time code generation, the situation might improve, but I have no "measurable" experience in that case. Alberto [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Victor Bazarov Guest Posted: Thu Jan 20, 2005 7:51 pm    Post subject: Re: Sutter's for loop optimization Brandt Dusthimer wrote: Quote: Hello. I recently got Herb Sutter's Exceptional C++ and have a question about one of the statements in it. The book says that we should do something like so for 'for' loops: vector<T>::const_iterator end = vec.end(); for (vector<T>::const_iterator iter = vec.begin(); iter != end; ++iter) { // something here } instead of just for (vector<T>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) { // something here } So that every time we iterate through the loop we don't have to call vec.end(). My question is, aren't most compilers smart enough to do the optimizations themselves or, as seems to be the general C/C++ rule, is this not done because you did not specifically say to have it done? The compiler is probably not smart enough (or sophisticated enough) to see that "// something here" does not change the size of the vector 'vec'. It is rather difficult for it to figure that out. That's where you come in, a programmer, who can help the compiler. Imagine how smart does the compiler have to be to know things like that? What if 'vec' is not a local variable but a member? What if inside the loop you call another member function (perhaps indirectly), which may actually change the size of the 'vec' vector? How in the world would the compiler figure that out? Yes, it is theoretically possible to make the optimiser good enough so it can at least attempt to optimise certain things *if* no adverse conditions exist. IOW, *if* 'vec' is a local variable *and* it is not getting passed to some function inside the loop that can change its size (which is rather *not* obvious, since you do something to the iterator[s], which *might* be aware of the container they are iterating), but just imagine how long it would take to compile a simple loop like that if the optimiser has to make sure it can pull the call to 'size()' outside of the loop. IOW, while theoretically possible, it's not *feasible* to create such optimiser. V [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top msalters Guest Posted: Thu Jan 20, 2005 7:57 pm    Post subject: Re: Sutter's for loop optimization Brandt Dusthimer wrote: Quote: Hello. I recently got Herb Sutter's Exceptional C++ and have a question about one of the statements in it. The book says that we should do something like so for 'for' loops: vector<T>::const_iterator end = vec.end(); for (vector<T>::const_iterator iter = vec.begin(); iter != end; ++iter) { // something here } instead of just for (vector<T>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) { // something here } So that every time we iterate through the loop we don't have to call vec.end(). IIRC, he also notes that you should not do such things if you are changing vec from the loop. More importantly, you shouldn't use such a loop at all if you're modifying a vector. You might be able to modify e.g. a list in this way, but vector invalidates its iterators too easy (e.g. on insert and clear ) Quote: My question is, aren't most compilers smart enough to do the optimizations themselves or, as seems to be the general C/C++ rule, is this not done because you did not specifically say to have it done? They're smart enough to do it only if they can prove that end==vec.end() for the entire loop, which usually means that they were able to inline every function in the for-loop. The compiler has to generate correct code for the case where some invisible code does a vec.push_back(). Regards, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Pavel Vozenilek Guest Posted: Thu Jan 20, 2005 8:03 pm    Post subject: Re: Sutter's for loop optimization "Brandt Dusthimer" wrote: Quote: Hello. I recently got Herb Sutter's Exceptional C++ and have a question about one of the statements in it. The book says that we should do something like so for 'for' loops: vector<T>::const_iterator end = vec.end(); for (vector<T>::const_iterator iter = vec.begin(); iter != end; ++iter) { // something here } instead of just for (vector<T>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) { // something here } So that every time we iterate through the loop we don't have to call vec.end(). My question is, aren't most compilers smart enough to do the optimizations themselves or, as seems to be the general C/C++ rule, is this not done because you did not specifically say to have it done? This very much depened on content of "something else". If it is complicated enough then optimizer may give up. I think the book's suggestion is good habit to be followed. /Pavel [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top west Guest Posted: Fri Jan 21, 2005 10:18 am    Post subject: Another Question So, by the general response of the newsgroup, I'm assuming that to do a lookup on the value of 'end' is more efficient than calling 'end()'? Thanks, Brandt Dusthimer [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top White Wolf Guest Posted: Fri Jan 21, 2005 10:32 am    Post subject: Re: Sutter's for loop optimization Hi All, Long time no C++. I will run the risk of being shut down, but I will make my points anyway. I have a bad brain day. 1.) The compiler may very well know that the end() stays constant during the loop.(*) 2.) Saying that "the STL is not part of the language" is true, but irrelevant. What is part of the language is the standard library (including the std::vector), about which the compiler is allowed to know everything. (*) But as pointed out by others, it may not be worth it. Little mind-running-wild (or little-mind running wild if you prefer;-): Case #1: The loop body only contains const member calls to the vector, and nothing else the compiler cannot see (the full definition of). Case #2: The compiler can see the definition of everything called, and in all those, there are only const calls to the vector Case #3: The compiler cannot see all the code, but in some implementation defined manner (see gcc.gnu.org on __attribute and pure) it is told, that none of the called functions it cannot see are going to change anything in the vector I know it is not done yet in compilers, but with clever additions to the language (about which we have had two people magically turning in the exact same proposal, independently) we can help the compiler to an easier job. I wonder what tricks (as bad effects) this end() reading can do on SMP machines. For a heavily used vector the sizeof-part of it and the allocated array part of it may be in very different places in the memory. I wonder what does that do for caches. I am not even close to an expert of it, but if the end() value shares its cache line with values frequently changed by other CPUs, could that cause the end() value to be read always from main memory? Because that would suc^H^H^H make the call pretty slow. Although we do have a brilliant memory model for threaded execution already proposed ; if you feel it is way too off topic here but you have an answer for this question drop me a mail. But please no mails with links to old usenet articles, because I can never figure out anything from those cascading links. :-) -- WW aka Attila ::: Defeat isn't bitter if you don't swallow it. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top msalters Guest Posted: Sat Jan 22, 2005 4:53 am    Post subject: Re: Sutter's for loop optimization Joe wrote: Quote: In general it is not done because the STL is a library and not a part of the language itself. The std::vector stuff /is/ part of the language, just look at the standard. Some Quote: In general, the compiler has no idea what vec.end() might be doing, so how can it eliminate the call? Now, we all know what it is likely to be doing, but if I were weird enough, I might have written my own class to replace the compiler's vector and it might have some side effect like incrementing a mutable variable to count the number of times end() was called. Ok, so it's not a likely scenereo, but the point is that there are replacement STL implementations and the compiler can't make any real assumptions about what calls are actually doing. It's the other way around in fact; the replacement STL has to deal with all the compiler weirdness. E.g. if the compiler uses a std::string in its RTTI implementation, and assumes some behavior, the replacement should follow that. If the compiler assumes that end() is really const, i.e. std::vector<> has no mutable members, then any replacement will have to follow that. Why do you think there's a rule that say you can't define your own functions in namespace std? Regards, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Victor Bazarov Guest Posted: Sat Jan 22, 2005 5:03 am    Post subject: Re: Another Question west wrote: Quote: So, by the general response of the newsgroup, I'm assuming that to do a lookup on the value of 'end' is more efficient than calling 'end()'? For some containers, definitely. So, generally, yes. I think it would be better to say that "calling 'end()' is no more efficient than to do the lookup, given that your container doesn't actually grow or shrink". IOW, calling 'end()' could be worse or could be the same. V [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Attila Feher Guest Posted: Sat Jan 22, 2005 5:08 am    Post subject: Re: Another Question west wrote: Quote: So, by the general response of the newsgroup, I'm assuming that to do a lookup on the value of 'end' is more efficient than calling 'end()'? What do you mean by "lookup on the value of 'end'"? Attempt to answer the question I did not understand: If you "copy away" the value returned by end(), and make it const or simply not change it in the loop, then the compiler knows (for example) that it can keep it in a fast register, or do any other optimization it wishes. So it has nothing to do with calling end() (since it is most probably inlined anyway). What matters is that the compiler can more easily figure out that the value will not change. -- Attila aka WW [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel K. O. Guest Posted: Sat Jan 22, 2005 11:27 am    Post subject: Re: Sutter's for loop optimization Brandt Dusthimer escreveu: Quote: My question is, aren't most compilers smart enough to do the optimizations themselves or, as seems to be the general C/C++ rule, is this not done because you did not specifically say to have it done? A quick test here shows that GCC is smart enough to inline vector<>::begin()/end(), even when using the smallest optimization level; no matter if you use just "-O1" or "-O3 -fexpensive-optimizations", the code generated is the same. Try for yourself: ---- #include <vector> using namespace std; extern void bar(vector<int>& v , vector<int>::const_iterator & i); void foo1(vector<int>& vec) { for (vector<int>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) bar(vec, iter); } void foo2(vector<int>& vec) { vector<int>::const_iterator end = vec.end(); for (vector<int>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) bar(vec, iter); } ---- Then compile it with: g++ file.cpp -S -o file.S -O1 or g++ file.cpp -S -o file.S -fverbose-asm -fexpensive-optimizations -O3 And see for yourself the file.S output. I don't have other C++ compilers here, but I think other "mainstream" C++ compilers also do this job well. Daniel K. O. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Sat Jan 22, 2005 6:44 pm    Post subject: Re: Sutter's for loop optimization [email]danielko1 (AT) bol (DOT) com.br[/email] (Daniel K. O.) wrote (abridged): Quote: A quick test here shows that GCC is smart enough to inline vector<>::begin()/end(), even when using the smallest optimization level; no matter if you use just "-O1" or "-O3 -fexpensive-optimizations", the code generated is the same. [...] vector<int>::const_iterator end = vec.end(); for (vector<int>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter) bar(vec, iter); In this case, the local variable end is not used. Was that a typo in your article? If that is fixed, I don't see how the compiler can generate the same code because the routines have different semantics, depending on the definition of bar. Is it doing whole program analysis, even at the lowest optimisation level? Or is GCC producing bad code when bar is like: void bar(vector<int>& v , vector<int>::const_iterator & i) { if (*i) v.push_back( 0 ); } -- Dave Harris, Nottingham, UK [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2, 3  Next Page 1 of 3   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.