What is an allocator
Allocation are always a source of worries for performances when they are done in the critical path of an application. In C++ they are often hidden behind a class that uses some kind of container, that uses some kind of allocator. All of these may not be well optimized and do some kind of allocation.
Allocating usually means giving the hand back to the operating system to ask it for usable memory. When we do so, we don’t know what it is doing. Maybe it will be fast, maybe not. Maybe it will preempt our thread prematurely leading to excessive lag.
To avoid this, it is fairly common to use some kind of allocator that avoid, at most, to ask the OS for memory. And root all allocation to this allocator (replacing malloc, new, etc with allocator_malloc, allocator_new etc).
Goal
General purpose allocator are already used in production by performance critic application such as servers & co.
I heard about it I used mimalloc in the game industry. This library is built mainly for big servers with multiple numa nodes and with a lot of available memory. It is one of the most used at this point but it has its flaws that lead me to build my own library.
There is also multiple other libraries such as jemalloc that inspired my project at some point.
My original goal was to research and build an allocator that would be a perfect match of these libraries and the world of gaming platforms (low memory footprint).
Implementation
My idea was “simple”, take what I thought was smart about mimalloc and jemalloc and merge it together.
Allocation size differentiation
Allocation are split between 3 categories : Small, medium, large.
- Small allocations are allocations that are smaller than a threshold (256 bytes).
- Large allocations are allocations that are bigger than a threshold (1+ mega-byte)
- Medium allocations are allocations in between.
All allocations are rooted to a different style of allocator called “arena”. Each arena allocates and manages its memory. There are optimizations done specifically for all of these types.
Metadata storage
When an allocation is done, the library gives back a pointer (malloc style). It is impossible to store metadata within this pointer as it will be used by the application. So we need to be smart about how we store metadata.
In mimalloc & redallocator, we create arena at a specific alignment that allows us to do something like :
void* ptr = red_alloc(10); // Allocate 10 bytes
memset(ptr, 0, 10); // use the bytes
red_free(ptr); // <- how do it work ?
// Pseudo code, multithreading stuff excluded:
void red_malloc(size_t size)
{
// arena ptr will be aligned on ARENA_ALIGNMENT that is a big number (above arena_max_size)
red_arena* arena;
if(need_new_arena)
{
arena = aligned_alloc(arena_max_size, ARENA_ALIGNMENT);
}
else
{
arena = red_get_old_arena(),
}
return red_arena_alloc(arena, size);
}
void red_free(void* ptr)
{
// The ptr we gave was allocated from a memory that starts at a specific alignment.
red_arena* = align_ptr_down(ptr, ARENA_ALIGNMENT);
red_arena_free(arena, ptr);
}
Multithreading
The library is built around multithreading and and avoiding concurrency between threads. Each thread owns its memory and data structures. It simplifies the mental model of the allocation and reduces the number of mutex used.
This adds some complexity to the code :
- Thread A can’t allocate when Thread B free memory that was previously allocated by Thread A.
- Thread A & B need to be able to allocate and free independently.
- Thead A exits but didn’t free all of its memory
To resolve these issues, I have a clear structure of code using thead_local variables to ensure the ownership of the data used.
- Small arena allocates using atomic bitmaps.
- Medium arena uses intrusive linked-list and mutexes
- Large arena are totally independent
When a thread exits, the arena that remains still in use (with a ptr that is not freed) are added to a linked list of orphans arenas that are adopted by one of the thread when it goes inside the library code path.