Is using size() for the 2nd expression in a for construct always bad?

Question

In the following example should I expect that values.size() will be called every time around the loop? In which case it might make sense to introduce a temporary vectorSize variable. Or should a modern compiler be able to optimize the calls away by recognising that the vector size cannot change.

double sumVector(const std::vector<double>& values) {
    double sum = 0.0;
    for (size_t ii = 0; ii < values.size(); ++ii) {
        sum += values.at(ii);
    }
}

Note that I don't care if there are more efficient methods to sum the contents of a vector, this question is just about the use of size() in a for construct.

Answer 1

Here's one way to do it that makes it explicit - size() is called only once.

for (size_t ii = 0, count = values.size();  ii < count;  ++ii)

Edit: I've been asked to actually answer the question, so here's my best shot.

A compiler generally won't optimize a function call, because it doesn't know if it will get a different return value from one call to the next. It also won't optimize if there are operations inside the loop that it can't predict the side effects of. Inline functions might make a difference, but nothing is guaranteed. Local variables are easier for the compiler to optimize.

Some will call this premature optimization, and I agree that there are few cases where you will ever notice a speed difference. But if it doesn't make the code any harder to understand, why not just consider it a best practice and go with it? It certainly can't hurt.

P.S. I wrote this before I read Benoit's answer carefully, I believe we're in complete agreement.

Answer 2

It all depends on what the vector's size implementation is, how aggressive the compiler is and if it listen/uses to inline directives.

I would be more defensive and introduce the temporary as you don't have any guarantees about how efficient your compiler will be.

Of course, if this routine is called once or twice and the vector is small, it really doesn't matter.

If it will be called thousands of times, then I would use the temporary.

Some might call this premature optimization, but I would tend to disagree with that assessment.
While you are trying to optimize the code, you are not investing time or obfuscating the code in the name of performance.

I have a hard time considering what is a refactoring to be an optimization. But in the end, this is along the lines of "you say tomato, I say tomato"...

Answer 3

Start with size() in the 'for' construct until you need to optimize for speed.

If it is too slow, look for ways to make it faster, such as using a temporary variable to hold the result of size.

Answer 4

No matter the optimisation settings, putting the .size() call in the second expression will be at most as performant as outlining the .size() call before the for-loop. That is:

size_t size = values.size();
for (size_t ii = 0; ii < size; ++ii) {
    sum += values.at(ii)
}

will always perform at least as well as, if not better than:

for (size_t ii = 0; ii < values.size(); ++ii) {
    sum += values.at(ii);
}

In practice, it probably wont matter, since outlining the .size() call is a common compiler optimisation. However, I do find the second version easier to read.

I find this even easier, though:

double sum = std::accumulate(values.begin(), values.end(), 0);

Answer 5

Worth noting that even if you are dealing with millions of items the overhead is going to be negligible.

In any case this should really be written using iterator - as there may be more overhead accessing a specific example.

There is really no way that the compiler can assume that size() won't change - because it could do..

If the order of iteration isn't important then you could always write it as which is slightly more efficient.

for (int i=v.size()-1; i>=0 ;i--)
{
   ...
}

Answer 6

This isn't part of the question but why are you using at in your code in place of the subscript operator []?

The sense in at is to ensure that no operation on an invalid index occurs. However, this will never be the case in your loop since you know from your code what the indices are going to be (always assuming single-threadedness).

Even if your code contained a logical error, causing you to access an invalid element, at in this place would be useless because you don't expect the resulting exception and hence you don't treat it (or do you enclose all of your loops by try blocks?).

The use of at here is misleading because it tells the reader that you (as a programmer) don't know what values the index will have – which is obviously wrong.

I agree with Curro, this is a typical case for the use of iterators. Although this is more verbose (at least if you don't use constructs like Boost.Foreach), it is also much more expressive and safer.

Boost.Foreach would allow you to write the code as follows:

double sum = 0.0;
foreach (double d, values)
    sum += d;

This operation is safe, efficient, short and readable.

Answer 7

It doesn't matter at all. The performance overhead of .at() is so large (it contains a conditional throw statement) that a non-optimized version will spend most of its time there. An optimizing compiler smart enough to eliminiate the conditional throw will necessarily spot that size() does not change.

Answer 8

I agree with Benoit. The introduction of a new variable, especially an int or even a short will have a bigger benefit that calling it each time.

It's one less thing to worry about if the loop ever gets large enough that it may impact performance.

Answer 9

The size method from std::vector should be inlined by the compiler, meaning that every call to size() is replaced by its actual body (see the question Why should I ever use inline code for more information about inlining). Since in most implementations size() basically computes the difference between end() and begin() (which should be inlined too), you don't have to worry too much about loss of performance.

Moreover, if I remember correctly, some compilers are "smart" enough to detect the constness of an expression in the second part of the for construct, and generate code that evaluates the expression only once.

Answer 10

If you hold the size of the vector in a temporary variable, you will be independent of the compiler.

My guess is, that most compilers will optimize the code in a way, that size() will be called only once. But using a temporary variable will give you a guarantee, size() will only be called once!

Answer 11

The compiler will not know if the value of .size() changes between calls, so it won't do any optimizations. I know you just asked about the use of .size(), but you should be using iterators anyway.

std::vector<double>::const_iterator iter = values.begin();
for(; iter != values.end(); ++iter)
{
    // use the iterator here to access the value.
}

In this case, the call to .end() is similar to the problem you expose with .size(). If you know the loop does not perform any operation in the vector that invalidates the iterators, you can initialize an iterator to the .end() position prior to enter the loop and use that as your boundary.

Answer 12

In such cases using iterators is cleaner - in some it's even faster. There's only one call to the container - getting the iterator holding a pointer to the vector member if there are any left, or null otherwise.

Then of course for can become a while and there are no temporary variables needed at all - you can even pass an iterator to the sumVector function instead of a const reference/value.

Answer 13

Always write code the first time exactly as you mean it. If you are iterating over the vector from zero to size(), write it like that. Do not optimise the call to size() into a temporary variable unless you have profiled the call to be a bottleneck in your program that needs optimising.

In all likelihood, a good compiler will be able to optimise away the call to size(), particularly given that the vector is declared as const.

Answer 14

If you were using a container where size() was O(n) (like std::list) and not O(1) (like std::vector), you would not be iterating through that container using indices. You would be using iterators instead.

Anyway, if the body of the loop is so trivial that recalculating std::vector::size() matters, then there is probably a more efficient (but possibly platform-specific) way to do the calculation, regardless of what it is. If the body of the loop is non-trivial, recalculating std::vector::size() each time is unlikely to matter.

Answer 15

• If you are modifying the vector (adding or removing elements) in the for loop then you should not use a temporary variable since this could lead to bugs.
• If you are not modifying the vector size in the for loop then I would all the time use a temporary variable to store the size (this would make your code independant on the implementation details of vector::size.

Answer 16

Most, maybe even all, standard implementations of size() will be inlined by the compiler to what would be the equivalent of a temporary or at most a pointer dereference.

However, you can never be sure. Inlining is about as hidden as these things get, and 3rd party containers may have virtual function tables - which means you may not get inlined.

However, seriously, using a temporary reduces readability slightly for almost certainly no gain. Only optimise to a temporary if profiling says it is fruitful. If you make these micro optimisations everywhere, your code could become unreadable, perhaps even for yourself.

As a slight aside, no compiler would optimise size() to one of call assigning to a temporary. There is almost no guarantee of const in C++. The compiler cannot risk assuming size() will return the same value for the whole loop. For example. Another thread could change the vector in between loop iterations.