Dynamic arrays like std::vector must be tweaked for a special use case as well, for instance it is quite essential to pre-allocate the array to a capacity of the expected number of entries using std::vector::reserve() so that no excessive re-allocation takes place while the array grows. Also special care must be taken if the objects have an expensive copy operation (that's where the new move-semantic in C++11 may help a lot).
It's not so much that dynamic arrays are the problem as std::vector specifically is the problem. Many game engines implement their own version of vector which is designed to grow by power-of-2. That way if you add 100 elements, the vector has already reserved 128 slots. If you add 129, it'll automatically reserve 256. Etc. Automatic power-of-2 growth turns out to have very nice performance and memory characteristics.
std::vector itself might work that way, but since the implementation can be different on different platforms, it's usually a better idea to write your own when performance matters.
I doubt there are any vector implementations that don't use exponential growth. Without exponential growth, push_back doesn't have constant time, and adding n elements doesn't take O(n) time. Since push_back is required to take amortized constant time, an implementation without exponential growth (or some kind of magic) wouldn't be standard conforming.
Whether the exponential growth is in the form of doubling or not is just a constant factor. There's nothing magical about using powers of two. Depending on the accounting used by the allocator you're using, there may be synergies, or there might not be - some allocators require a few bytes more than the allocation request, and this requirement might inflate the underlying memory request more than necessary.
> I doubt there are any vector implementations that don't use exponential growth.
Trivia fact time: Westwood Studios wrote their own vector implementation for the original Command&Conquer, and reused it for later games in the same series, until Renegade/Generals. That implementation uses linear growth, capacity grows by 10 elements each time.
Whether the exponential growth is in the form of doubling or not is just a constant factor. There's nothing magical about using powers of two.
Actually, powers-of-two reduce memory fragmentation for all objects of the same size. Since memory fragmentation is one of the central causes of performance problems in modern large projects, it's really important. Firefox spent a bunch of time realizing their performance problems were due to an incredible amount of fragmentation.
Exponential growth gives you most of the benefit, but specifically growing by a factor of 2 gives you the rest.
If the overhead of an allocation is h bytes, and your allocator stores it in e.g. the prefix of the memory allocation, then all your allocations will be for 2x+h. And this will not have nice effects for your memory fragmentation. In this case, you'd be better off allocating 2x-h each time.
Of course, modern allocators tend to store accounting information using separately reserved arrays of records to avoid exactly this problem. But if you use a language like C# or Java, you come back to around to this problem. Without using a double indirection for array data, object header and array length are stored contiguously with array data. So allocating an array with a power of two will again not be a power of two for the underlying allocator. Much less of a problem with precise GC, but not all GC'd languages use precise moving GC, and some languages let you pin arrays for interop with C. So it's something to be aware of.
I agree! It's just that C++ people from outside the gaming industry always give me the evil look when I start ranting about how useless the std containers actually are ;)
