C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  vector::size() - To cache or not to cache? Goto page 1, 2, 3  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Kelly Walker Guest Posted: Fri Jul 29, 2005 11:10 am    Post subject: vector::size() - To cache or not to cache? When writing a plain old loop over the elements in a std::vector, there are two options involving the size() operation (as opposed to using iterators): ********************* vector<int> v; // Add a bunch of ints to v size_t numInts = v.size(); // cache the size for(size_t i=0; i<numInts; ++i) { do_something(v[i]); } ********************* vs. ********************* vector // Add a bunch of ints to v for(size_t i=0; i do_something(v[i]); } In the second version, are most compilers smart enough to optimize the repeated call of size() away to a single call? Or will size() be called size() times (i.e. every time the loop condition is checked until it fails)? Does it even matter since size() is (most likely) inlined? Obviously, these questions apply to other containers using iterators where the result of end() could be cached to avoid repeatedly calling it. The second version is more succinct and to the point. My gut instinct is that it is just as quick as the first version. However, lingering doubt makes me tend to use the first version to avoid repeated calls to size(). I know optimization is a secondary concern (make it work and THEN make it work faster, if necessary) but looping over containers is so common that choosing the faster version (if either) is important. Thanks in advance. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Fri Jul 29, 2005 1:41 pm    Post subject: Re: vector::size() - To cache or not to cache? Quote: When writing a plain old loop over the elements in a std::vector, there are two options involving the size() operation (as opposed to using iterators): ********************* vector<int> v; // Add a bunch of ints to v size_t numInts = v.size(); // cache the size for(size_t i=0; i<numInts; ++i) { do_something(v[i]); } ********************* vs. ********************* vector // Add a bunch of ints to v for(size_t i=0; i do_something(v[i]); } In the second version, are most compilers smart enough to optimize the repeated call of size() away to a single call? No, at least not last time when I have checked (well, even not counting the fact that do_something actually can change 'size()' of 'v' as side-effect). Anyway, if you insist of this variant over iterators (I do, but my container stores 'count' instead of 'end' in its implementation; 'end - begin' operation might be pretty costly), I strongly recommend second variant as slightly more bullet-proof. Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michael Jørgensen Guest Posted: Fri Jul 29, 2005 3:10 pm    Post subject: Re: vector::size() - To cache or not to cache? "Kelly Walker" <kelly_g_walker (AT) earthlink (DOT) net> wrote Quote: When writing a plain old loop over the elements in a std::vector, there are two options involving the size() operation (as opposed to using iterators): [snip] Quote: vector<int> v; // Add a bunch of ints to v for(size_t i=0; i<v.size(); ++i) { do_something(v[i]); } [snip] Quote: The second version is more succinct and to the point. My gut instinct is that it is just as quick as the first version. However, lingering doubt makes me tend to use the first version to avoid repeated calls to size(). I know optimization is a secondary concern (make it work and THEN make it work faster, if necessary) but looping over containers is so common that choosing the faster version (if either) is important. Thanks in advance. Well, if you are so concerned with speed, please realize that the array subscript may be time consuming (since it generally involves an integer multiplication). The same loop could be implemented using iterators as: for (std::vector do_something(*i); } Whether this form is actually faster may depend on many things, but it should not be any slower. Of course, your original question now applies to whether v.end() is cached. For that, I have no answer... -Michael. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Roger Orr Guest Posted: Sat Jul 30, 2005 12:26 am    Post subject: Re: vector::size() - To cache or not to cache? "Kelly Walker" <kelly_g_walker (AT) earthlink (DOT) net> wrote Quote: When writing a plain old loop over the elements in a std::vector, there are two options involving the size() operation (as opposed to using iterators): ********************* vector<int> v; // Add a bunch of ints to v size_t numInts = v.size(); // cache the size for(size_t i=0; i<numInts; ++i) { do_something(v[i]); } I prefer: for ( size_t i=0, numInts=v.size(); i as it keeps the 'numInts' variable scoped. Quote: vector // Add a bunch of ints to v for(size_t i=0; i do_something(v[i]); } In the second version, are most compilers smart enough to optimize the repeated call of size() away to a single call? If you care -- measure for the actual compilers you care about. It is likely the code is a function call in a debug build and inlined in a release build, but this is highly compiler (and compiler release) dependent. Roger Orr -- MVP in C++ at www.brainbench.com [ 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 Jul 30, 2005 12:26 am    Post subject: Re: vector::size() - To cache or not to cache? [email]kelly_g_walker (AT) earthlink (DOT) net[/email] (Kelly Walker) wrote (abridged): Quote: for(size_t i=0; i<v.size(); ++i) { do_something(v[i]); } In the second version, are most compilers smart enough to optimize the repeated call of size() away to a single call? Often not. Because often the compiler is unable to prove that do_something() does not change v, especially if v is a reference or a member variable. However, recalculating v.size() will probably be fast; faster than the comparison, for example. You really need to measure with your compiler and your hardware to be sure. Quote: size_t numInts = v.size(); // cache the size for(size_t i=0; i You can also write this as: for(size_t i=0, s=v.size(); i and declaring the extra variable only adds a few characters. Fastest is probably to count backwards: for (int i = v.size()-1; i >= 0; --i) because it is comparing against constant 0 instead of a variable s or expression v.size(). It's too error-prone for casual use, though. -- 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 Mirek Fidler Guest Posted: Sat Jul 30, 2005 10:21 am    Post subject: Re: vector::size() - To cache or not to cache? Dave Harris wrote: Quote: kelly_g_walker (AT) earthlink (DOT) net (Kelly Walker) wrote (abridged): for(size_t i=0; i do_something(v[i]); } In the second version, are most compilers smart enough to optimize the repeated call of size() away to a single call? Often not. Because often the compiler is unable to prove that do_something() does not change v, especially if v is a reference or a member variable. However, recalculating v.size() will probably be fast; faster than the comparison, for example. Well, depends on vector implementation, but it can be pretty slow. vector usually stores begin - end pair. The real calculation is (end - begin) / sizeof(T), which can be pretty bad if division cannot be performed by shift (AFAIK integer division is still quite expensive even on modern CPU). Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bo Persson Guest Posted: Sat Jul 30, 2005 11:52 am    Post subject: Re: vector::size() - To cache or not to cache? "Dave Harris" <brangdon (AT) cix (DOT) co.uk> skrev i meddelandet news:memo.20050729203825.460D (AT) brangdon (DOT) m... Quote: size_t numInts = v.size(); // cache the size for(size_t i=0; i<numInts; ++i) { You can also write this as: for(size_t i=0, s=v.size(); i and declaring the extra variable only adds a few characters. And a few more chances to get it wrong. Variable names like i, s, and v are very sensitive to "spelling errors". Also, how do you know that the vector::size() is not defined as size_type size() const { return m_size; } How do you improve on that? By making a copy s on the stack? Quote: Fastest is probably to count backwards: for (int i = v.size()-1; i >= 0; --i) because it is comparing against constant 0 instead of a variable s or expression v.size(). It's too error-prone for casual use, though. Yes, not only is there a risk of forgetting the -1, you also stand the risk of having a size() that doesn't fit in an int. Premature optimizations, etc... Bo Persson [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Sat Jul 30, 2005 4:51 pm    Post subject: Re: vector::size() - To cache or not to cache? Quote: Also, how do you know that the vector::size() is not defined as size_type size() const { return m_size; } How do you improve on that? By making a copy s on the stack? Well, actually, effective std::string implementation is very unlikely to be done like this. From performance standpoint, cacheing s here is a good idea. Anyway, I would still recommend using slower variant as safer. (Well, actually, I would recommend using NTL Vector which has GetCount implemented just like you suggest - the thing is that you can optimize vector implementation for indicies or for iterators. It is obvious what path STL has to take). Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bo Persson Guest Posted: Sun Jul 31, 2005 1:05 am    Post subject: Re: vector::size() - To cache or not to cache? "Mirek Fidler" <cxl (AT) volny (DOT) cz> skrev i meddelandet news:3l1gvoF10hiitU1 (AT) individual (DOT) net... Quote: Also, how do you know that the vector::size() is not defined as size_type size() const { return m_size; } How do you improve on that? By making a copy s on the stack? Well, actually, effective std::string implementation is very unlikely to be done like this. From performance standpoint, cacheing s here is a good idea. Too bad Microsoft/Dinkumware hasn't understood this, as VC2005 Beta still contains this for basic_string: size_type __CLR_OR_THIS_CALL size() const { // return length of sequence return (_Mysize); } Quote: Anyway, I would still recommend using slower variant as safer. But it was introduced in this thread as faster. :-) Quote: (Well, actually, I would recommend using NTL Vector which has GetCount implemented just like you suggest - the thing is that you can optimize vector implementation for indicies or for iterators. It is obvious what path STL has to take). Not obvous at all, as shown by the diverging implementations. Low level optimizations, based on false premises, is not the way to go. Bo Persson [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Sun Jul 31, 2005 11:51 am    Post subject: Re: vector::size() - To cache or not to cache? Bo Persson wrote: Quote: "Mirek Fidler" <cxl (AT) volny (DOT) cz> skrev i meddelandet news:3l1gvoF10hiitU1 (AT) individual (DOT) net... Also, how do you know that the vector::size() is not defined as size_type size() const { return m_size; } How do you improve on that? By making a copy s on the stack? Well, actually, effective std::string implementation is very unlikely to be done like this. From performance standpoint, cacheing s here is a good idea. Too bad Microsoft/Dinkumware hasn't understood this, as VC2005 Beta still contains this for basic_string: size_type __CLR_OR_THIS_CALL size() const { // return length of sequence return (_Mysize); } I guess we were speaking about std::vector? Microsoft/Dinkumware, VC2005 Beta std::vector:: size_type size() const { // return length of sequence return (_Myfirst == 0 ? 0 : _Mylast - _Myfirst); } GCC library: size_type size() const { return size_type(end() - begin()); } STLport: size_type size() const { return size_type(this->_M_finish - this->_M_start); } Makes perfect sense for STL. Quote: Anyway, I would still recommend using slower variant as safer. But it was introduced in this thread as faster. NO, it is not, at least with any current implementation. Implementation that would have this faster would have slower other operations (like end() and to some degree push_back). Quote: Not obvous at all, as shown by the diverging implementations. Absolutely obvious, as shown with all existing implementation. They do NOT diverge. They agree on this. Check better next time. Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Sun Jul 31, 2005 11:54 am    Post subject: Re: vector::size() - To cache or not to cache? Quote: Well, actually, effective std::string implementation is very unlikely Ooops Of course, I was speaking about std::vector... Sorry. Quote: Too bad Microsoft/Dinkumware hasn't understood this, as VC2005 Beta still contains this for basic_string: size_type __CLR_OR_THIS_CALL size() const { // return length of sequence return (_Mysize); } Mirek [ 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: Sun Jul 31, 2005 4:46 pm    Post subject: Re: vector::size() - To cache or not to cache? [email]bop (AT) gmb (DOT) dk[/email] (Bo Persson) wrote (abridged): Quote: Also, how do you know that the vector::size() is not defined as size_type size() const { return m_size; } Did you miss the bit where I said you should check your local implementation? Incidently, do you know of an implementation that actually has std::vector::size() defined like that? Quote: How do you improve on that? By making a copy s on the stack? Indeed. The compiler knows that a copy on the stack cannot be changed by do_something(), so it becomes a loop invariant and can be held in a register. If the vector is passed by reference or is an instance variable, and do_something() is not inlined, the compiler will probably assume that m_size can change in the loop so it must keep loading it from memory. And then it must repeat any calculations that depend on that value. By the same token, it can be faster to cache v.begin(). Quote: Fastest is probably to count backwards: for (int i = v.size()-1; i >= 0; --i) because it is comparing against constant 0 instead of a variable s or expression v.size(). It's too error-prone for casual use, though. Yes, not only is there a risk of forgetting the -1, you also stand the risk of having a size() that doesn't fit in an int. Another classic mistake is to continue using size_t instead of int, so that i>=0 is always true. I just checked with MS VC++6, and it wasn't faster anyway. The compiler applied the same optimisation (to the caching size version) without being told, so the counting-forward and the counting-backward produced virtually identical assembler. Both used two loop variables, one counting down by ones to zero, and the other counting up by sizeof(T). I tried various loops with this compiler. Here are the results: Version Assembler instructions Array-naive: 20 Array-size: 9 Array-best: 6 Iterator-naive: 7 Iterator-best: 6 For_each: 6 Obviously your compiler may vary. I really hope modern compilers improve on Array-naive. Some may improve on std::for_each(), eg by unrolling the loop. If vec is a local variable and not passed by reference or a member variable, everything changes. Array-naive: void test0( Vec &vec ) { for (size_t i = vec.size(); i < vec.size(); ++i) do_something( vec[i] ); } Array-size: for (size_t i = 0, s = vec.size(); i < s; ++i) do_something( vec[i] ); Array-best: T *begin = vec.begin(); for (size_t i = 0, s = vec.size(); i < s; ++i) do_something( begin[i] ); Iterator-naive: for (Vec::iterator i = vec.begin(); i != vec.end(); ++i) do_something( *i ); Iterator-best: for (Vec::iterator i = vec.begin(), e = vec.end(); i != e; ++i) do_something( *i ); For_each: std::for_each( vec.begin(), vec.end(), do_something ); -- 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 Dave Harris Guest Posted: Sun Jul 31, 2005 4:49 pm    Post subject: Re: vector::size() - To cache or not to cache? [email]cxl (AT) volny (DOT) cz[/email] (Mirek Fidler) wrote (abridged): Quote: vector usually stores begin - end pair. The real calculation is (end - begin) / sizeof(T), which can be pretty bad if division cannot be performed by shift (AFAIK integer division is still quite expensive even on modern CPU). True, but that's something I was hoping the compiler would optimise away. If we end up with: for (size_t i = 0; i < (v->end_ - v->begin_) / sizeof(T); ++i) do_something( v->begin_ + i * sizeof(T) ); then the compiler can eliminate a multiply and a divide by scaling the index: for (size_t i = 0; i < v->end_ - v->begin_; i += sizeof(T)) do_something( v->begin_ + i ); And I thought some real compilers did this. You do need to check, though. Alas, the only compiler I have to hand is an old MS VC++6, and it seems to produce very poor code. Vector::size() is defined like: return (begin_ == 0 ? 0 : _end - _begin); and the test against zero remains in the inner loop, even at full optimisation. And the division is there too. I hope Microsoft's current compiler and library does better. -- 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 Bo Persson Guest Posted: Sun Jul 31, 2005 6:25 pm    Post subject: Re: vector::size() - To cache or not to cache? "Dave Harris" <brangdon (AT) cix (DOT) co.uk> skrev i meddelandet news:memo.20050731172855.1208B (AT) brangdon (DOT) m... Quote: bop (AT) gmb (DOT) dk (Bo Persson) wrote (abridged): Also, how do you know that the vector::size() is not defined as size_type size() const { return m_size; } Did you miss the bit where I said you should check your local implementation? Incidently, do you know of an implementation that actually has std::vector::size() defined like that? My implementation is indeed *local*, and does exactly as I quoted above. The point was that the attempts to optimize low level operations are limited to the specific implementations you have checked. It is not a good idea everywhere - it might even make the code run slower on another implementation. Thus not a good recommendation for general use. Quote: How do you improve on that? By making a copy s on the stack? Indeed. The compiler knows that a copy on the stack cannot be changed by do_something(), so it becomes a loop invariant and can be held in a register. If the vector is passed by reference or is an instance variable, and do_something() is not inlined, the compiler will probably assume that m_size can change in the loop so it must keep loading it from memory. And then it must repeat any calculations that depend on that value. But, if do_something() does anything non-trivial it is not that likely that the register will be available to the top level loop. If do_soemthing() really performs some non-trivial operations, what are the odds that recomputing the vector size would really show up in the timing? If do_something() doesn't take any significant amount of time, the odds are high that the compiler will notice that it doesn't call any non-const vector members. Then the size will not change. Quote: By the same token, it can be faster to cache v.begin(). Come on! :-) Quote: I tried various loops with this compiler. Here are the results: Version Assembler instructions Array-naive: 20 Array-size: 9 Array-best: 6 Iterator-naive: 7 Iterator-best: 6 For_each: 6 Is this an argument for or against using iterators, or what? Using for_each seems to be a good choice. Quote: Bo Persson [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top deb@pixar.com Guest Posted: Sun Jul 31, 2005 6:26 pm    Post subject: Re: vector::size() - To cache or not to cache? Dave Harris wrote: Quote: kelly_g_walker (AT) earthlink (DOT) net (Kelly Walker) wrote (abridged): Fastest is probably to count backwards: for (int i = v.size()-1; i >= 0; --i) because it is comparing against constant 0 instead of a variable s or expression v.size(). It's too error-prone for casual use, though. Personally, I prefer for (size_t i = v.size(); i--; ) { // access v[i] } Note that when i is zero, then i-- as an expression yields 0; the fact that what i is after this is badly defined (since i is a size_t) is not of consequence, since we leave the loop. The value of this idiom is that you keep i as a size_t, and it's really short to write. [ 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.