Using arrays or std::vectors in C++, what's the performance gap?
Using C++ arrays with new
(that is, using dynamic arrays) should be avoided. There is the problem you have to keep track of the size, and you need to delete them manually and do all sort of housekeeping.
Using arrays on the stack is also discouraged because you don't have range checking, and passing the array around will lose any information about its size (array to pointer conversion). You should use boost::array
in that case, which wraps a C++ array in a small class and provides a size
function and iterators to iterate over it.
Now the std::vector vs. native C++ arrays (taken from the internet):
// Comparison of assembly code generated for basic indexing, dereferencing,
// and increment operations on vectors and arrays/pointers.
// Assembly code was generated by gcc 4.1.0 invoked with g++ -O3 -S on a
// x86_64-suse-linux machine.
#include <vector>
struct S
{
int padding;
std::vector<int> v;
int * p;
std::vector<int>::iterator i;
};
int pointer_index (S & s) { return s.p[3]; }
// movq 32(%rdi), %rax
// movl 12(%rax), %eax
// ret
int vector_index (S & s) { return s.v[3]; }
// movq 8(%rdi), %rax
// movl 12(%rax), %eax
// ret
// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.
int pointer_deref (S & s) { return *s.p; }
// movq 32(%rdi), %rax
// movl (%rax), %eax
// ret
int iterator_deref (S & s) { return *s.i; }
// movq 40(%rdi), %rax
// movl (%rax), %eax
// ret
// Conclusion: Dereferencing a vector iterator is the same damn thing
// as dereferencing a pointer.
void pointer_increment (S & s) { ++s.p; }
// addq $4, 32(%rdi)
// ret
void iterator_increment (S & s) { ++s.i; }
// addq $4, 40(%rdi)
// ret
// Conclusion: Incrementing a vector iterator is the same damn thing as
// incrementing a pointer.
Note: If you allocate arrays with new
and allocate non-class objects (like plain int
) or classes without a user defined constructor and you don't want to have your elements initialized initially, using new
-allocated arrays can have performance advantages because std::vector
initializes all elements to default values (0 for int, for example) on construction (credits to @bernie for reminding me).
Is std::vector so much slower than plain arrays?
Using the following:
g++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray completed in 2.196 seconds
UseVector completed in 4.412 seconds
UseVectorPushBack completed in 8.017 seconds
The whole thing completed in 14.626 seconds
So array is twice as quick as vector.
But after looking at the code in more detail this is expected; as you run across the vector twice and the array only once. Note: when you resize()
the vector you are not only allocating the memory but also running through the vector and calling the constructor on each member.
Re-Arranging the code slightly so that the vector only initializes each object once:
std::vector<Pixel> pixels(dimensions * dimensions, Pixel(255,0,0));
Now doing the same timing again:
g++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector completed in 2.216 seconds
The vector now performance only slightly worse than the array. IMO this difference is insignificant and could be caused by a whole bunch of things not associated with the test.
I would also take into account that you are not correctly initializing/Destroying the Pixel object in the UseArrray()
method as neither constructor/destructor is not called (this may not be an issue for this simple class but anything slightly more complex (ie with pointers or members with pointers) will cause problems.
Performance gap between vectorbool and array
std::vector<bool>
isn't like any other vector. The documentation says:
std::vector<bool>
is a possibly space-efficient specialization of
std::vector
for the typebool
.
That's why it may use up less memory than an array, because it might represent multiple boolean values with one byte, like a bitset. It also explains the performance difference, since accessing it isn't as simple anymore. According to the documentation, it doesn't even have to store it as a contiguous array.
Vector vs Array Performance
I can guarantee that LLVM does infact misoptimize std::vector (if you are in fact optimising at all), at least as of right now. It does not correctly inline many of the function calls involved. You will get better performance with GCC.
Vectors vs Array in C++ [duplicate]
In programming as in life there is no free meal... Keep that in mind all the time. If you want nice and convenient features you have to pay a price.
std::vector
will add some complexity to your code you don't see. Adding items to your std::vector
does more, then just writing a value. It may allocate new memory and copy the old values to it. And several more things you won't really see.
Switching to std::array
won't give you the boost you might looking for. It is a bit simpler then std::vector
. It is the way to got, when you are looking for an supplement of an plain c array. But still, it will add complexity too.
So my advice is and you will find similar once in good books. Try to optimize your code on algorithm base and not on the implementation. There is much more potential in possible flawed algorithms or there may be much better once. The implementation won't give you the ground braking boost.
Performance implications of using a list of vectors versus a vector of vectors when appending in parallel
Taken from the comments, it appears vectors of vectors can happily be used.
Related Topics
Operator≪ and Strict Weak Ordering
Is Meyers' Implementation of the Singleton Pattern Thread Safe
Why Does Changing 0.1F to 0 Slow Down Performance by 10X
How Approximation Search Works
How to Find Out If an Item Is Present in a Std::Vector
How to Get the Directory That a Program Is Running From
How to Enforce Move Semantics When a Vector Grows
How to Instantiate Objects from a String Holding Their Class Name
Why Aren't My Include Guards Preventing Recursive Inclusion and Multiple Symbol Definitions
How to Fill 2D Array With the User'S Input
Thou Shalt Not Inherit from Std::Vector