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
Array realloc size
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.
When you're making games, you can generally work out your correct capacities ahead of time, allocate that amount once, and then never reallocate.
Typical "best average case" pattern is to grow by 50%.
That's not necessarily the best case for what you're trying to do, though. The job of an engineer is to evaluate the problem at hand and select the appropriate solution. There will be no perfect fit that covers every single use case.
That's not necessarily the best case for what you're trying to do, though. The job of an engineer is to evaluate the problem at hand and select the appropriate solution. There will be no perfect fit that covers every single use case.
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.
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.
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)
(unless you expect to be running out of physical/ total available memory)
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.
There's an interesting analysis of the effect of realloc sizes here: https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
