Efficient passing of std::vector

Question

When a C++ function accepts an std::vector argument, the usual pattern is to pass it by const reference, such as:

int sum2(const std::vector<int> &v)
{
   int s = 0;
   for(size_t i = 0; i < v.size(); i++) s += fn(v[i]);
   return s;
}

I believe that this code results in double dereferencing when the vector elements are accessed, because the CPU should first dereference v to read the pointer to the first element, which pointer needs to be dereferenced again to read the first element. I would expect that it would be more efficient to pass a shallow copy of the vector object on the stack. Such shallow copy would encapsulate a pointer to the first element, and the size, with the pointer referencing the same memory area as the original vector does.

int sum2(vector_ref<int> v)
{
   int s = 0;
   for(size_t i = 0; i < v.size(); i++) s += fn(v[i]);
   return s;
}

Similar performance, but much less convenience could be achieved by passing a random access iterator pair. My question is: what is flawed with this idea? I expect that there should be some good reason that smart people accept to pay the performace cost of vector reference, or deal with the inconvenience of iterators.

Edit: Based on the coments below, please consider the situation if I simply rename the suggested vector_ref class to slice or range. The intention is to use random-access iterator pairs with more natural syntax.

Answer 1

Pass by value unless you're certain passing by reference improves performances.

When you pass by value, copy elision may occur which will result in similar if not better performances.

Dave wrote about it here:

http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/

Answer 2

I believe that this code results in double dereferencing when the vector elements are accessed

Not necessarily. Compilers are pretty smart and should be able to eliminate common subexpressions. They can see that the operator [] doesn't change the 'pointer to the first element', so they have no need make the CPU reload it from memory for every loop iteration.

Answer 3

What is flawed with this idea?

Simple: It's premature optimization. Alternatives: Accept a vector<int> const& and use iterators or pass iterators directly to the function.

Answer 4

There is no double dereferencing because the compiler will probably pass the real pointer to the vector as the argument and not a pointer to a pointer. You can simply try this out and check the disassembly view of your IDE for what is actually going on behind the scenes:

void Method(std::vector<int> const& vec) {
 int i = vec.back();
}


void SomeOtherMethod() {
  std::vector<int> vec;
  vec.push_back(1);
  Method(vec);
}

What happens here? The vector is allocated on the stack. The first push back is translated to:

push        eax  // this is the constant one that has been stored in eax
lea         ecx,[ebp-24h] // ecx is the pointer to vec on the stack
call        std::vector<int,std::allocator<int> >::push_back

Now we call Method(), passing the vector const&:

lea         ecx,[ebp-24h] 
push        ecx  
call        Method (8274DC0h)

Unsurprisingly, the pointer to the vector is passed as references are nothing but permanently dereferenced pointers. Now inside Method(), the vector is accessed again:

mov         ecx,dword ptr [ebp+8] 
call        std::vector<int,std::allocator<int> >::back (8276100h)

The vector pointer is taken directly from the stack and written to ecx.

Answer 5

You're right that there's an extra indirection here. It's conceivable (though it would be surprising) if the compiler (with the help of link-time code generation) optimized it away.

What you've proposed is sometimes called slicing, and it's used extensively in some situations. Though, in general, I'm not sure it's worth the dangers. You have to be very careful about invaliding your slice (or someone else's).

Note that if you used iterators for the loop instead of indexing, then you'd deref the reference only a couple times (to call begin() and end()) rather than n times (to index into the vector).

int sum(const vector<int> &v)
{
   int s = 0;
   for (auto it = v.begin(); it != v.end(); ++it) {
       s += fn(*it);
   }
   return s;
}

(I'm assuming the optimizer will hoist the begin() and end() calls out of the loop. You could do it explicitly to be certain.)

Passing a pair of iterators instead of the container itself seems like the STL idiom. That would give you more generality, as the type of container can vary, but so can the number of dereferences needed.

Answer 6

What's wrong with your idea is that you already have two perfectly good solutions:

• Pass the vector as is, either by value (where the compiler will often eliminate the copy), or by (const) reference, and trust the compiler to eliminate the double indirection, or
• Pass an iterator pair.

Of course you can argue that the iterator pair is "less natural syntax", but I disagree. It is perfectly natural to anyone who's used to the STL. It is efficient, and gives you exactly what you need to work with the range, using std algorithms or your own functions.

Iterator pairs are a common C++ idiom, and a C++ programmer reading your code will understand them without a problem, whereas they're going to be surprised at your home-brewed vector wrappers.

If you're really paranoid about performance, pass the pair of iterators. If the syntax really bothers you, pass the vector and trust the compiler.