Summary

Lecture 15 covers heap allocators, explaining their role in managing dynamic memory allocation via malloc, realloc, and free. It discusses the requirements and goals of heap allocators, including handling allocation/free sequences, tracking memory usage, and optimizing for throughput and memory utilization. The lecture then details three heap allocator implementation methods: Bump Allocator (focused on speed), Implicit Free List Allocator (using headers to track free/allocated blocks), and Explicit Free List Allocator (more efficient free block management). Finally, it briefly touches on compiler optimizations.

1. The Heap and Heap Allocators

  • The heap is a memory area that grows upwards, used for dynamic memory allocation.
  • Heap memory persists until explicitly freed, unlike stack memory.
  • A heap allocator manages heap memory by fulfilling allocation requests.
  • It receives a large memory block and divides it into smaller blocks for allocation.
  • Key functions:
    • malloc(size_t size): Allocates a block of at least size bytes.
    • free(void *ptr): Frees the allocated block at ptr.
    • realloc(void *ptr, size_t size): Resizes the allocated block at ptr.

2. Heap Allocator Requirements

  • Handle any sequence of allocate and free requests.
  • Track allocated and free memory regions.
  • Choose which free memory to use for allocation.
  • Respond to allocation requests immediately.
  • Return 8-byte aligned memory addresses.

3. Heap Allocator Goals

  • Maximize throughput (requests served per unit time).
  • Maximize memory utilization (efficient use of heap memory).
  • Fragmentation reduces utilization (unused memory that can’t fulfill requests).
  • Relocating allocated blocks is not allowed as it invalidates pointers.
  • Throughput and utilization can be conflicting goals.

4. Bump Allocator

  • A simple allocator that allocates the next available memory.
  • Free operations are no-ops.
  • High throughput, very poor utilization (no memory reuse).
  • Example:
    • malloc(4) allocates 4 bytes.
    • free() does nothing.
  • Illustrates the throughput vs. utilization trade-off.

5. Implicit Free List Allocator

  • Tracks allocated/free blocks using headers before each block.
  • Header stores block size and allocation status.
  • malloc searches for a free block and updates the header.
  • free updates the block’s header to mark it as free.
  • Improves utilization over Bump Allocator by reusing freed memory.

6. Explicit Free List Allocator

  • Uses a separate data structure (e.g., linked list) to track free blocks, improving efficiency of free block management.

7. Optimization

  • (Briefly mentioned)
  • Compiler optimizations can improve code efficiency.