Advanced Memory Pooling Strategies for AI

Alex J. Champandard on June 21, 2007

Using the most basic type of memory pooling can improve the performance of your AI engine dramatically. However, your memory usage may not be optimal at first if you have one big memory pool.

Problems arise when pooling AI tasks because of the following:

  1. All tasks are different and they have various sizes in memory.

  2. Some tasks use practically no memory while others require hundreds of bytes.

  3. With one pool using a maximum chunk size, hundreds of bytes are wasted for each small allocation.

In fact, you’ll typically waste (max_size - average_size) per task — which is a pretty high price to pay if you have only one very large task. Very often, most of the tasks use a small amount of memory (say, around 32 bytes each), so you can use that to your advantage.

A better strategy is to split your allocations into two pools, one small pool for the average allocation, and a large pool for everything else. To figure out the best small pool size to use, try the following:

  • Collect a list of all your tasks sizes and their frequency of use by logging all the memory allocations.

  • Plot a graph of your allocations per-size, and see where you have the peak (typically around the median).

  • Pick a chunk size for the small pool that covers the majority of your small allocations, like twice the median size.

You could solve this as an optimization problem to work out precisely which size saves you the most memory! But doing it by hand will allow you to use a sensible size of chunk (e.g. multiple of 4), which you can set as a guideline for all task allocations.

Later, you can even introduce more pools with multiple chunk sizes if necessary, but watch out as this can also waste memory as certain pool become rarely used. (Fewer pools is more flexible, and you don’t have to worry too much about the total pool size). So two-three chunk sizes is typically sufficient.

Once you have this in place, your memory usage will drop drastically! Do you have any strategies that you use for memory pooling? Share them in the comments.

Discussion 1 Comments

gware on June 22nd, 2007

"Modern C++ Design, Generic Programming and Design Patterns Applied" by Andrei Alexandrescu has a very good chapter on small objects allocators. It's a good start for those who want to write their own pool in C++ (and aren't afraid of template programming). I think a good thing is to have : - a pool for small objects - a pool for medium objects - all other allocation go through the main system allocator - only one entry point for all allocs Also, be careful not to loose your focus on AI and waste too much time on your allocator (unless it's really necessary) ;)

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!