c++ performance issue beginner (size function in for loop)

Question

hi when having a vector<int> var; for(int i=0; i< var.size();i++) , is the size() function called each time or only once ?

---

from the answers I guess I better use iterators , or just have variable before the loop

Answer 1

It's 'called' each time, but I put called into quotes because it really probably is just an inline method call, so you don't have to worry about its performance.

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

Answer 2

The size() member function is called each time, but it would be a really bad implementation that wouldn't inline it, and a strange one where it wouldn't be a simple access of a fixed datum or a subtraction of two pointers.
Anyway, you shouldn't worry yourself with such trivialities until you have profiled your application and found out that this is a bottleneck.

However, what you should pay attention to is:

1. The correct type for a vector's index is std::vector<T>::size_type.
2. There are types (some iterators, for example) where i++ might be slower than ++i.

Therefore, the loop should be:

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

Answer 3

It must be called everytime because size() might return a different value everytime.

Therefore there's no big choice it simply must be.

Answer 4

In theory, it is called each time, since a for loop:

for(initialization; condition; increment)
    body;

is expanded to something like

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

(notice the curly braces, because initialization is already in an inner scope)

In practice, if the compiler understands that a piece of your condition is invariant through all the duration of the loop and it does not have side-effects, it can be smart enough to move it out. This is routinely done with strlen and things like that (that the compiler knows well) in loops where its argument isn't written.

The compiler may be helped in this optimization also by the various const modifiers that may be present: for example, if you're manipulating a vector via a const reference, the compiler can exploit this information to be sure that its fields will never change.

Doing that optimization by hand is worthy if you know that a part of your condition is "expensive" to evaluate (and such condition isn't, since it usually boils down to a pointer subtraction, which is almost surely inlined).

---

Edit: as others said, in general with containers it's better to use iterators, but for vectors it's not so important, because random access to elements via operator[] is guaranteed to be O(1); actually with vectors it usually is a pointer sum (vector base+index) and dereference vs the pointer increment (preceding element+1) and dereference of iterators. Since the target address is still the same, I don't think that you can gain something from iterators in terms of cache locality (and even if so, if you're not walking big arrays in tight loops you shouldn't even notice such kind of improvements).

For lists and other containers, instead, using iterators instead of random access can be really important, since using random access may mean walk every time the list, while incrementing an iterator is just a pointer dereference.

The use of vector<int>::size_type instead of just int is important too, because you gain that your code can actually walk all the elements the vector can contain and avoid warnings (and potential logic errors at runtime) about signed/unsigned comparisons.

Answer 5

As other have said

• the semantics must be as if it were called each time
• it is probably inlined, and is probably a simple function

on top of which

• a smart enough optimizer may be able to deduce that it is a loop invariant with no side effects and elide it entirely (this is easier if the code is inlined, but may be possible even if it is not if the compiler does global optimization)

Answer 6

But it could be done in this way (providing that this loop intends to only read/write without actually changing the size of a vector):

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

In the loop above you have just one call to size independently from size being inlined or not.

Answer 7

I think that if the compiler can conclusively deduce that the variable var is not modified inside the "loop body"

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

then the above may be transposed to something equivalent of

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

However, I am not absolutely sure, so comments are welcome :)

Also,

• In most situations, the size() member function is inlined, so the issue does not warrant worrying

• The concern is perhaps equally applicable to the end() which is always used for iterator based looping, i.e. it != container.end()

• Please consider using size_t or vector<int>::size_type for the type of i [See Steve Jessop's comment below.]

Answer 8

Hi, as others said, The compiler shall decide what to do with the actual code written. The key figure is that it is called each time. But if you want to get a performance boost, it is best to write your code with some considerations. Your case is one of them, there are others as well, 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 one will not change the ram page too much per references, but the other will exhaust your cache and TLB and other stuff.

Also inline won't help that much! because the order of the calling function will remain as n(size of the vector) times. It helps in some places though, but the best thing is to rewrite your code.

But! if you want to let a compiler do it's optimizations over your code NEVER put volatile, like so:

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

It prevents the compiler from optimizing. If you need another hint for performance use register 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. It is not ensured that it can do it, but it will do it's best ;)