Videos: More on Memory Allocation

To turn our alocator from Videos: Memory Allocation into a realistic allocator, we need to improve performance in terms of both utilization and throughput.

• Malloc 14: Improving performance and first-fit vs. best-fit   2:57
  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.

• Malloc 15: Packing headers to reduce internal fragmentation   4:49
  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.

• Malloc 16: Header/footer sizes and alignment   2:02
  Changing the header and footer representation has implications for preserving allocation alignment. Fortunately, the issues are easily manageable.

• Malloc 17: Avoiding footers in allocated blocks   2:08
  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.

• Malloc 18: Explicit free lists   4:36
  Keeping an explicit list of unallocated blocks can greatly improve the throughput of our allocator.

• Malloc 19: Alternative free-list representations   2:32
  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.

• Malloc 20: Adapting an allocator to mmap   2:43
  To build on mmap instead of sbrk, our allocator must adapt to working with discontiguous chunks of memory.

• Malloc 21: Segregated allocation   2:32
  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.