To turn our alocator from Videos: Memory Allocation into a realistic allocator, we need to improve performance in terms of both utilization and throughput.
- To improve our allocator’s performance, we first consider first-fit (allocate in the first suitable block that we find) vs. best-fit (allocate in the most suitable block among all available) allocation strategies.
- Instead of a 16-byte header and footer, we can use less overhead and reduce internal fragmentation through a more compact representation of size and allocation information.
- Changing the header and footer representation has implications for preserving allocation alignment. Fortunately, the issues are easily manageable.
- A more complex encoding can take advantage of the fact that the footer’s size information is not needed for allocated blocks if we push some allocation information into adjacent blocks. Production allocators are full of tricks like this.
- Keeping an explicit list of unallocated blocks can greatly improve the throughput of our allocator.
- Further improvements are possible by using other data structures to keep track of unallocated blocks. such as using a balanced binary tree to support best-fit allocation.
- To build on mmap instead of sbrk, our allocator must adapt to working with discontiguous chunks of memory.
- We have pursued a particular style of allocator in detail, but completely different approaches are also found in the wild. Here’s one of them.