null program

14 Sep 2007

Memory Allocation Pool

I wrote this code and writeup some time ago and have used it in several projects for building parse trees quickly. Using the pool is faster than making a system call with malloc each time you add a new node. In fact, one of my programs ran 25% faster when I dropped in the this memory allocation pool. This code is very solid and reliable.

Download the code (GPL licensed) at download/alloc-pool.tar.gz (2.58KB).

I read about memory allocation pools in the Subversion manual and decided to write one for fun. So here it is. Included is a small driver I ran over night to test for memory leaks. lint will complain about memory leaks on this code, however. I also added thread safety, but I don't suggest you use it.

A memory allocation pool is good for speeding up a program that needs to make many small memory requests quickly (many system calls). Instead, one system call is made in place of many.

It is also useful for semi-automatic memory management. Let's say you build some large tree structure somewhere in your program. If you want to free all this memory used by the tree, you will need to traverse it to take it down. This takes time and code. If you use a memory pool, you can free all of the memory at once by freeing the entire memory pool.

The pool works by allocating a large chunk of memory and dishes it out as requested (a subpool). If a request is too large to take out of the current chunk, it allocates another chunk twice as large as the previous one (another subpool). This doubling allows the pool to quickly scale up to whatever size is needed. Memory will still be allocated from the old pool until that pool has too many misses in a row (hard coded to 10 in my sources). Once this happens, the subpool remains untouched and your pool will have some slight internal fragmentation.

[] permanent link

Don't stop here! This isn't everything. Check out the archives (on the left) for more posts. Or just have a look at the index.