Cheney Algorithm

The Cheney algorithm is a classic garbage collection technique used in memory management for programming languages with automatic memory allocation. It is a type of copying garbage collector that uses a breadth-first traversal to reclaim unused memory.

How It Works

1. Memory Division
   The heap is divided into two equal-sized regions:

   • From-space: Where objects are currently allocated.
   • To-space: An empty region used during collection.

2. Root Set Identification
   The algorithm starts by identifying all root references (e.g., global variables, stack variables).

3. Copying Live Objects

   • All objects reachable from the root set are copied from the from-space to the to-space.
   • As each object is copied, its references are updated to point to the new location in the to-space.
   • A forwarding pointer is left in the old location to avoid duplicating objects.

4. Breadth-First Traversal

   • Cheney’s algorithm uses two pointers in the to-space:
     • Scan pointer: Points to the next object whose references need to be updated.
     • Free pointer: Points to the next free space in the to-space.
   • The scan pointer advances through the to-space, copying any referenced objects not yet moved.

5. Swap Spaces

   • Once all reachable objects are copied, the roles of from-space and to-space are swapped.
   • The old from-space (now containing only garbage) is cleared and becomes the new to-space.

Advantages

• No Fragmentation: Objects are packed together in memory, eliminating fragmentation.
• Simple Allocation: Allocation is just a pointer increment in the to-space.
• Efficient for Short-Lived Objects: Works well in environments where most objects die young.

Disadvantages

• Requires Double Memory: Needs two memory regions of equal size.
• All Objects Moved: Every live object is copied during each collection cycle.