TODO: stack-allocated container?
I was browsing a codebase when I noticed this usage pattern, several times:
void SomeFunction()
{
…
vector<some class> localVector;
…
localVector.push_back(some data);
…
}
In considered cases, the push_back doesn’t always happen and the number of pushed elements is not known ahead of time (i.e. there’s a good reason why a dynamic array is used). However what happens is that only a few elements are usually written to the array, and overall a small amount of memory is actually needed. So, it’s a bit painful to do an allocation/deallocation for this.
So it might be useful to allocate the initial memory on the stack (i.e. with alloca) and only switch to “real” memory allocations the first time the array is resized. If we stack-allocate say 16K initially, it could significantly reduce the number of small allocations performed by that kind of code. Something to try at some point.
EDIT: done! Works nicely.
February 14th, 2008 at 7:28 am
I know I’ve seen this somewhere before (in-place arrays or something). I have a template class that does this. The initial size is an int template parameter so alloca isn’t needed. You want the constructor/destructor to be as simple as possible so cases where even nothing is added to the vector/array have very little cost.
/*! \brief An Array with an initial allocation of size N stored within the object itself.
This class works just like Array except the first allocation is stored within the
object itself (eliminating calls to malloc until capacity must be expanded beyond N).
*/
template
class StaticArray
February 14th, 2008 at 8:10 am
I removed the two extra posts where you tried to copy-paste the code. Indeed, the blog apparently tries to interpret it as HTML code and messes everything up. I’ll have a look later, I don’t know if there’s a good way to write code here (…).
March 13th, 2008 at 12:56 pm
Havok has a stack-allocated dynamic array implementation called HkLocalArray. We used it frequently on BioShock to minimize unnecessary heap allocations.
There’s also an implementation in the book “Imperfect C++” by Matthew Wilson, in chapter 32.2.3, starting with auto_buffer.
-Chris Kline, 2K Boston
March 14th, 2008 at 1:27 am
I didn’t know about HkLocalArray, good to hear. I admit I never actually used Havok