Mark-and-Sweep

The algorithm operates in two strictly sequential, non-interleaved phases:

• Mark Phase: Starting from a set of root references (e.g., global variables, active stack frames), the collector traverses the entire object graph, marking every reachable object as 'alive'.
• Sweep Phase: The collector linearly scans the entire heap. Any object not marked during the previous phase is deemed unreachable garbage. Its memory is reclaimed and added to a free list for future allocations. This clear separation simplifies implementation but introduces a stop-the-world pause, as all mutator (application) threads must be halted to ensure a consistent view of the object graph.

A key strength of mark-and-sweep is its ability to correctly collect cyclic reference structures, which are fatal to simple reference-counting collectors.

• In a cycle (e.g., Object A references Object B, which references Object A), reference counts never drop to zero even if the cycle is unreachable from the roots.
• Because mark-and-sweep uses graph reachability from external roots as its liveness criterion, it correctly identifies the entire cycle as garbage if no root points to it. The collector will fail to mark any object in the cycle and the sweep phase will reclaim all their memory.

A major drawback is the potential for memory fragmentation. Since objects are reclaimed in-place during the sweep, free memory becomes scattered in gaps between live objects.

• This external fragmentation can lead to allocation failures even when total free memory is sufficient, as no single contiguous block may be large enough for a new allocation.
• Mitigation strategies include compacting collectors (like mark-compact) that relocate live objects after sweeping to consolidate free space, or sophisticated free list allocators that can coalesce adjacent free blocks.

The time and space complexity of the algorithm is defined by its phases:

• Time Complexity: O(L + H) where L is the number of live objects (traversed during mark) and H is the total size of the heap (scanned during sweep). Performance degrades as heap size grows.
• Space Complexity: Requires auxiliary space for the mark bits. Typically, a dedicated bit (the 'mark bit') is stored in the object header or in a separate mark bitmap. This overhead is minimal but non-zero. The pause time is proportional to the heap size, not the amount of garbage, making it less suitable for real-time systems without modifications.

Mark-and-sweep is the archetypal tracing garbage collector. Its core principle—determining liveness by tracing references from roots—underpins most modern GC algorithms.

• Generational Collectors (like in Java's G1, ZGC) use mark-and-sweep (or mark-compact) for old generation collection.
• Incremental and Concurrent variants (e.g., Tri-color marking) were developed to reduce its long pause times by interleaving marking/sweeping with mutator execution.
• It contrasts with direct collectors like reference counting, which track liveness per-object without a global tracing phase.

In agentic memory management, mark-and-sweep principles inform context window eviction and long-term memory pruning.

• Episodic Buffer Cleanup: An agent's short-term working memory (e.g., a conversation buffer) can be viewed as a heap. Unreachable intermediate thoughts or deprecated tool call results are 'garbage'.
• Vector Store Maintenance: In a vector database backing agent memory, old, irrelevant, or low-quality embeddings that are no longer linked to any active agent context or knowledge graph entity can be identified (marked) via metadata and swept (deleted) in batch jobs to manage storage costs and retrieval performance.

Garbage collection (GC) is the overarching automatic memory management process of which mark-and-sweep is a specific algorithm. It identifies memory occupied by objects that are no longer reachable or in use by the program and reclaims it for future allocations. GC aims to prevent memory leaks and manual memory management errors.

• Tracing vs. Reference Counting: Mark-and-sweep is a tracing collector, following object graphs. An alternative is reference counting, which tracks the number of references to each object.
• Generational Hypothesis: Most modern GCs (like in Java's JVM) are generational, based on the observation that most objects die young. They segregate objects by age to optimize collection frequency and method.

A cache eviction policy is a predetermined algorithm that determines which items to remove from a finite cache when it reaches capacity. While mark-and-sweep reclaims unreachable heap objects, eviction policies remove reachable but less valuable cached data to make space.

• LRU (Least Recently Used): Evicts the item not accessed for the longest time.
• LFU (Least Frequently Used): Evicts the item with the lowest access count.
• TTL (Time-To-Live): Evicts items after a fixed expiration period.
• ARC (Adaptive Replacement Cache): Dynamically balances between LRU and LFU strategies.

Memory fragmentation is a condition where free memory is broken into small, non-contiguous blocks, preventing allocation of larger objects despite sufficient total free space. The sweep phase of mark-and-sweep can contribute to external fragmentation by leaving gaps of freed memory.

• Internal vs. External: Internal fragmentation is wasted space within an allocated block (e.g., due to size rounding). External fragmentation is wasted space between allocated blocks.
• Compaction: A common solution is a compacting garbage collector, which moves all live objects to one end of the heap after marking, eliminating fragmentation and improving allocation speed.

Reference counting is an alternative automatic memory management technique to trace-based garbage collection like mark-and-sweep. Each object stores a count of the number of references to it; when this count reaches zero, the object's memory is immediately reclaimed.

• Pros: Immediate reclamation, predictable pause times.
• Cons: Cannot detect cyclic references (e.g., object A references B, and B references A), which leads to memory leaks unless supplemented with a cycle detector. Overhead on every assignment operation.
• Use Cases: Used in file systems, COM, Objective-C (with manual cycle breaking), and Python (CPython uses reference counting with a cycle-detecting GC as a backup).

A stop-the-world pause is a period during which all application threads are halted so the garbage collector can safely perform operations like marking the object graph. The classic mark-and-sweep algorithm requires such a pause, making it unsuitable for real-time systems.

• Impact: Causes latency spikes and jitter in responsive applications.
• Solutions: Modern collectors use techniques like tri-color marking and incremental or concurrent collection (e.g., Java's G1, ZGC, Shenandoah) to perform most GC work concurrently with application threads, drastically reducing pause times.

The root set is the collection of starting points from which the garbage collector begins tracing reachable objects in the mark phase. If an object is not reachable from any root, it is considered garbage.

• Typical Roots: Include global variables, active stack frames (local variables), CPU registers, and static fields.
• Precise vs. Conservative: A precise GC has exact knowledge of what is a pointer in the root set. A conservative GC (like Boehm GC) treats any word that looks like a pointer as a root, which can cause retention of some garbage but is easier to integrate with languages like C/C++.