Vector [] vs copying

Question

What is faster and/or generally better?

vector<myType> myVec;
int i;
myType current;

for( i = 0; i < 1000000; i ++ )
{
 current = myVec[ i ];
 doSomethingWith( current );
 doAlotMoreWith( current );
 messAroundWith( current );
 checkSomeValuesOf( current );
}

or

vector<myType> myVec;
int i;

for( i = 0; i < 1000000; i ++ )
{
 doSomethingWith( myVec[ i ] );
 doAlotMoreWith( myVec[ i ] );
 messAroundWith( myVec[ i ] );
 checkSomeValuesOf( myVec[ i ] );
}

I'm currently using the first solution. There are really millions of calls per second and every single bit comparison/move is performance-problematic.

Answer 1

Test it. Both are equally readable to me, though.

Answer 2

Depends what the assignment operator for your type gets up to. And you are passing by reference to those functions, I hope? But as for all performance questions, if it is important to you, test your specific case yourself.

Answer 3

Accessing the variable with [] from your vector will look it up each time, taking a local copy would be a better idea, but it depends on the size of myType.

Answer 4

The first version may be needlessly expensive because it relies on creating a copy of the object in the vector. Unless myType is some very small and simple object, like an int, storing a reference may be a better idea. It should also be declared when you need it, and no earlier, to limit aliasing issues that might otherwise cause the compiler to emit less efficient code:

vector<myType> myVec;
for(int i = 0; i < 1000000; i ++ )
{
 myType& current = myVec[ i ];
 doSomethingWith( current );
 doAlotMoreWith( current );
 messAroundWith( current );
 checkSomeValuesOf( current );
}

One advantage of creating a copy, rather than using a reference, is that it might cause the compiler to load the object into a register, rather than read it from memory on every access. So both versions are worth trying.

Any of course, the copy vs reference advice applies to each of your functions too. Do they take the argument by value or reference? Depending on what they do with it, and how myType is defined, one might be faster than the other.

The second version is flawed because it (unless the compiler is able to optimize it away) requires the object to be looked up in memory every time. Depending on your STL implementation, there may also be a bit of overhead due to bounds checking on operator[].

Creating a temporary first, which is then passed to each of your functions is the right way to go. The question is whether that temporary should be of value type (myType), or reference type (myType&/const myType&)

Another option that may be worth exploring is putting each function call in its own separate loop. That hurts data locality in some ways, but if some of the functions use a lot of local data, it might perform better. It might also play nicer with the instruction cache.

But really, performance is extremely complicated. Caching, out of order execution, the exact semantics of myType (especially its copy constructor and size) and the amount of optimizations performed by the compiler are all unknown to us. So we cannot give you a reliable answer.

Guess who can: your compiler. Write the test. Try both. Time the results. Pick the faster one.

Answer 5

Besides avoiding multiple access to the same index and using a reference to avoid copying, you could use the fastcall calling convention in your functions. It instructs the compiler to pass parameters in registers, when possible, instead of pushing them to the stack.

However, the fastcall isn't standardized, so it's vendor specific.

Answer 6

I would like to place a comment in jalf's answer but it seems that I don't have enough reputation points in order to do so.

Could anyone explain to me why declaring the variable inside the loop is better than declaring it outside.

Thanks

Edit:

Sorry, I think I got it. If I understand correctly we cannot "assign" a new value to the reference.

C++ FAQ

Remember: the reference is the referent, so changing the reference changes the state of the referent. In compiler writer lingo, a reference is an "lvalue" (something that can appear on the left hand side of an assignment operator).