1

If i have a myVector which is a STL vector and execute a loop like this:

for(int i=0;i<myVector.size();++i) { ... }

Does the C++ compiler play some trick to call size() only once, or it will be called size()+1 times?

I am little confused, can anyone help?

Martin York
  • 257,169
  • 86
  • 333
  • 562
James Bond
  • 7,533
  • 19
  • 50
  • 64
  • I am not sure, but I think that it will be called size() + 1 times. – vietean Sep 07 '11 at 17:01
  • I once [ran some tests](http://stackoverflow.com/questions/6926930/it-or-it-when-iterating-over-a-map/6927125#6927125) on a `map` which suggested that the compiler can figure out when to hoist the end out of the loop. – Kerrek SB Sep 07 '11 at 17:06
  • @Kerrek SB: Those are simple tests and not representative of real code. If anywhere in the loop you call out to another non-inlined function, the compiler will almost always have to assume that somewhere else could alias the size, and will reload it on each iteration. It will only be hoisted in very, very simple situations (like your tests). – Peter Alexander Sep 07 '11 at 17:19
  • @Peter: Yeah, that's true... one more reason to hoist manually for non-modifying loops! – Kerrek SB Sep 07 '11 at 17:22
  • The only way to know for sure is to get your assembly and dig through it (not fun, but conclusive). `g++ -Owhatever -S file.cpp` will do it on Linux (look for `file.s` afterwards) - just keep in mind that the assembly can differ drastically depending on the optimization level. Though, personally, I just try to dodge this entirely by starting loops at `size - 1` and going down to zero... Cheers! – Xavier Holt Sep 07 '11 at 17:55

8 Answers8

5

Logically, myVector.size() will be called each time the loop is iterated - or at least the compiler must produce code as if it's called each time.

If the optimizer can determine that the size of the vector will not change in the body of the loop, it could hoist the call to size() outside the loop. Note that usually, vector::size() is an inline that's just a simple difference between pointers to the end and beginning of the vector (or something similar - maybe a simple load of a member that keeps track of the number of elements).

So there's actually probably little reason for concern about what happens for vector::size().

Note that list::size() could be a different story - the C++03 standard permits it to be linear complexity (though I think this is rare, and the C++0x standard changes list::size() requirements to be constant complexity).

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
  • I'd say if compiler can determine that calling `size ()` has no side effects, not only if method doesn't change the body of the loop, or vector. Simply, it will be called N+1 times even if you insert `printf` there. –  Sep 07 '11 at 17:17
  • I remember having had a horrible experience with list::size()'s linear complexity (Visual Studio 7.1, i think). The for statement becomes of N² complexity and out went my performance ! – Benoît Sep 07 '11 at 19:24
  • Your compiler must also assume that no other thread is changing your vector. If the vector has changed from another thread, the compiler would need to call `size()` again. – Robert Martin Mar 11 '12 at 08:11
3

I'm assuming that the vector doesn't change size in the loop. If it does change size, it's impossible to tell without knowing how it changes size.

On the C++ abstract machine it will be called exactly size()+1 times. And on a concrete implementation it will have an observable behaviour equivalent to it having been called size()+1 times (this is called the as if rule).

This means that the compiler can choose to call it just once, because the observable behaviour is the same. In fact, by following the as if rule, if the body of the loop is empty, the compiler can even choose to not call it at all and just skip the whole thing altogether. The observable behaviour is the same, because making your code run faster is not considered different observable behaviour.

R. Martinho Fernandes
  • 228,013
  • 71
  • 433
  • 510
2

It will be called size + 1 times. Changing the size of the vector will affect the number of iterations.

Ernest Friedman-Hill
  • 80,601
  • 10
  • 150
  • 186
  • 1
    No, it will behave *as if* it were called `size+1` times, which is not the same as actually being called `size+1` times. (assuming the loop doesn't change the size of the vector.) – Robᵩ Sep 07 '11 at 17:17
  • @Rob: If it behaves as if it's called `size+1` times what's the point in making the distinction? If the compiler can make the last `size()` calls have zero cost by not actually doing anything then that's great but it can only do that where calling the function has the same behaviour as not calling the function. In this case you may as well consider the function has been "called" because the language requires it to be called and there can be no observable evidence that it hasn't been called. – CB Bailey Sep 07 '11 at 17:28
  • I make the distinction because the question makes the distinction. He is trying to understand the difference between `size()` being *actually* called and "some trick" which allows it to not be called. I take "some trick" to mean optimizations allowed by the language. – Robᵩ Sep 07 '11 at 17:38
  • @Rob: For the sake of example, how would you tell if a function defined `inline void fn() {}` is called when a statement `fn();` is executed? It *must* be called but you're unlikely to find any difference between object code generate from similar source code with the statement missing. Every time the compiler translates source code to object code it is performing all sorts of tricks every time; the mapping from a high level language such as C++ to what a CPU actually executes should not be expected to be a simple one-to-one mapping. – CB Bailey Sep 09 '11 at 07:28
2

It may be called once, may be called size+1 times, or it may never be called at all. Assuming that the vector size doesn't change, your program will behave as if it had been called size+1 times.

There are two optimizations at play here: first, std::vector::size() is probably inlined, so it may never be "called" at all in the traditional sense. Second, the compiler may determine that it evaluate size() only once, or perhaps never:

For example, this code might never evaluate std::vector::size():

for(int i = 0; i < myVector.size(); ++i) { ; }

Either of these loops might evaluate std::vector::size() only once:

for(int i = 0; i < myVector.size(); ++i) { std::cout << "Hello, world.\n"; }
for(int i = 0; i < myVector.size(); ++i) { sum += myVector[i]; }

While this loop might evaluate std::vector::size() many times:

for(int i = 0; i < myVector.size(); ++i) { ExternalFunction(&myVector); }

In the final analysis, the key questions are:

  • Why do you care?, and
  • How would you know?

Why do you care how many times size() is invoked? Are you trying to make your program go faster?

How would you even know? Since size() has no visible side-effects, how would you even know who many times it was called (or otherwise evaluated)?

Robᵩ
  • 163,533
  • 20
  • 239
  • 308
1

It will be called size() + 1 times (it may be that the compiler can recognize it as invariant in the loop, but you shouldn't count on it)

antlersoft
  • 14,636
  • 4
  • 35
  • 55
  • The compiler would also need to be able to recognize that `std::vector<>::size()` has no side effects, a situation which is more likely if the method is inline-able. – dmckee --- ex-moderator kitten Sep 07 '11 at 17:05
  • @dmckee: Don't we have `const` for that? –  Sep 07 '11 at 17:14
  • @delnan `const` insures that the method does not change the state of the object, but does not insure that it does not print, write to disk, send to the network, etc. Or am I bonkers? – dmckee --- ex-moderator kitten Sep 07 '11 at 17:17
  • @dmckee: No, you're right. I guess the compilers that do this optimization either really inline it (easy, since the definition for templated code is available anyway) or have a special annotation for "pure" code (GCC has one) and re-use that (doesn't rely on inlining, which isn't always desired). –  Sep 07 '11 at 17:20
1

It will be called until the condition is not falsified (size() could change each time for example). If size() remains constant, it's size() + 1 times.

From the MSDN page about for:

for ( init-expression ; cond-expression ; loop-expression )
statement

cond-expression

Before execution of each iteration of statement, including the first iteration. statement is executed only if cond-expression evaluates to true (nonzero). An expression that evaluates to an integral type or a class type that has an unambiguous conversion to an integral type. Normally used to test for loop-termination criteria.

Community
  • 1
  • 1
xanatos
  • 109,618
  • 12
  • 197
  • 280
  • 1
    Not necessarily, just like `a = 0` won't necessarily assign `a`. In both cases, the program will behave *as if* it did, but if the compiler can prove that another operation (which is probably considers more "better" in some regard) and doesn't affect the program's behavior (save undefined behavior etc.), it's free to replace it with that operation. That's an important difference. –  Sep 07 '11 at 17:13
  • 1
    @delnan We are speaking of the sex of angels. The compiler is free to omit 100% of your program if he can see that it wouldn't change its behaviour. If this is so, is it truly important to repeat that every single instruction could be "ignored"? – xanatos Sep 07 '11 at 20:32
0

It will be called size + 1 times, as Ernest have mentioned. However, if you are sure that size is not changing, you can apply an optimisation and make your code look like this:

for (unsigned int i = 0, e = myVector.size (); i < e; ++i)

... in which case size () will be called only once.

  • There are those who would argue that it is wiser to leave this optimization to the compiler, at least until you *know* that it isn't doing a good enough job. – dmckee --- ex-moderator kitten Sep 07 '11 at 17:20
  • @dmckee: in case of `std::vector` it doesn't matter. In case of more complex things, I think it is easier to just write it this way rather than going and checking if every compiler and every new version of used compiler generates the code you expect, if you really rely on it to be called once. –  Sep 07 '11 at 17:25
0

Actually myVector.size() will be inlined, so there will be no call at all. Just comparing register value with memory location. Of course I am talking about release build.

In debug build it will be called size()+1 times.

EDIT: No doubt that there exists such compiler or STL implementation which cannot optimize myVector.size(). But the chances to face them are very low.

Sergey Podobry
  • 7,101
  • 1
  • 41
  • 51