Any sane implementation of std::vector is probably going to have three pointers of overhead, and might allocate twice as much memory as required in the worst case when you push a bunch of objects into it. That doesn't seem totally absurd to me - was yours much worse, or am I just being more tolerant of it?
Sorry, you are correct; I should have been more specific: the memory management overhead was tremendous. For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat. Moving to a fixed size array in C++ I saw an easy 50% drop in CPU usage.
I think STL is a great set of libraries, but I also think they're sometimes too easy to use if you don't consider alternative implementations and the impact of each way.
For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat.
That doesn't sound right at all.
Of course, if you add or remove objects at the vector's head, all of its data will be moved, though probably not reallocated. But if you have a need for frequent additions and deletions anywhere but the tail of the vector, you picked a wrong data structure. Double ended queue (<deque>) would would've suited you much better.
Moving to a fixed size array in C++ I saw an easy 50% drop in CPU usage.
Did you reimplement element addition/deletion logic from scratch?
I wouldn't call myself an expert on vertex buffers, but IIRC the OpenGL API to load data into a buffer just takes a pointer to the data and a size, so requires that your data is contiguous in memory beforehand - so deque may not have been an option.
Agreed. But I can't think of any data structure that would offer you contiguous, order-preserving storage and O(1) insertions/deletions of arbitrary elements.
There are actually implementations of deque which can store elements contiguously: imagine a vector where the "first element" is placed in the middle of the vector, and push_{front,back} reallocate whenever either end is reached. It wastes more memory than the typical deque implementation, but the elements are contiguous.
> Sorry, you are correct; I should have been more specific: the memory management overhead was tremendous. For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat.
If that was the case, you were doing something wrong.
You're being more tolerant. When you're building a high performance game engine for fixed target hardware, the last thing you want is to be doubling up the size of your arrays.
If you know before the allocation how much entries it must hold at maximum, you can give an std::vector that information. There is simply no case where you are forced to require more memory with an std::vector but not with a manual implementation.
If you have a lot of small vectors those three pointers can be expensive. On a 64 bit machine they're 8 bytes apiece.
If you know the vector isn't going to be enormous you can swap two of those pointers for unsigned integers, cutting overhead down to 16 bytes total. If you know more about your data and usage patterns you can probably get it further. For very small vectors of largely static data you might trade one of the integers for linear-time insertion and deletion. If capacity is known at compile-time you can make it part of the type. If you know that size() will always equal capacity() you can get rid of the size int.
It's also worth noting that you don't have to double your storage on every reallocation to avoid linear-time insertions - you just have to multiply it by some constant that's greater than one. If you don't know how many reallocs you're going to do, but you know that it isn't many, you might want to just multiply your capacity by 1.1 every time to avoid a lot of wasted space. Assuming, of course, that you're happy with bringing floating point computation in, and that you've thought about how you're going to increase the capacity of a vector of size 1...
If you don't overallocate the vector then push_back() runs in linear time instead of amortized constant which is generally a worse tradeoff. You can avoid the whole issue by calling reserve() ahead of time, but if you don't know how many elements you're going to have then you're in trouble, but you won't be able to do much better by replacing vector with your own array either.
It's great until you need to allocate 3.9Gb of vector on a 32bit machine.
Somebody said computer science is solving yesterdays problems on tomorrows hardware, the rest of science is solving tomorrows problems on yesterdays hardware
