Introduction

Using replacements for the standard memory allocators, can seem a bit scary. But memory allocation is at the heart of programming and can easily be the most fundermental issue effecting program operation.

There are several issues involved in memory allocation:

Speed
Fragmentation
Overhead
Thread Safety
Class specific allocators

Memory Allocation Speed

Perhaps the main point for most people, memory allocators must retain some form of map of what memory they have allocated and what has been freed so that they can return unallocated space on a request to malloc. There are any number of strategies for doing this, and we provide some references to custom allocators at the end of this article. Most memory allocators will use a system of "bins" each bin being used to store blocks in a certain size range.

Memory Allocation Fragmentation

When memory is allocated and freed as an application is running, spaces inevitably develop in the memory map, where memory has been freed and not reallocated. It is tempting to assume that the space wasted is marginal, but in many real life examples, the wastage can be massive in some cases exceeding 100%. In programs consuming large amounts of memory this will have a horrendus impact upon performance.

Memory Allocation Overhead

Each time you allocate memory, you incur an overhead over and above the amount you actually allocate. At a minimum this is likely to be 8 bytes, 4 bytes being a pointer to the next allocated block, and 4 bytes for the amount of memory allocated. Though having said that many allocators will have special routines for small block allocation which may reduce this overhead.

If you consider the case where you have a great number of small allocations to make, then this overhead can be very large. This is one of the scenarios when use of a custom allocator should be considered.

Memory Allocation Thread Safety

If you are writing single threaded code, then you do not need to worry about choosing an allocator which is thread safe. If you are using threads then you can still easily port custom allocators, by using critical sections to ensure thread safety.

Class Specific Allocators

This in many ways is the crux of the matter. In common with most issues of optimisation, where it does tend to be the case that one small section of the code takes up most of the time. It is likely that most memory issues can be sorted with just a few custom allocators. A custom allocator for a class has several benefits.

Speed, as it only has to allocate one size it can be very fast.
Low overhead, as it does not need to keep track of allocation size.
Potential for garbage collection. You can program so as to start allocation pools, that can be released in a single call, assuming that no class members allocate memory themselves.

For examples we present some non standard allocations being used in MarsJupiter projects.

Our simple non standard allocator

For a non standard allocator to offer real benefits, you need to consider just what special features your usage of a class gives you to work with? The simple lack of the need to store the size of each allocation whilst also tightly packing the allocations has real benefits when allocating lots of small blocks, but this benefit is less proportionally with bigger blocks. For example for one of the marsjupiter classes, we know that the pattern of allocation is to start with no allocation, followed by loads of allocations with only the odd free, and then to clear all the allocated space. This removes the need for a "free list" and hence gives real benefit.

Replacement Malloc

Given the notable inefficiencies of the standard malloc it may be desirable to replace malloc with you own code, if your compiling under unix, then a simple internet search will provide you with plenty of possibilities. Under windows with Visual C++ and MFC you will struggle to find drop in replacements, if you do know of any, please let us know.

We have ported quick fit malloc (see references) and made if thread safe and are currently experimenting with it, initial results on some simple benchmarks showed a 10% increase in speed. A 10% speed up is quite remarkable, and we look forward to reporting more real life results, since benchmark tests unless cleverly designed to make life difficult for malloc can all to easily simply "fit a niche" with a particular implementation making it look better than it really is.