Performance of vector::size() : is it as fast as reading a variable?

Question

I have do an extensive calculation on a big vector of integers. The vector size is not changed during the calculation. The size of the vector is frequently accessed by the code. What is faster in general: using the vector::size() function or using helper constant vectorSize storing the size of the vector? I know that compilers usually able to inline the size() function when setting the proper compiler flags, however, making a function inline is something that a compiler may do but can not be forced.

Answer 1

As I understand the 1998 C++ specification, vector<T>::size() takes constant time, not linear time. So, this question likely boils down to whether it's faster to read a local variable than calling a function that does very little work.

I'd therefore claim that storing your vector's size() in a local variable will speed up your program by a small amount, since you'll only call that function (and therefore the small constant amount of time it takes to execute) once instead of many times.

Answer 2

In every implementation I've, seen vector::size() performs a subtraction of end() and begin(), ie its not as fast as reading a variable.

When implementing a vector, the implementer has to make a choice between which shall be fastest, end() or size(), ie storing the number of initialized elements or the pointer/iterator to the element after the last initialized element. In other words; iterate by using iterators.

If you are worried of the size() performance, write your index based for loop like this;

for (size_t i = 0, i_end = container.size(); i < i_end; ++i){
// do something performance critical
}

Answer 3

You could write yourself a functor for your loop body and call it via std::for_each. It does the iteration for you, and then your question becomes moot. However, you're introducing a function call (that may or may not get inlined) for every loop iteration, so you'd best profile it if you're not getting the performance you expect.

Answer 4

Performance of vector::size() : is it as fast as reading a variable?

Probably not.

Does it matter

Probably not.

Unless the work you're doing per iteration is tiny (like one or two integer operations) the overhead will be insignificant.

Answer 5

Always get a profile of your application before looking at this sort of micro optimization. Remember that even if it performs a subtraction, the compiler could still easily optimize it in many ways that would negate any performance loss.

Answer 6

Funny question.

So, what's going to happened ? Well if you debug with gdb you'll see something like 3 member variables (names are not accurate):

• _M_begin: pointer to the first element of the dynamic array
• _M_end: pointer one past the last element of the dynamic array
• _M_capacity: pointer one past the last element that could be stored in the dynamic array

The implementation of vector<T,Alloc>::size() is thus usually reduced to:

return _M_end - _M_begin;  // Note: _Mylast - _Myfirst in VC 2008

Now, there are 2 things to consider when regarding the actual optimizations possible:

• will this function be inlined ? Probably: I am no compiler writer, but it's a good bet since the overhead of a function call would dwarf the actual time here and since it's templated we have all the code available in the translation unit
• will the result be cached (ie sort of having an unnamed local variable): it could well be, but you won't know unless you disassemble the generated code

In other words:

• If you store the size yourself, there is a good chance it will be as fast as the compiler could get it...
• but you expose yourself to maintenance wreck: what if suddenly you modify the vector and don't update the variable ;) ?

Anyhow, I seriously doubt it's worth the hassle. It's a micro-optimization at best, and unlikely to yield much of an improvement.