C++ STL: Array vs Vector: Raw element accessing performance

by

Element access time in a typical implementation of a std::vector is the same as element access time in an ordinary array available through a pointer object (i.e. a run-time pointer value)

std::vector<int> v;
int *pa;
...
v[i];
pa[i]; 
// Both have the same access time

However, the access time to an element of an array available as an array object is better than both of the above accesses (equivalent to access through a compile-time pointer value)

int a[100];
...
a[i];
// Faster than both of the above

For example, a typical read access to an int array available through a run-time pointer value will look as follows in the compiled code on x86 platform

// pa[i]
mov ecx, pa // read pointer value from memory
mov eax, i
mov <result>, dword ptr [ecx + eax * 4]

Access to vector element will look pretty much the same.

A typical access to a local int array available as an array object will look as follows

// a[i]
mov eax, i
mov <result>, dword ptr [esp + <offset constant> + eax * 4]

A typical access to a global int array available as an array object will look as follows

// a[i]
mov eax, i
mov <result>, dword ptr [<absolute address constant> + eax * 4]

The difference in performance arises from that extra mov instruction in the first variant, which has to make an extra memory access.

However, the difference is negligible. And it is easily optimized to the point of being exactly the same in multiple-access context (by loading the target address in a register).

So the statement about “arrays being a bit faster” is correct in narrow case when the array is accessible directly through the array object, not through a pointer object. But the practical value of that difference is virtually nothing.

You may be barking up the wrong tree. Cache misses can be much more important than the number of instructions that get executed.

More Related Contents:

  1. Is std::vector so much slower than plain arrays?
  2. How to initialize std::vector from C-style array?
  3. array vs vector vs list
  4. How to cheaply assign C-style array to std::vector?
  5. Array of vectors
  6. Thou shalt not inherit from std::vector
  7. What’s the most efficient way to erase duplicates and sort a vector?
  8. How to convert vector to array
  9. vector vs. list in STL
  10. How do I sort a std::vector by the values of a different std::vector?
  11. How do I erase an element from std::vector by index?
  12. Is it safe to assume that STL vector storage is always contiguous?
  13. How to get std::vector pointer to the raw data?
  14. Efficient way of reading a file into an std::vector?
  15. Looking for C++ STL-like vector class but using stack storage
  16. Appending a vector to a vector [duplicate]
  17. Sorting a vector in descending order
  18. How to initialize a vector in C++ [duplicate]
  19. Why is it OK to return a ‘vector’ from a function?
  20. Are vectors passed to functions by value or by reference in C++
  21. Is the use of std::vector objects in C++ acceptable, or should I use an alternative?
  22. STL vector and thread-safety
  23. Sorting a std::vector by the string?
  24. what is the best modern c++ approach to construct and manipulate a 2d array [closed]
  25. How do you copy the contents of an array to a std::vector in C++ without looping?
  26. How do I store arrays in an STL list?
  27. Why would I prefer using vector to deque
  28. std::vector removing elements which fulfill some conditions
  29. Converting between C++ std::vector and C array without copying
  30. “Right” way to deallocate an std::vector object

Leave a Comment