OH4 - memory allocators

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:

Temporal knowledge - Knowledge about the order or lifetime of your allocations and deallocations.
Spatial knowledge - Knowledge about the range of sizes or total space needed.

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 known	Alloc size known	Total lifetime known	Alloc lifetime known
Arena	yes	no	yes	no
Stack/Queue	yes	no	no	yes
Pool	no	yes	no	no
Heap	no	no	no	no

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:

Arena = Array
Stack/Queue = Stack/Queue
Pool = Linked List
Heap = Hash Map

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:

Add integer guards at the start and/or end of allocations (in buffer "redzones")
Overwrite freed memory with a bit pattern
Fill uninitialized memory with a bit pattern
Add guard pages between allocations
Decommit and don't reuse free virtual pages
On free, don't reallocate the last N free'd pages, instead put them in a FIFO. Items in the FIFO are overwritten with a bit pattern and periodically scanned for corruption.

Terms

Static allocator - An allocator that partitions a single fixed-size chunk of memory and cannot grow that chunk.
Dynamic allocator (a.k.a. Growable allocator) - An allocator that partitions multiple chunks of memory and can retrieve more chunks as needed.
Arena allocator (a.k.a. Linear allocator, Bump allocator) - Static allocator. Allocates linearly. No fine-grained deallocation, only the option to deallocate everything.
Stack/Queue allocator (a.k.a. LIFO/FIFO allocator) - Static allocator. Allocates linearly. Offers fine-grained deallocation but it must be performed in LIFO/FIFO order.
Pool allocator (a.k.a. Fixed size allocator) - Dynamic allocator. Allocates and deallocates objects of a single fixed size in any order.
Heap allocator (a.k.a. General purpose allocator) - Dynamic allocator. Allocates and deallocates arbitrary sized objects in any order.

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