One big pool or several type specific pools?

Question

Hello,

I'm working on a video game witch require high performance so I'm trying to setup a good memory strategy or a specific part of the game, the part that is the game "model", the game representation. I have an object containing a whole game representation, with different managers inside to keep the representation consistent, following the game rules. Every game entity is currently generated by a type-specific factory, so I have several factories that allow me to isolate and change the memory management of those entities as I wish.

Now, I'm in the process of choosing between those two alternatives :

1. Having a memory pool for each type : that will allow really fast allocation/deallocation and minimal fragmentation as an object pool already know the size of the allocated objects. One thing that bother me is to have several pools like that that are separate, maybe making the other solution more efficient...
2. Having one big memory pool shared by all factories of one game representation : (using something like boost::pool with some adapter functions) that way I've got all the game objects memory allocated together and can have one bit allocation for a game that I already know the total size (it's not always the case). I'm not sure it's a better solution than A because of possible fragmentation inside the pool, as there would be objects of different size in the same pool, but it looks like an easier one for memory analysis and other problem fixing.

Now, I had some real worlds experiences with the A so I'm not experienced with B and would like some advice regarding those solutions, for a long-life project. Wich solution seem better for a long-life project and why? (Note: a pool is really necessary in this case because the game model is used for game editing too so there will be lot of allocation/deallocation of little objects).

Edit for clarification : I'm using C++ if (it's not clear yet)

Answer 1

I don't have specific experience with the memory manager you are considering, but here are some general guidelines that may help:

• If you do not expect a shortage of memory, Option 1 would be best because as you state it is fast (faster than 2?), and having separate pools will make it easier to spot allocation/deallocation/buffer issues (assuming the pool manager has decent error detection capabilities).
• If memory could be an issue (as in your game will take a lot of memory compared to the target platform's commonly available memory), having one large pool will provide more efficient use of memory. Also, if you cannot accurately predict the average and maximum memory requirements per pool, this is a better choice unless the memory manager can dynamically grow the memory pools (and ideally dynamically release blocks from the pool as well). The only downsides to 2 that I see are that it could be slower (is it so?), and errors in memory management could be harder to detect.

You might get the best of both worlds (assuming speed is similar) by developing with multiple pools, but doing final testing and the production release with a single pool. That way, you can spot allocation/management issues during development but still benefit from the potentially more efficient single pool.

Answer 2

One of the possible solution is something between 1. and 2.

Use pools for small objects: one pool per object size. In this case you can easy find pool by storing pointers in array.

And in addition you can have one pool for large objects. In this case fragmentation is less probable and time overhead is not so critical because large objects are not allocated and deallocated very frequently.

Note about boost::pool. When testing performance of boost::pool, test not only allocation but also deallocation. I experienced that boost::pool and boost::fast_pool deallocation time can be extremally large. My case consisted of allocations and de-allocations of small objects of different sizes in one pool

Answer 3

The correct answer is specific to your problem domain. But in the problem domains that I work, the first is usually the one we choose.

I do realtime or near realtime code. Audio editing and playback mostly. In in that code, we generally cannot afford to allocate memory from the heap down in the playback engine. Most of the time malloc returns fast enough, but sometimes it doesn't. And that sometimes matters.

So our solutions is to have specific pools for certain objects, and use the general pool for everything else. The specific pools have a certain number of elements preallocated, and are implemented as a linked list (actually a queue), so allocation and release is never more than a couple of pointer updates and the cost of entering and leaving a critical section.

As a fallback for unusual cases; when someone needs to allocate from a special pool and it's empty - we will allocate a hunk of general memory (several objects) and add that to the special pool. Once an allocation is part of the special pool, it is NEVER returned to the general pool until the app exits or starts a new project.

Making good choices about the initial size and maximum size of the special pools are an important part of tuning the application.

Answer 4

One problem that you'll run into is that STL implementations are allowed to assume that two allocators of the same type are equivalent. This is the reason that Boost.Pool uses only one pool (technically it uses a different pool for each type). I.E., your allocators are not allowed to have any non-static members in the general case. If you're making a video game and you know that your STL implementation does not have this problem, then don't worry about this -- however there might still be some issues with list::splice and std::swap on containers.

Answer 5

Actually, I will go with 2. I can give you an example from linux kernel. In kernel, the dentry(directory entry) and inode objects should be cached in memory for longer time for better responsiveness to users. As inode object depends on the file system, each filesystem will create its own pool of objects. One more thing you could do if the objects are similar is to abstract out the objects and keep common attributes in one abstract object and store the object specific information using a container. Refer to the below code for complete idea.

http://lxr.linux.no/linux+v2.6.32/fs/ext2/super.c#L149

Answer 6

It's not practical to use stl or boost for any type of video game, for starters. You can be absolutely sure the second you use one stl container your memory is fragmented and your performance is hopelessly in the toilet compared to the ideal at least (since most everyone's code is in this category most people never notice and can't really compare to anything else). I didn't always think so strongly but over time I have seen even a couple lines of code is like a little gremlin that will eventually some day cause you great pain.

The first method is most common, and as someone who's done both it's probably the only way that's practical if you don't want to spend a lot lot LOT more time and energy on the problem than it's probably worth to you. The second way is better because it's more general and yet can be tailored to your exact needs, but it's a lot of work and not something to jump into lightly.