Garbage Collection

A two-phase, non-moving algorithm that first marks all objects reachable from root pointers, then sweeps through the heap to reclaim memory from unmarked objects. It handles cyclic references but can cause heap fragmentation.

• Phases: Mark (trace reachability) → Sweep (collect unreachable).
• Advantage: Simple, handles reference cycles.
• Disadvantage: Causes stop-the-world pauses and memory fragmentation.
• Use Case: Foundational algorithm in early Java Virtual Machines (JVMs).

An optimization based on the weak generational hypothesis: most objects die young. The heap is divided into generations (e.g., Young and Old). Frequent, fast collections (minor GC) target the young generation. Objects that survive multiple collections are promoted to the old generation, which is collected less frequently via a major GC.

• Key Insight: Separates short-lived and long-lived objects.
• Performance: Dramatically reduces pause times for most collections.
• Implementation: Used in modern JVMs (HotSpot) and V8 JavaScript engine.

A moving algorithm that divides the heap into two equal-sized spaces: from-space and to-space. Allocation happens in from-space. When full, live objects are copied contiguously to to-space, compacting memory. The roles of the spaces are then swapped.

• Advantage: Eliminates fragmentation, allocation is a simple pointer bump.
• Disadvantage: Halves usable heap capacity.
• Complexity: Time proportional to the number of live objects.
• Typical Use: Often used for the young generation in a generational collector.

A direct, non-tracing method where each object stores a count of references to it. The count is incremented on new references and decremented when references are removed. When the count reaches zero, the object's memory is immediately reclaimed.

• Advantage: Memory is reclaimed incrementally, with predictable, short pauses.
• Critical Flaw: Cannot reclaim cyclic references (e.g., object A references B, and B references A) without additional mechanisms.
• Use Case: Common in file systems, COM, and early versions of Python (supplemented with a cycle detector).

This defines the fundamental strategy for identifying garbage.

• Tracing (Indirect): Starts from root references (globals, stack variables) and traverses the object graph to find all reachable objects. Anything unreachable is garbage. Used by Mark-and-Sweep and Copying collectors.
• Direct (Reference Counting): Each object tracks its own references. Garbage is identified locally when the count hits zero.

Trade-off: Tracing handles cycles naturally but can cause pauses. Reference counting has incremental reclamation but fails on cycles and has runtime overhead on every pointer assignment.

Advanced algorithms designed to minimize stop-the-world pauses by performing garbage collection work concurrently with the application's execution (mutator).

• Concurrent Mark-Sweep (CMS): Marks objects concurrently with the mutator, with brief pauses for initial marking and remarking.
• Garbage-First (G1): Partitions heap into regions, collecting regions with the most garbage first (garbage-first), aiming for predictable pause times.
• ZGC & Shenandoah: Ultra-low-pause collectors that perform most work concurrently, including relocation, with pause times often under 10ms.

These are essential for low-latency applications like financial trading or real-time data processing.

An algorithm that determines which items to remove from a finite cache when it reaches capacity. These policies are a higher-level, application-specific form of memory management, whereas garbage collection operates at the runtime level.

• Common Policies: Least Recently Used (LRU) evicts the oldest accessed item; Least Frequently Used (LFU) removes the least-often accessed item.
• Deterministic vs. Heuristic: Eviction policies are typically deterministic rules, while garbage collection uses heuristics (like reference counting or tracing) to identify unreachable objects.
• Application: Used in CPU caches, database buffers, and in-memory stores like Redis to manage working sets.

A type of resource leak that occurs when a computer program incorrectly manages memory allocations, failing to release memory that is no longer needed, causing gradual performance degradation or system failure.

• Cause in GC Systems: Even with garbage collection, leaks can occur if unintentional strong references are maintained (e.g., objects in long-lived caches, static collections, or event listeners).
• Contrast with Uncollected Garbage: A leak holds memory that is still reachable but logically unused. Garbage collection cannot reclaim it because the objects are not identified as garbage.
• Impact: Leads to increased memory footprint, frequent garbage collection cycles ('thrashing'), and ultimately OutOfMemoryError exceptions.

A simple garbage collection technique where each object stores a count of the number of references to it. The memory is reclaimed immediately when this count reaches zero.

• Mechanism: The runtime increments the count on assignment and decrements it when a reference goes out of scope or is reassigned.
• Pros & Cons: Offers predictable, immediate reclamation but cannot handle cyclic references (where objects reference each other but are otherwise unreachable).
• Usage: Employed in systems like CPython (for its primary GC) and in smart pointer implementations (e.g., std::shared_ptr in C++).

A class of algorithms that periodically identify garbage by tracing which objects are reachable from a set of root references (e.g., global variables, active stack frames). Any object not reached is considered garbage.

• Core Algorithms: Includes Mark-and-Sweep, Mark-Compact, and Copying Collection.
• Process: 1) Mark: Traverse the object graph from roots, marking live objects. 2) Sweep/Compact: Reclaim memory from unmarked objects, optionally compacting live objects to reduce fragmentation.
• Characteristics: Can handle cyclic references but typically introduces pause times ("stop-the-world") during collection cycles.

An optimization for tracing collectors based on the weak generational hypothesis: most objects die young. Memory is divided into generations (e.g., Young and Old).

• Young Generation (Nursery): Where new objects are allocated. Frequent, minor collections occur here, using a fast copying collection.
• Old Generation (Tenured): Objects that survive several young generation collections are promoted here. Collections are less frequent but more expensive.
• Benefit: Dramatically improves throughput by focusing effort where most garbage is created. Used in JVM HotSpot and .NET CLR.

A memory management scheme where the compiler inserts reference counting instructions (retain/release) at compile time, automating what would be manual reference counting.

• Key Difference from GC: Reclamation is deterministic and occurs at precise points in code execution, avoiding the unpredictable pause times of tracing collectors.
• Cycle Handling: Requires developers to break potential cycles using weak or unowned references, as the compiler cannot automatically resolve them.
• Primary Use: The default memory management model for Swift and Objective-C, optimized for low-latency systems.