Memory Management

Background

• General purpose functions
• Hidden behavior (and you thought that was a good thing!)
• Inadequate capabilities

• generate statistics
• control/simulate memory usage
• provide extensive debugging and error detection
• implement virtual memory, heap defrag
• tweak memory management to suit your application

• Ease of Use
• Performance
• Memory Overhead
• Fragmentation
• Debugging

Ease of Use

• Pointers vs. Handles (opaque pointers)
• Complexity to implement and for users
• Garbage collection, coalescing/compacting memory

Performance

• Speed and consistency (when to do GC, compaction)
• Allocation/deallocation policies (best fit, worst fit, next fit, first fit, LIFO/FIFO, etc.)
• Spatial coherence and locality of reference (cache mechanisms, write-back/write-through)
• Virtual memory (disk-based memory), disk buffers (read-ahead, read-behind)
• Recycling

Memory Overhead

• The memory manager requires memory
• Each block requires (accounting) overhead (small vs. large)
• Variable block sizes vs. fixed block size

Fragmentation Control

• Happens randomly over time (not stack or queue-like)
• Usually responsible for "Insufficient Memory" problems
• Allocation policies (e.g. best fit, first fit)
• Fixed vs. variable size
• Lifetime of blocks (programmer knowledge)
• Number of free blocks vs. amount of free memory
• Multiple heaps (size-based, lifetime based)
• Coalescing (merging adjacent free blocks)
• Pointers vs. Handles for compacting memory (PDF)
• Fragmentation vs. performance

Debugging Capabilities

• Audit memory usage patterns and statistics
• Consistency checking (memory corruption, heap validation)
• Initializing blocks to certain values (free/allocated/deallocated)
• Invalid memory block detection (allocate/deallocate)
• Memory leak checking

Self-check:
1. What's the difference between a pointer and a handle?
2. What is the benefit of locality of reference?
3. What is the benefit of having fixed-size blocks?
4. What is the drawback of having fixed-size blocks?

Automatic Memory Management

• a.k.a. Garbage Collectors
• Advantages:
  • Programmer doesn't worry about MM (memory management)
  • Code is cleaner (GC has responsibility for MM)
  • Bugs related to MM are far less
  • GC is generally superior to hand-coded MM
• Disadvantages:
  • Sometimes memory that is no longer needed is not released
  • Depending on the implementation, the programmer can't control when GC occurs
  • Generally needs to be built into the language (e.g. BASIC, C#, Java, Javascript, Lisp, Perl, Python, PHP, Ruby, Smalltalk)
  • C/C++ is conspicuously absent, but there is a solution in the Boehm Garbage Collector
• When is it collected?
  • immediately
  • as-needed
  • idle
  • continuously
  • programmatically
• Tracing Collectors
  • Mark-and-sweep (scan entire memory, can't be interrupted, compact live blocks)
  • Copying (requires extra memory, fixes fragmentation and locality of reference)
  • Incremental (recover at intervals, no large pauses, program cooperates)
  • Conservative (for languages without built-in GC, assumes what a pointer is)
  • Generational (new objects are reclaimed before old ones)
• Reference Counting
  • Easy to implement
  • Counting is not free
  • Circular reference problem
• GC has matured over the years (it's been around since about 1958)
• People devote careers to the topic