Research into memory allocation strategies

Every software application must deal either implicitly or explicitly with memory allocation. While higher-level languages often tout the ability to ignore this concern, truly performant software must eventually wrestle with its memory allocation needs.

Most programming language runtimes aim to provide a good general purpose allocator to their users. However, this generality is purchased at a cost and in cases where you know more about your specific allocation patterns and believe there is extra performance to be gained by exploiting this knowledge, it may make sense to use a purpose-built allocator.

There are two types of knowledge about your allocations that you might use to boost performance:

If you posses one or both of these types of knowledge about your allocations you are likely in a position to explore a custom allocator. For example:

If exact size and lifetime are known (ex. loading a file): Pre-allocate for the known size and free data at the end of its lifetime.

If maximum size and total lifetime are known (ex. data for a single frame): Pre-allocate maximum expected space. No need to do fine-grained freeing, just free everything at the end of the scope.

If maximum size is unknown, allocation size is fixed, and lifetime is unknown (ex. game entities): Use pool allocation and maintain a free-list for allocating new items. No need to coalesce blocks or store sizing metadata.

If maximum size and allocation order but not lifetime is known (ex. work queue): Pre-allocate a large chunk and allocate from it in order, no need to coalesce free chunks.

Below is a general table of which kinds of allocation strategies may fit which kinds of knowledge. Total space known means you know your maximum space requirements. Alloc size known means you know the size (or range of sizes) of allocations. Total lifetime known means you know a priori a point in time (not the end of the program) when all the data is no longer needed. Alloc lifetime known means you know a priori a point in time when specific allocations are no longer known.:

 Total space knownAlloc size knownTotal lifetime knownAlloc lifetime known

This is by no means an exhaustive list and within each type of allocator there remain many variations of design possible. For example, if you know a range of sizes you might have a Pool allocator with sub-pools for each size.

If you squint, you will notice a pretty close correspondence between these allocation strategies and common abstract data types:

Detecting memory corruption

One advantage of writing a custom allocator is the ability to add more sophisticated memory corruption detection. The following is a short list of memory corruption detection methods:


Last update on 7E7204, edited 1 times. 3/3thh