Performance of vector::size() : is it as fast as r

问题:

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.

回答1:

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.

回答2:

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.

回答3:

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.

回答4:

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
}

回答5:

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.

回答6:

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.

回答7:

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.