Jump to content
  • Advertisement
Sign in to follow this  
Sc4Freak

To use std::vector or not to use std::vector...

This topic is 4149 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

...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?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!