Introduction to Allocators
This post is intended for programmers who aren't particularly familiar with various memory management techniques and have some basic experience in low level environments, such as C. For such lower level programming languages, manually allocating and freeing memory may be daunting to some programmers as it can be easy to make mistakes, like in a complicated data structure. This may drive them to use a higher level language, where allocating memory is simple and there is no need to free the memory as the runtime is garbage collected, which may be convenient, but hinders performance in both apparent and subtle ways.
Instead of manually allocating and freeing every chunk of memory, using alternative allocators can both improve performance and convenience compared to standard dynamic allocation, making low level programming more approachable. These alternative allocators aren’t as flexible as a dynamic allocator such as malloc, but that tradeoff is often worth it. I believe it is worth getting acquainted with a few simple allocators, as well as some examples as to where they might be useful and preferable to a standard dynamic allocator. Lifetimes
The lifetime of a particular chunk of memory is the time between its allocation and freeing. Malloc is flexible as it allows every chunk of memory to exhibit its own lifetime. Therefore every invocation of a dynamic allocator would imply that that memory has a lifetime independent of the other allocations, right? Identifying patterns in lifetimes between allocations informs the programmer about which allocator they should use, which very well may not be a dynamic allocator.
Complicated lifetimes require complicated allocators
Arena
While labeling something an allocator may make it sound official, an allocator is just something that controls memory, lending it out to tasks that request it, and reclaiming it. Arena allocators are one of the simplest allocators as they only have two associated functions: allocating some memory, and freeing all of the allocator’s memory (no partial freeing). The Arena controls a large stretch of contiguous memory, basically just an array of bytes. While this post does not cover implementation as that can be found elsewhere (https://www.gingerbill.org/article/2019/02/08/memory-allocation-strategies-002/), both of these actions are simple to implement and very fast to execute.
In a game engine I developed, there was an Arena dedicated for data that could only last one frame. At the end of each frame, the Arena was reset back to the beginning. Even though allocations that used this Arena often did not have to last until the end of the frame, they did anyways. While this approach may be more wasteful in terms of raw memory usage as allocations aren't freed in the middle of a frame, memory leaks were no longer possible between frames.
Because the memory an Arena manages is contiguous, the capacity of the Arena is generally determined when it is created. Oftentimes one doesn't know how much memory a particular task will need beforehand, so a safe route would be to make the Arena exceedingly large, so that no reasonable workload would overallocate. This may seem wasteful, as tons of memory is being allocated for the Arena but isn't used. However, because of how virtual memory works, usually allocations from the OS (i.e. VirtualAlloc, mmap) simply reserve ranges in the virtual address space your process uses, and only maps the addresses to physical memory when necessary. This means that one can allocate huge chunks of memory, but only pay for what you need, so to speak. This allows for Arenas to be huge in capacity, but still efficient in memory usage.
Stack
The call stack (often referred to as just the “stack”, but I will refer to it as the “call stack” for clarity) works similarly to an Arena as large portions of memory are freed at the same time because the lifetimes of the memory are the same. However it is able to do so at a finer granularity, only freeing memory associated with a particular function call. Modifying the Arena allocator to allow partial freeing only from the end of the Arena adds the flexibility that the call stack has. This allows for fast and easy memory reuse, assuming your allocation pattern matches accordingly.
Works similarly to the call stack
Free List
Arena allocators may not be suited for many allocations with differing lifetimes, and thus more flexibility is required. Free Lists work very similarly to a dynamic allocator as they require explicit allocation and freeing, but are easy to implement and often more performant. A caveat to this allocator is that all the allocations need to be of the same size.
Free Lists work by using any free chunks of memory the allocator has to maintain a linked list which keeps track of the free chunks of memory. So while the Arena manages an array of memory, a Free List manages a linked list of memory. Allocation works by returning the head of the linked list, and making the new head of the list equal to the next element. Freeing memory involves storing the current head of the list in the newly freed memory, then setting the head of the list to the newly freed memory. These operations are very simple and are essentially push and pop with a linked list. More about the implementation can be read here (https://www.gingerbill.org/article/2019/02/16/memory-allocation-strategies-004/).
Convince yourself of this
Composition
Allocators can be nested within each other for more complicated behavior. One such example would be in a game where entities need to be stored. When a new entity needs to get allocated and the Free List is empty, such as at the beginning of a level in the game, memory is allocated from an Arena allocator. The Free List now is able to manage this newly allocated memory. This allows the Free List to reuse memory dynamically as entities are created and destroyed, as well as get new memory if it runs out. Then when the level needs to be unloaded, the Arena resets, resetting the Free List along with it.
So hopefully this small introduction has eased you into the idea that analyzing the patterns of memory allocations and familiarizing yourself with several allocators, or creating your own, can increase performance and alleviate some of the pains that may arise from using the wrong allocator and low level programming in general.