For 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.
The lifetime of a particular chunk of memory is the time between its allocation and free. 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 allocators are one of the most simple allocators as they only have two associated functions: allocating some memory, and freeing all the allocator’s memory (no partial freeing). While this post does not cover implementation as that can be found elsewhere, both of these actions are simple to implement and very fast to execute.
One common situation is that memory is needed for a particular task, and once that task is finished, all the memory should be freed. In this case the lifetimes of all the memory associated with that task are okay to end at task completion. An arena allocator would lend itself well here instead to a dynamic one. All of the allocations would be performed similarly to before, and freeing is no longer necessary except at the at of the task, where the entire arena can be freed at once. With an arena allocator, allocations are fast, and freeing is much simpler.
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.
Works similarly to the call stack
Arena allocators may not be suited for many allocations with differing lifetimes, and thus more flexibility is required. Free lists work 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. 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 therefore fast to execute, more about the implementation can be read here.
Convince yourself of this
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 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.
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.