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
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
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.
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.
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.