Sign in to follow this  
Alundra

Array realloc size

Recommended Posts

There's no portable advice for that. The underlying memory allocator and the reason that you're expanding the buffer will affect the most effective memory growth strategy. For instance, some memory allocators can never expand in place, in which case incremental growth can be very expensive. However, if your underlying memory allocator can grow in place then growing by a small value can be effective. Some allocators will allow you to query if an in place growth is possible, or do an in place only expansion. Ex: MSVC has the _expand() function.

Share this post


Link to post
Share on other sites

I read growing by 2x is kind of like a worst case scenario, because the newly needed space is always just a tiny bit too large to reuse the then free space from the former allocations.

I recall calculating a good value for myself as just below 1.68..., but don't remember the formula I came up with.

Growing by +4 or some other fixed value is always bad, because the time spent on reallocations gets too much to run in amortized O(1) time for each push_back into the array.

Edited by wintertime

Share this post


Link to post
Share on other sites

Generally properly planned AAA games have what is known as a "memory budget", especially on consoles.

 

The memory budget dictates what subsystems can use a maximum of what amounts of memory, and all the subsystems must stick within this memory budget. During debugging and testing, the allocator might even contain code to raise assertions if the memory budgets are exceeded at any time.

 

Memory budgets have historically been extremely important as consoles have had very limited amount of memory compared to PCs and no ability to swap to disk if they run out.

 

This is something that can still help you though when writing your own allocation and memory management, as part of this can be how often you allocate as well as how much. Pre-allocation of memory in smart ways can help you a lot with the speed and efficiency of your game's code.

Share this post


Link to post
Share on other sites

General purpose reallocation will usually happen exponentially.  I believe g++ doubles vector capacity, and VS multiplies by 1.5.  Java ArrayLists increase by a factor of 1.5 as well IIRC.  This information may be a bit outdated as it's been a few years since I checked.  Of course, the best reallocation strategy is to not reallocate at all, or realloc exactly what you'll ever need, but that requires knowing your data set.

 

At some point someone will probably bring up the golden ratio, which is supposedly the ideal growth rate for mathematical reasons I don't really understand.

Share this post


Link to post
Share on other sites

I already use pool array for lighting on each frame, things like that, as Hodgman said, but was a more general question to have advice or just a general discussion on the subject.

Edited by Alundra

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this