Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient passing of std::vector

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.

like image 811
shojtsy Avatar asked Nov 20 '09 15:11

shojtsy


People also ask

Is std::vector fast?

A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.

Is passing a vector by reference faster?

Because the value is typically already in a register, it is slightly faster. If you pass a larger structure or array, copying the content (for by-value) takes longer than copying its pointer (for by-ref). vector of pointers to objects again could be many bytes, so reference is faster.

Why is it best to pass a vector as a reference?

Passing by value keeps the original vector unchanged and doesn't modify the original values of the vector. However, the above style of passing might also take a lot of time in cases of large vectors. So, it is a good idea to pass by reference.

Is vector better than array C++?

Vector is better for frequent insertion and deletion, whereas Arrays are much better suited for frequent access of elements scenario. Vector occupies much more memory in exchange for managing storage and growing dynamically, whereas Arrays are a memory-efficient data structure.


1 Answers

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.

like image 131
int3 Avatar answered Oct 04 '22 06:10

int3