in general: stack allocation at compile-time is faster/simpler than dynamic heap allocation
stack allocation is done by the compiler with alloca calls
compiler internally inserts alloca calls (incl in LLVM)
allocators want to avoid Fragmentation they do this by keeping track of free blocks of memory by chaining them together with a linked list need to be able to handle a request of any size for allocation, choose block large enough for request, remove from free list for deallocation, we add block to back to free list. if adjacent to another free block, we merge them
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
kernel has to implement its own memory allocations
Sub-pages
- Dynamic memory allocation (
malloc,free) - Arena allocator
- C/C++ allocation mechanisms