Jump to content
  • Advertisement
Sign in to follow this  
Alundra

Array realloc size

This topic is 1254 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

Hi,

Strategy to avoid lot of realloc is used everywhere nowadays but how really do that correct.

Is it good to realloc double of the actual capacity or "+4" each time is a better choice ?

Thanks

Share this post


Link to post
Share on other sites
Advertisement

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
Maybe semi on/ off topic, but why dont you use std::vector or similar to take care of it?
(unless you expect to be running out of physical/ total available memory)

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

The question is moot, because you should use a library to implement such operations instead of writing them yourself, or if you do write them yourself, you should test extensively instead of asking on a forum.

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!