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

by

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.

However it must be noted that this last condition isn’t always trivial to prove; in general, it’s easy if the container is local to the function and is never passed to external functions; if the container is not local (e.g. it’s passed by reference – even if it’s const) and the loop body contains calls to other functions, the compiler often has to assume that such functions may alter it, thus blocking the hoisting of the length calculation.

Doing that optimization by hand is worthy if you know that a part of your condition is “expensive” to evaluate (and such condition usually 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.

More Related Contents:

  1. How do I print out the contents of a vector?
  2. How do I print out the contents of a vector?
  3. Concatenating two std::vectors
  4. Is std::vector so much slower than plain arrays?
  5. What is the advantage of using forwarding references in range-based for loops?
  6. Correct way to work with vector of arrays
  7. Removing item from vector, while in C++11 range ‘for’ loop?
  8. What’s faster, iterating an STL vector with vector::iterator or with at()?
  9. C++ for-loop – size_type vs. size_t
  10. Does a C++11 range-based for loop condition get evaluated every cycle?
  11. Is the ranged based for loop beneficial to performance?
  12. std::vector resize downward
  13. Why is std::vector::operator[] 5 to 10 times faster than std::vector::at()?
  14. Benefits of using reserve() in a vector – C++
  15. How to cheaply assign C-style array to std::vector?
  16. Erasing elements from a vector
  17. Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly?
  18. Why can’t I make a vector of references?
  19. Does C++11 allow vector?
  20. Static linking vs dynamic linking
  21. vector size – 1 when size is 0 in C++
  22. How to use std::sort with a vector of structures and compare function?
  23. How to implement 2D vector array?
  24. How to make elements of vector unique? (remove non adjacent duplicates)
  25. What is the performance cost of having a virtual method in a C++ class?
  26. Why is iterating though `std::vector` faster than iterating though `std::array`?
  27. Difference between rdtscp, rdtsc : memory and cpuid / rdtsc?
  28. c++11 regex slower than python
  29. C++ Serialization Performance
  30. Why is pow(int, int) so slow?

Leave a Comment