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.

Solution 1

Interesting 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.
• If you do not, it will depend on whether the compiler can establish that nothing else is modifying the vector; if not, it cannot cache the variable, and will need to perform memory reads (L1) every time.

It's a micro-optimization. In general, it will be unnoticeable, either because the performance does not matter or because the compiler will perform it regardless. In a critical loop where the compiler does not apply the optimization, it can be a significant improvement.

Solution 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.

Solution 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.

Solution 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
}

Solution 5

I always save vector.size() in a local variable (if the the size doesn't change inside the loop!).
Calling it on each iteration vs. saving it in a local variable can be faster. At least, that's what I experienced.
I can't give you any real numbers, as I tested this a very long time ago. However from what I can recall, it made a noticeable difference (however potentially only in debug mode), especially when nesting loops.

And to all the people complaining about micro-optimization:
It's a single additional line of code that introduces no downsides.

View more solutions

Comments

[Mr. Boy]

"In every implementation I've, seen vector::size() performs a subtraction of end() and begin(), ie its not as fast as reading a variable." -- yes but the compiler may still take that outside the loop in theory, or otherwise monkey about with the C++ code you are looking at.

[Steve Jessop]

I think that if your compiler isn't smart enough to inline vector::size, the performance of any code using standard template containers will be so desperately awful that removing a few calls to size won't help. So it's not really a function call overhead. If it was, what about all the calls to operator[], or operator* on an iterator? We could assume they're slow too, and iterate over the vector using a pointer starting with &vec[0]. If you don't trust your implementation of std::vector, best just to write in C instead of C++...

[Steve Jessop]

That said, you may well be right that it would be a small speedup, just not because of the inlining issue the questioner is worried about. For instance, maybe size hits memory every time (if the compiler can't prove to itself that the size won't change), whereas using a local variable allows the compiler to keep the size in a register (if you have enough registers). You never know, basically.

[stakx - no longer contributing]

@Steve Jessop: Well pointed out. The real time saving (even if it's very small) of course would result from calling the function only once instead of many times, not from the fact that the function call mechanism itself is more expensive than reading a variable. -- However, I wouldn't want to rely on an optimising compiler to take the function call outside of the loop if I can easily do this myself.

[MSalters]

"Will the result be cached?" That's a question which can have 2 answers even within a single function. Compilers are quite good at figuring out whether and where they have enough registers to save an intermediate result.

[MSalters]

You're asssuming that size() is used just in the loop condition. What if each iteration calls foo(vec[i], vec.size()-i) ? You can't make that call using for_each.

[Matthieu M.]

@MSalters: I couldn't agree more. And in particular if the compiler decides there isn't enough space, then introducing a spurious variable may not yield any improvement.

[TheAhmad]

There are some situations where using a local variable is significantly faster. For example, I had a Pintool with a loop over a 30000 element vector that was called before the execution of each basic block of the traced program. For a single run, after 8 minutes even half of the program was not finished. When I replaced size() with a variable, the execution time reduced to 80 seconds.

[Matthieu M.]

@TheAhmad: Indeed. As all micro-optimizations it rarely is worth it, but it can sometimes have dramatic effect -- I have altered the conclusion to better reflect this. Note that if possible you should use for (auto& e : vec) to iterate over the vector, and you will get the most optimal form of iteration.

[Viktor Sehr]

True, compilers often find's these kind of optimizations. But if it's a hotspot, I would still make the optimization by myself.