A memory allocator generally refers to libraries that provisions memory for the user. In general, this will refer to heap memory.
Stack allocation
This is done at compile-time and is nearly always faster and simpler than dynamic heap allocation. Stack allocation is done by the compiler with the equivalent of LLVM’s alloca instruction (typically via moving the stack pointer). The compiler will internally insert alloca calls where necessary (including in LLVM).
Heap allocation
A major problem is heap allocation, done at runtime. For a single allocation, allocators need to track a few key details:1
- How much memory is requested by the user
- Whether this chunk is free or allocated
- Where the next and previous chunks are
- Thread ownership information
- Debugging metadata for debug builds
3 general heap allocation strategies
- best fit: choose smallest block that can satisfy request
- need to search through entire list
- tends to leave very large holds and very small holes
- small holes probably useless
- worst fit: choose largest block (most leftover space for future requests)
- also needs to search through entire list
- simulation says worst in terms of storage utilisation
- first fit: find first block that satisfies request
- tends to leave average sized holes
Fragmentation
One big goal of allocators is to avoid fragmentation. Since we allocate in contiguous blocks, and we can’t move memory around after allocation (for the programmer’s sanity), we get fragments: small contiguous blocks of memory that can’t handle allocation (like a “hole” in memory). There are three requirements for fragmentation:
- Different allocation lifetimes
- Different allocation sizes
- Inability to relocate previous allocations
One way allocators can avoid fragmentation is by keeping track of free blocks of memory by chaining them together with a linked list. For allocation, we choose a block large enough for the request and remove from the free list. For deallocation, we add the block to back to the free list. If it’s adjacent to another free block, we merge them.