Implementing Incremental Garbage Collection in Go

Go's garbage collector is a sophisticated piece of software responsible for automatically managing memory. While highly efficient, a "stop-the-world" (STW) pause during garbage collection can lead to latency spikes in responsive applications. This challenge asks you to explore a simplified model of incremental garbage collection, allowing the GC to run in smaller, more frequent cycles interleaved with program execution, thus reducing STW pause times.

Problem Description

Your task is to implement a simplified, user-space "incremental garbage collector" for a custom object model in Go. This is not about modifying the Go runtime itself but simulating the behavior of an incremental GC for a defined set of objects and their relationships.

You will be managing a collection of objects, each with a unique identifier and a set of references to other objects. The "garbage" will be objects that are no longer reachable from a designated set of "root" objects. Your incremental GC should periodically scan for and reclaim these unreachable objects.

Key Requirements:

Object Model: Define a simple Object struct that includes:
- ID (unique identifier, e.g., an integer)
- References (a slice or map of *Object pointers to other objects it holds)
- A flag or mechanism to mark an object as "live" or "reachable."
Memory Arena/Heap: Maintain a collection of all allocated Objects. This will act as our simulated heap.
Root Set: Designate a set of Objects that are considered always reachable (e.g., global variables or objects explicitly kept alive by the application).
Incremental Collector Logic:
- Mark Phase: Implement a marking phase that starts from the root set and traverses the object graph, marking all reachable objects as "live."
- Sweep Phase: Implement a sweeping phase that iterates through all objects in the heap. Any object not marked as "live" is considered garbage and should be removed from the heap.
- Incremental Execution: The mark and sweep phases should be designed to be interruptible. You'll need to simulate running these phases in small, discrete steps. For example, the mark phase might mark a fixed number of objects at a time, and the sweep phase might process a fixed number of objects before yielding control.
Application Interaction: Provide functions to:
- Allocate new Objects.
- Add/remove references between Objects.
- Explicitly add/remove objects from the root set.
- Trigger a GC cycle (or a portion of it).

Expected Behavior:

The GC should correctly identify and reclaim unreachable objects.
The GC operations should be designed to be broken down into smaller steps, simulating incremental execution. You'll need a way to control how much work is done per "tick" of the GC.

Edge Cases:

Objects with no references.
Cycles in the object graph (e.g., Object A references Object B, and Object B references Object A).
Removing an object from the root set when it's no longer referenced elsewhere.
Concurrent modification of object references while the GC is running (though for this challenge, we can initially assume single-threaded access or handle synchronization explicitly if time permits).

Examples

Example 1: Simple Reachability

// Initial state:
// Roots: [obj1]
// Heap: [obj1, obj2, obj3]
// obj1.References = [obj2]
// obj2.References = [obj3]
// obj3.References = []

// After allocation and referencing:
// obj1 (ID: 1) references obj2 (ID: 2)
// obj2 (ID: 2) references obj3 (ID: 3)
// obj3 (ID: 3) has no references

// Roots = {obj1}
// Heap = {obj1, obj2, obj3}

// Trigger a full GC cycle.
// Mark phase starts from obj1, marks obj1, obj2, obj3. All are live.
// Sweep phase finds all marked as live.
// No objects are collected.

// Now, remove obj1 from roots and make obj2 unreferenced by obj1.
// obj1.References = []
// Roots = {}

// Trigger a GC cycle.
// Mark phase: No roots, so nothing is marked initially.
// Sweep phase:
//   - obj1: Not marked, collected.
//   - obj2: Not marked, collected.
//   - obj3: Not marked, collected.

Example 2: Cycles and Incremental Steps

Imagine an incremental mark phase that can mark up to 2 objects per step, and a sweep phase that can process up to 2 objects per step.

// Initial state:
// Roots: [root_obj]
// Heap: [root_obj, obj_a, obj_b, obj_c, obj_d]
// root_obj references obj_a
// obj_a references obj_b
// obj_b references obj_a (cycle)
// obj_b references obj_c
// obj_c references obj_d
// obj_d has no references

// Roots = {root_obj}
// Heap = {root_obj, obj_a, obj_b, obj_c, obj_d}

// --- GC Cycle Start ---

// Mark Phase - Step 1 (marks 2 objects):
// Starts from root_obj, marks root_obj.
// Traverses to obj_a, marks obj_a.
// Marked: {root_obj, obj_a}

// Mark Phase - Step 2 (marks 2 objects):
// Continues from obj_a's reference to obj_b, marks obj_b.
// Traverses obj_b's reference to obj_a (already marked, no change).
// Traverses obj_b's reference to obj_c, marks obj_c.
// Marked: {root_obj, obj_a, obj_b, obj_c}

// Mark Phase - Step 3 (marks 2 objects):
// Continues from obj_c's reference to obj_d, marks obj_d.
// Marked: {root_obj, obj_a, obj_b, obj_c, obj_d}
// Mark phase complete. All objects are reachable.

// Sweep Phase - Step 1 (processes 2 objects):
// Processes root_obj (marked, kept).
// Processes obj_a (marked, kept).

// Sweep Phase - Step 2 (processes 2 objects):
// Processes obj_b (marked, kept).
// Processes obj_c (marked, kept).

// Sweep Phase - Step 3 (processes 2 objects):
// Processes obj_d (marked, kept).
// Sweep phase complete. No objects collected.

// --- Now, let's make obj_d unreachable ---
// Remove root_obj's reference to obj_a.
// root_obj.References = []

// --- Trigger another GC cycle ---

// Mark Phase - Step 1 (marks 2 objects):
// Starts from root_obj, marks root_obj.
// No outgoing references from root_obj.
// Marked: {root_obj}

// Mark Phase - Step 2 (marks 2 objects):
// No new objects to mark.
// Mark phase complete.

// Sweep Phase - Step 1 (processes 2 objects):
// Processes root_obj (marked, kept).
// Processes obj_a (NOT marked, collected).

// Sweep Phase - Step 2 (processes 2 objects):
// Processes obj_b (NOT marked, collected).
// Processes obj_c (NOT marked, collected).

// Sweep Phase - Step 3 (processes 2 objects):
// Processes obj_d (NOT marked, collected).
// Sweep phase complete. obj_a, obj_b, obj_c, obj_d are collected.

Constraints

The simulated heap will contain a maximum of 1000 objects.
Each object will have a maximum of 10 references to other objects.
The GC "tick" (the amount of work done per incremental step) for both marking and sweeping will be a configurable parameter (e.g., an integer representing the number of objects processed per tick).
Assume no explicit memory allocation/deallocation beyond the managed Objects. The GC itself will manage the removal of objects from its internal heap.
For simplicity in this challenge, assume a single goroutine manages the objects and triggers GC. Concurrent access is not required for the core implementation but can be discussed as an extension.

Notes

This challenge is about understanding the principles of incremental GC, not about achieving optimal performance or replacing Go's built-in GC.
You'll need a way to reset the "live" status of objects before each mark phase.
Consider how to represent the heap and how to efficiently iterate and remove objects during the sweep phase.
Think about how to manage the state of the GC (e.g., is it in the mark phase, sweep phase, what's the current progress within a phase).
A good approach for the mark phase might be a Breadth-First Search (BFS) or Depth-First Search (DFS) adapted for incremental execution. For example, using a queue for BFS and processing a fixed number of items from the queue per GC tick.
The sweep phase typically involves iterating through the entire heap, so you'll need a data structure that supports ordered iteration and efficient removal.