Performance issue for vector :: size () in a loop in C ++

Question

In the following code:

std::vector<int> var; for (int i = 0; i < var.size(); i++); 

Is the size() member function called for each iteration of the loop, or only once?

Answer 1

In theory, this is called every time because the for loop:

 for(initialization; condition; increment) body; 

expands to a value

 { initialization; while(condition) { body; increment; } } 

(pay attention to curly braces, since initialization is already in the inner area)

In practice, if the compiler understands that part of your condition is invariant over the entire duration of the cycle, and it has no side effects, it may be smart enough to move it. This is usually done with strlen and such things (that the compiler knows well) in loops where its argument is not written.

However, it should be noted that this last condition is not always trivial to prove; in general, it is easy if the container is local to the function and is never passed to external functions; if the container is not local (for example, it is passed by reference, even if it is const ), and the body of the loop contains calls for other functions, the compiler often must assume that such functions can change it, thereby blocking the rise in length of the calculation.

Performing this optimization manually is worth the effort if you know that part of your condition is priced “expensive” (and this condition is usually not, since it usually comes down to subtracting the pointer, which is almost certainly embedded).

---

Edit: as others have said, in general it is better to use iterators with containers, but for vector this is not so important, because random access to elements through operator[] guaranteed to be O (1); in fact, with vectors it is usually the sum of the pointer (vector base + index) and dereferencing with increasing pointer (previous element + 1) and dereferencing iterators. Since the destination address is the same, I don’t think that you can get something from iterators in terms of cache locality (and even if it is, if you do not go through arrays in complex loops, you should not even notice such kind of improvements )

Instead of lists and other containers, using iterators instead of random access can be very important, because using random access can mean a walk every time the list is used, and incrementing the iterator is just dereferencing the pointer.

Answer 2

It is called "every time", but I put the call in quotation marks because it is probably just a built-in method call, so you don’t have to worry about its performance.

Why not use vector<int>::iterator instead?

Answer 3

The member function size() is called every time, but it would be a very poor implementation that would not be built into it, and strange where it would not be easy access to a fixed date or subtract two pointers.
In any case, you should not worry about such trifles until you profile your application and find out that this is a bottleneck.

However, you should pay attention to the following:

• The correct type for the vector index is std::vector<T>::size_type .
• There are types (e.g. some iterators) where i++ can be slower than ++i .

Therefore, the cycle should be:

 for(vector<int>::size_type i=0; i<var.size(); ++i) ... 

Answer 4

It should be called every time, because size () may return a different value each time.

Therefore, there is not much choice that it simply should be.

Answer 5

As others said

• semantics should be as if they were called every time
• it is probably inline and probably is a simple function

over which

• a reasonable optimizer can deduce that it is an invariant of the cycle without side effects and completely eliminates it (this is easier if the code is embedded, but it can be possible even if it is not, if the compiler does global optimization)

Answer 6

I think that if the compiler can finally infer that the var variable does not change inside the "loop body"

 for(int i=0; i< var.size();i++) { // loop body } 

then the above can be carried over to something equivalent

 const size_t var_size = var.size(); for( int i = 0; i < var_size; i++ ) { // loop body } 

However, I'm not quite sure, so comments are welcome :)

Besides,

• In most situations, the size() member function is built in, so the problem is not a concern

• Perhaps the problem is with end() , which is always used for iterator-based cyclization, i.e. it != container.end()

• Please use size_t or vector<int>::size_type for type i [See commentary on Steve Jessop below.]

Answer 7

But this can be done in this way (provided that this cycle intends to read or write only without changing the size of the vector):

 for(vector<int>::size_type i=0, size = var.size(); i < size; ++i) { //do something } 

In the above loop, you only have one size call, no matter what size was built in or not.

Answer 8

as others have said, the compiler must decide what to do with the written code. The key is that it is called every time. But if you want to improve performance, it is better to write code with some considerations. Your case is one of them, there are others, like the difference between these two pieces of code:

 for (int i = 0 ; i < n ; ++i) { for ( int j = 0 ; j < n ; ++j) printf("%d ", arr[i][j]); printf("\n"); } for (int j = 0 ; j < n ; ++j) { for ( int i = 0 ; i < n ; ++i) printf("%d ", arr[i][j]); printf("\n"); } 

The difference is that the first will not change the markup page for links too much, but the other will exhaust your cache and TLB and other things.

Also the built in will not help! because the order of the calling function will remain equal to n (vector size) times. However, this helps in some places, but it is best to rewrite your code.

But! if you want the compiler to do this with optimization according to your code, NEVER put volatile, for example:

 for(volatile int i = 0 ; i < 100; ++i) 

This prevents compiler optimization. If you need other advice to use, use case instead of volatile.

 for(register int i = 0 ; i < 100; ++i) 

The compiler will try not to move I from the CPU registers to RAM. This does not guarantee that he can do it, but he will do it best;)

Answer 9

Tested it on 900,000 iterations. Its time is 43 seconds for a pre-calculated size and 42 seconds for using the size () call.

If you are guaranteed not to change the size of the vector in the loop, it is better to use a pre-calculated size, otherwise there is no choice and you must use size ().

 #include <iostream> #include <vector> using namespace std; int main() { vector<int> v; for (int i = 0; i < 30000; i++) v.push_back(i); const size_t v_size = v.size(); for(int i = 0; i < v_size; i++) for(int j = 0; j < v_size; j++) cout << ""; //for(int i = 0; i < v.size(); i++) // for(int j = 0; j < v.size(); j++) // cout << ""; }