CODEWITHSUNDEEP
c++arraysperformancevector
user997112
user997112

Reputation: 30635

Does a vector use one more dereference to access elements than std::array?

To access elements of a std::vector the start of the vector has to be located via dereferencing a vector data member pointer. Does this pointer de-rerefence happen every time a vector element is accessed, or just once?

Upvotes: 2

Views: 142

Answers (3)

Gretchen
Gretchen

Reputation: 2334

It is up to the compiler, as Mats said. If we look at a simple example:

#include <vector>

int vector_function(std::vector<int> & v){
    v[3] = v[1];
    v[2] = v[4];
    return v[1];
}

int array_function(int *a){
    a[3] = a[1];
    a[2] = a[4];
    return a[1];
}

Then compile with gcc -c -O2, and run objdump -S on the .o file, we get:

for vector_function:
   0:   48 8b 17                mov    (%rdi),%rdx
   3:   8b 42 04                mov    0x4(%rdx),%eax
   6:   8b 4a 10                mov    0x10(%rdx),%ecx
   9:   89 42 0c                mov    %eax,0xc(%rdx)
   c:   89 4a 08                mov    %ecx,0x8(%rdx)
   f:   c3                      retq   

for array_function:
  10:   8b 47 04                mov    0x4(%rdi),%eax
  13:   8b 57 10                mov    0x10(%rdi),%edx
  16:   89 47 0c                mov    %eax,0xc(%rdi)
  19:   89 57 08                mov    %edx,0x8(%rdi)
  1c:   c3                      retq

we see that indeed there was only one extra instruction in the vector case (the mov (%rdi),%rdx, which loads the vector's internal pointer)

Note that this only works with optimization (and in particular, with inlining on) - otherwise the disassembly for vector_function is a complete mess (making function calls for each access)

Upvotes: 1

Mats Petersson
Mats Petersson

Reputation: 129474

Maybe, sometimes. It largely depends on the circumstances, and how you use it.

Quite often, the overhead can be optimised out, e.g. 

vector<int> v(100);

for(i = 0; i < 100; i++)
{
   v[i] = i;
}

should, in a decent compiler, only have ONE extra load instruction to get the internal buffer of the vector before the loop, and then just use that value throughout the loop.

Upvotes: 1

JuniorCompressor
JuniorCompressor

Reputation: 20025

I believe so. Vector's underlying array can be reallocated because it needs to expand on successive push backs. So the pointer to this array may change.

Upvotes: 1

Related Questions