Optimize "for" loop

Question

std::vector<int> someVector;    
for (unsigned int i = 0; i < someVector.size(); i++)
{
   // do something
}

Does the value of someVector.size() get calculated every time?

Why don't you generate the assembly code and check yourself? — Alok Save, May 25 '13 at 06:26
Depends heavily on your compiler _and_ your optimization flags. You may also have a look at http://herbsutter.com/2013/05/13/gotw-2-solution-temporary-objects/ (doesn't really answer your question, but gives you some hints). — Zeta, May 25 '13 at 06:28
Don't listen to Alok, that's a terrible suggestion. Looking at the code will only tell you what your compiler actually does, and you're probably more interested in what the standard specifies. The termination condition of a loop *is* evaluated on each iteration, so that if it has side effects, they will occur. *If* you call a function that happens to not have side effects, and you don't do anything inside the loop that does, and if the compiler is smart enough to figure all that out, it *might* optimize away the call, but that's a big if. Probably better to do it yourself. — Lee Daniel Crocker, May 25 '13 at 06:37
size() should be called every time because someVector could be modified from another thread while the loop is being executed. — Jari Karppanen, May 25 '13 at 07:21
@LeeDanielCrocker I'd say that 1. `vector::size` is `const`, so that may very well be a hint to the compiler to call it only once if the aforementioned conditions are met; 2. I can't imagine a situation when you loop through the vector and you modify its size. I mean, there **is** `for (i = 0; i < 10; i++) v.push_back(i);`, but that doesn't depend on the size of the vector, and modifying it *while* enumerating is really a bad idea (to draw perhaps not so good parallels, in Objective-C, `NSMutableArray` explicitly prohibits this and throws an exception - because it really is nonsense). — , May 25 '13 at 07:35
@H2CO3 still, you *can* modify the vector in the loop, and the compiler needs to be clever enough to detect that you don't do this. — juanchopanza, May 25 '13 at 11:45

Stefan Haustein · Answer 1 · 2013-05-25T07:26:13.350

I have checked with GCC explorer:

Code entered:

#include<vector>

int sum(const std::vector<int> & someVector) {
  int s = 0;
  for (int i = 0; i < someVector.size(); i++) {
    s += someVector[i];
  }
  return s;
}

int main() {
  std::vector<int> someVector;
  return sum(someVector);
};

Assembly generated for sum():

  movq  (%rdi), %rcx
  movq  8(%rdi), %rdx
  xorl  %eax, %eax
  cmpq  %rcx, %rdx
  je    .LBB0_3
  subq  %rcx, %rdx
  sarq  $2, %rdx
  xorl  %eax, %eax
  xorl  %esi, %esi
.LBB0_2:                                # =>This Inner Loop Header: Depth=1
  addl  (%rcx,%rsi,4), %eax
  incq  %rsi
  cmpq  %rdx, %rsi
  jb    .LBB0_2
.LBB0_3:                                # %._crit_edge
  ret

i.e. the size is kept in %rdx -- there is no call to size() each time.

As others have pointed out already, results may depend on

your compiler,
optimization settings and
what you actually do in the loop (click the gcc explorer link above to try yourself).

Without calculating anything, the whole loop gets optimized away.

The code is also quite different to OP's, and a case where it is safe to assume the optimization will happen: You have `const` reference to a vector. It would be interesting to see the assembly for OP's example, without the additional `sum` function. — juanchopanza, May 25 '13 at 07:14
Without doing anything in the loop, the whole loop is eliminated. The relevant part of the code stays the same if I drop const &. I guess the compiler figures out that it can be a const reference anyway. — Stefan Haustein, May 25 '13 at 07:23

juanchopanza · Accepted Answer · 2013-05-25T07:07:19.977

4

Does the value of someVector.length() get calculated every time?

Possibly, depending on the contents of the loop and many other things. For instance, the size of the vector could be modified inside the loop. Then your compiler has to be able to spot if this is not the case. So a few conditions have to be met for this to be optimized out.

If you require that std::vector::size() is only called once in the loop, then the best (and only) strategy is to sidestep the question entirely through a trivial modification to the code:

std::vector<int> someVector;    
for (unsigned int i = 0, length = someVector.size(); i < length; ++i)
{
   // do something
}

edited May 25 '13 at 07:07

answered May 25 '13 at 06:27

juanchopanza

223,364
34
402
480

I know I can do that, but I was wondering if that's really necessary. – Maria Ines Parnisari May 25 '13 at 06:28
1

@l19 well, you cannot be completely sure it will be optimized out. It can be, but it doesn't have to be (the vector's size can change inside the loop, for example). – juanchopanza May 25 '13 at 06:30
You should probably add your above comment as part of your answer. – srikanta May 25 '13 at 07:02
@srikanta Good point, thanks. I expanded the answer a little bit. – juanchopanza May 25 '13 at 07:08
"*the best (and only) strategy*" - not quite. If there is no requirement to iterate from the beginning to the end (and in most cases it doesn't matter), the cleaner way would be to start from last element and iterate with i--. – SomeWittyUsername May 25 '13 at 09:44

score 0 · Answer 3 · answered May 25 '13 at 06:29

It depends on the compiler optimization.

it might Loop optimization,(if possible not mentioned something like volatile)

the compiler will put datas (irrelevant) not dependent on loop outside.

so it may generate something like

int length = someVector.length();
for (unsigned int i = 0; i < length; i++)
{
    // do something
}

There are many compiler optimization techniques that it 'll do.

By default in c++ there are some "pure functions" string.length() which is always optimized. i'm not sure whether vector.size belong to that.

Optimize "for" loop

3 Answers3

Linked