To use std::vector or not to use std::vector...
...that is the question.
I've written my own Array class, which is basically a dynamic-sized array. It automatically handles things like memory allocation/deallocation and allows resizing/random insertion/deletion.
But that was before I found out about std::vector. It appears to work almost exactly the same as my custom array class. The thing is, I'm a little worried about performance. std::vector performs pretty much the same as my custom class... except that it's much, much slower at random insertion/deletion. I tested a massive 128mb array (containing 2^10 elements), and inserting 8000 new elements into the beginning of that array took over 10 minutes. My custom array did it in 2.6 seconds. Both tests were in release mode.
My custom array uses an internal array of pointers, which point to dynamically allocated data representing the elements of the array. Because of this, the array isn't contiguous which I'm guessing is why it's faster (not really sure, though). When resizing the array to accommodate new elements, the array of pointers resizes up to the nearest power of two elements, and a new block of memory is allocated for each of the newly created pointers. This way, the amount of data that needs to be copied around is small, because I don't actually move any data during array resize, only the pointers to that data.
In my game, I'm going to be randomly inserting/deleting data from large arrays, so this is why I'm so concerned about performance.
I have a couple of questions:
1) std::vector is doing something behind the scenes that's making it slower, but probably more safe to use. I was wondering, what could it possibly be doing that would cause it to be several orders of magnitude slower?
2) How is my custom array class? Does there seem to be any inherent problems with it?
And most importantly:
3) Should I use std::vector, even though it's slower? What do you guys use in your projects when you need a dynamic array?
std::vector holds elements contiguously by value --- which allows fun things like passing a pointer to the first element to a C style function expecting a C style array, and knowing it will work.
It also means it has to copy back every single element in the vector when you push_front. There's nothing it's worse at.
std::deque gives up the benifit of being contiguous, but will be much much faster at frontal insertions.
These are just 2 of the... 7? different containers of the standard C++ library. Showing us the source code of your container might let us point out the closest match in the C++ standard library.
It also means it has to copy back every single element in the vector when you push_front. There's nothing it's worse at.
std::deque gives up the benifit of being contiguous, but will be much much faster at frontal insertions.
These are just 2 of the... 7? different containers of the standard C++ library. Showing us the source code of your container might let us point out the closest match in the C++ standard library.
Quote:Original post by Sc4Freak
I have a couple of questions:
1) std::vector is doing something behind the scenes that's making it slower, but probably more safe to use. I was wondering, what could it possibly be doing that would cause it to be several orders of magnitude slower?
2) How is my custom array class? Does there seem to be any inherent problems with it?
And most importantly:
3) Should I use std::vector, even though it's slower? What do you guys use in your projects when you need a dynamic array?
1) Vectors are guaranteed to be contiguous. So when you add things at the front, it'll reallocate the whole chunk of memory, move the elements around, and then insert the new elements at thge beginning.
2) Does it handle objects with constructors / destructors? std::vector will handle them correctly, and call the destructors, copy constructors, operator=, etc correctly.
3) As always, you should use the standard components unless they become a bottleneck (as in this case). So I don't see any problem with using your own class here, so long as you've profiled a real case (In your game will you actually be adding 8000 objects to the beginning of the list on a regular basis?), and it's turned out to be a bottleneck.
To backup MaulingMonkeys comment, a std::vector is required to store data in a contiguous block, if the block is full the entire chunk is copied into a larger one and insertions at any point other than the end require that all proceeding elements be copied forward, this is why the performance is so bad. What std::vector does offer though is blisteringly fast random access and iteration (since its contiguous).
A std::deque is more similar to your array implementation and is optimised for insertions at both the front and back.
Actually if you dont require contiguous memory access and are dealing with a large but unknown number of elements/insertions then often a deque is a better choice than a vector.
In your Array class, do you separate memory allocation and class/element construction? In the STL this functionality is the job of an allocator (std::allocator, but its pluggable).
Basically it makes for more efficient growth of a container since objects can be constructed when required (Just-In-Time construction) but the memory itself can be pre-allocated and already reserved.
Edit: Yes as Evil Steve pointed out the standard containers handle constructors etc correctly, this is actually vital!
The standard containers employ the RAII idiom.
If, for example, a constructor was to throw an exception would your Array class deallocate its acquisitioned memory correctly?
A std::deque is more similar to your array implementation and is optimised for insertions at both the front and back.
Actually if you dont require contiguous memory access and are dealing with a large but unknown number of elements/insertions then often a deque is a better choice than a vector.
In your Array class, do you separate memory allocation and class/element construction? In the STL this functionality is the job of an allocator (std::allocator, but its pluggable).
Basically it makes for more efficient growth of a container since objects can be constructed when required (Just-In-Time construction) but the memory itself can be pre-allocated and already reserved.
Edit: Yes as Evil Steve pointed out the standard containers handle constructors etc correctly, this is actually vital!
The standard containers employ the RAII idiom.
If, for example, a constructor was to throw an exception would your Array class deallocate its acquisitioned memory correctly?
http://www.sgi.com/tech/stl/Vector.html
Go there ^, scroll to the bottom, read note #4, and study.
If learn the STL and you will find that it is faster, more powerful, and more flexible than 99.9% of the generic containers made by solo programmers.
Go there ^, scroll to the bottom, read note #4, and study.
If learn the STL and you will find that it is faster, more powerful, and more flexible than 99.9% of the generic containers made by solo programmers.
Hasn't anyone written a proper, simple guide to all the containers in the STL? Seems like it'd be a good thing to direct newbies to.
This here journal post (scroll down to "I should have known better..") might be helpful in making your decission. In some cases, when you have detailed knowledge of the typical usage pattern, it might pay off to implement your own container. But if you need a fairly run-of-the-mill solution, your time is probably better spent elsewhere.
Judging from your description, it would perhaps be better to compare your array class with std::deque instead (which, in terms of implementation, sounds a lot like your class anyway).
Quote:Original post by Promit
Hasn't anyone written a proper, simple guide to all the containers in the STL? Seems like it'd be a good thing to direct newbies to.
Of course someone has. Although perhaps you meant this effort that was started but not completed.
Quote:Original post by Promit
Hasn't anyone written a proper, simple guide to all the containers in the STL? Seems like it'd be a good thing to direct newbies to.
I my self usually use http://cppreference.com/ when I am looking up STL functionality.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement