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

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.

Answers


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.


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.


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.


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
}

I always save the vector.size() in a local variable (Only if the vector.size() doesn't change in the for loop!). Why? Because calling it on each iteration vs. saving it in a local variable is much much faster. That's what I experienced in my applications. I can't give you any real numbers, but it made a noticeable difference.

And to all those people complaining about micro-optimization: When you write a huge for loop, do you simply (just for fun) insert an unnecessary subtraction in it? No, you don't.

Why don't you simply profile it? A huge vector and std::time will do just fine.


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.


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.


Need Your Help

DataGridViewColumnHeader Make Bold

c# winforms datagridview

I have one DataGridView and want to make the Header text Bold.