In my previous post I spoke about that basics I believe you should add to your allocator to aid development. I didn’t touch on any of the more advanced features, so I am going to do that now. Unlike the basics, advanced features can affect the running of the allocator. Their use often means consuming more memory and/or CPU time that may result in slight differences compared to using the vanilla allocator.
The advanced list
1. Unique id’s, names and callstacks. If possible give each memory operation (allocation or free) a unique id to help with debugging. Additional information such as a small piece of unique text with each operation can help locate where it came from and what it was used for. I prefer to store a small string with each while others like to store a pointer to __FILE__/__FUNCTION and __LINE__. Callstacks can also be captured. They have some great upsides for tracking purposes but platform and compiler issues can cause problems. MSVC can make it impossible to capture these without omitting frame pointers in optimised builds.
2. Buffer overrun detection. This one is fairly simple to add depending on how the allocator works and/or the area of memory. By adding a few markers around each operation you can detect if the memory has been corrupted by checking if these values have changed. Combined with the previous point these can uncover previously time consuming bugs in a matter of moments.
3. Dangling pointer detection. What buffer overrun detection doesn’t pickup is when you have freed some memory and something else happens to be still using the pointer. It can become seriously problematic when a block of memory is freed and reused by something else. Anything still using that pointer is going to trample all over that memory and cause crashes or worse (oddly for this situation), random runtime corruption.
4. Heaps and pools. Adding the ability to have multiple heaps that can be allocated into individually can help with both fragmentation and budgeting. For example, if you have one area of your game that performs lots of operations it can cause fragmentation problems when mixed with operations from other areas. Giving this area of your game its own heap contains these operations within a certain region. This prevents the other regions of memory from becoming polluted. It is not a fool proof method by any means, but it can save your ass in a pinch. Pools or fixed lists, as they are often called can also be extremely beneficial in this area. A good, practical pool article was written by Simon Yeung for his iPhone Game Engine a couple of weeks ago here.
One additional advantage is that you can also set heaps up for use on memory areas that are not directly supported by the platform vender. For example, VRAM on the PS3 requires you to manage memory yourself.
The downsides to advanced features
There is a problem with some of the more advanced techniques. They consume memory and increase execution time. Though this may seem a trivial problem for debug builds it can be enough to cause existing problems to vanish into thin air. The tracking information, especially buffer overrun sentinels may have to be placed with the memory allocated. This will increase size and potentially change the location of the allocation.
Personally, I favour storing all of the advanced information with each allocation rather than in a separate location. If experience has taught me anything, it is that this makes it easier for me to see the immediate surrounding memory in memory view windows, what it was used for and where it might be a good place to start looking. Buffer overruns typically occur regardless of memory arrangement. Any dangling pointer problems tend to move around based on the execution time so placement in other locations makes little difference in a lot of situations. These rules are not perfect but are a good jumping off point.
Tools
There are many tools available that you can use to find errors. Their use however is dictated somewhat by what platform you are working on. Valgrind and Boundschecker are common PC tools but may not be suited for games depending on the situation. I have used Excel (or equivalent) successfully with the added logging information more times than I can count. The advantage is that this is platform independent and free if using software like OpenOffice. A custom tool can also be written, it is hard wading through many, many allocations in a spread sheet.
For static memory don’t forget to check the MAP file generated by the linker. You will be surprised how much memory can go missing with global variables.
Summary
A good custom allocator will provide a solid foundation for any project. With the right additions you have the ability to track bugs quickly and easily. This is especially important if you work on multiple platforms at the same time and don’t have the tools available, like you do on the PC.
If you fancy giving our allocator, Elephant a go visit www.juryrigsoftware.com. We welcome feedback and what areas to improve on for future revisions.