CODEWITHSUNDEEP
c++stlvectorcompiler-optimization
peter karasev
peter karasev

Reputation: 2614

performance of std::vector c++ size() inside loop in member function

Similar question, but less specific: In a "i < vector.size()" loop condition, is size() called each iteration?

Suppose we're in a member function like:

void  Object::DoStuff()  {

   for( int k = 0; k < (int)this->m_Array.size(); k++ )
   {  
       this->SomeNotConstFunction();
       this->ConstFunction();
       
       double x = SomeExternalFunction(i);
   }
}

  1. I'm willing to believe that if only the "SomeExternalFunction" is called that the compiler will optimize and not redundantly call size() on m_Array ... is this the case?

  2. Wouldn't you almost certainly get a boost in speed from doing

    int N = m_Array.size() for( int k = 0; k < N; k++ ) { ... }

    if you're calling some member function that is not const ?

Perhaps I can clarify:

Firstly, it's not to optimize per-se but just understand what the compiler will and will not fix. Usually I use the size() function but I ask now because here the array might have millions of data points.

Secondly, the situation is that "SomeNotConstFunction" might have a very rare chance of changing the size of the array, or its ability to do so might depend on some other variable being toggled. So, I'm asking at what point will the compiler fail, and what exactly is the time cost incurred by size() when the array really might change, despite human-known reasons that it won't?

Third, the operations in-loop are pretty trivial, there are just millions of them but they are embarrassingly parallel. I would hope that by externally placing the value would let the compiler vectorize some of the work.

Upvotes: 3

Views: 2959

Answers (4)

CodeLurker
CodeLurker

Reputation: 1371

In MSVC 2015, it does a return (this->_Mylast() - this->_Myfirst()). I can't tell you offhand just how the optimizer might deal with this; but unless your array is const, the optimizer must allow for the possibility that you may modify its number of elements; making it hard to optimize out. In Qt, it equates to an inline function that that does a return d->size; ; that is, for a QVector.

I've taken to doing it in one particular project I'm working on, but it is for performance-oriented code. Unless you are interested in deeply optimizing something, I wouldn't bother. It probably is pretty fast any of these ways. In Qt, it is at most one pointer dereferencing, and is more typing. It looks like it could make a difference in MSVC.

I think nobody has offered a definitive answer so far; but if you really want to test it, have the compiler emit assembly source code, and inspect it both ways. I wouldn't be surprised to find that there's no difference when highly optimized. Let's not forget, though, that unoptimized performance during debug is also a factor that might be taken into consideration, when a lot of e.g. number crunching is involved.

I think the OP's original ? really could use to give how the array is declared.

Upvotes: 1

user1084944
user1084944

Reputation:

Do not get into the habit of doing things like that.

The cases where the optimization you make in (2) is:

  • safe to do
  • has a noticeable difference
  • something your compiler cannot figure out on its own

are few and far in-between.

If it were just the latter two points, I would just advise that you're worrying about something unimportant. However, that first point is the real killer: you do not want to get in the habit of giving yourself extra chances to make mistakes. It's far, far easier to accelerate slow, correct code than it is to debug fast, buggy code.

Now, that said, I'll try answering your question. The definitions of the functions SomeNotConstFunction and SomeConstFunction are (presumably) in the same translation unit. So if these functions really do not modify the vector, the compiler can figure it out, and it will only "call" size once.

However, the compiler does not have access to the definition of SomeExternalFunction, and so must assume that every call to that function has the potential of modifying your vector. The presence of that function in your loop guarantees that `size is "called" every time.

I put "called" in quotes, however, because it is such a trivial function that it almost certainly gets inlined. Also, the function is ridiculously cheap -- two memory lookups (both nearly guaranteed to be cache hits), and either a subtraction and a right shift, or maybe even a specialized single instruction that does both.

Even if SomeExternalFunction does absolutely nothing, it's quite possible that "calling" size every time would still only be a small-to-negligible fraction of the running time of your loop.

Edit: In response to the edit....

what exactly is the time cost incurred by size() when the array really might change

The difference in the times you see when you time the two different versions of code. If you're doing very low level optimizations like that, you can't get answers through "pure reason" -- you must empirically test the results.

And if you really are doing such low level optimizations (and you can guarantee that the vector won't resize), you should probably be more worried about the fact the compiler doesn't know the base pointer of the array is constant, rather than it not knowing the size is constant.

If SomeExternalFunction really is external to the compilation unit, then you have pretty much no chance of the compiler vectorizing the loop, no matter what you do. (I suppose it might be possible at link time, though....) And it's also unlikely to be "trivial" because it requires function call overhead -- at least if "trivial" means the same thing to you as to me. (again, I don't know how good link time optimizations are....)

If you really can guarantee that some operations will not resize the vector, you might consider refining your class's API (or at least it's protected or private parts) to include functions that self-evidently won't resize the vector.

Upvotes: 9

Bo Persson
Bo Persson

Reputation: 92271

The micro optimization remarks are probably because the two most common implementations of vector::size() are

return _Size;

and

return _End - _Begin;

Hoisting them out of the loop will probably not noticably improve the performance.

And if it is obvious to everyone that it can be done, the compiler is also likely to notice. With modern compilers, and if SomeExternalFunction is statically linked, the compiler is usually able to see if the call might affect the vector's size.

Trust your compiler!

Upvotes: 2

Gerald
Gerald

Reputation: 23499

The size method will typically be inlined by the compiler, so there will be a minimal performance hit, though there will usually be some.

On the other hand, this is typically only true for vectors. If you are using a std::list, for instance, the size method can be quite expensive.

If you are concerned with performance, you should get in the habit of using iterators and/or algorithms like std::for_each, rather than a size-based for loop.

Upvotes: 3

Related Questions