Concurrent Garbage Collection: Sweeping Phase

Concurrent sweeping is a crucial phase in garbage collection, responsible for reclaiming memory occupied by unreachable objects. This challenge asks you to implement a simplified concurrent sweeping algorithm in Go, focusing on safely traversing and marking objects for collection while the program continues to execute. This is a foundational element in many garbage collection systems and understanding it is key to optimizing Go's runtime.

Problem Description

You are tasked with implementing a concurrent sweeping phase for a simplified garbage collector. Assume you have a slice of Object structs, each potentially containing pointers to other Object structs. The goal is to identify and reclaim memory occupied by objects that are no longer reachable from a set of root objects.

The sweeping phase will operate concurrently with the main program. Therefore, you must ensure thread safety when traversing the object graph and marking objects as reachable. You'll be provided with a slice of root objects and the entire object slice. Your implementation should traverse the object graph starting from the root objects, marking all reachable objects. Finally, it should return a slice containing the indices of the unreachable objects (those that were not marked as reachable during the sweep).

Key Requirements:

• Concurrent Traversal: Use goroutines to traverse the object graph concurrently.
• Thread Safety: Protect shared data structures (e.g., the reachable slice) with appropriate synchronization mechanisms (e.g., mutexes).
• Reachability Marking: Maintain a slice (reachable) to track the indices of objects that are reachable from the root objects.
• Unreachable Object Identification: Return a slice containing the indices of objects that are not present in the reachable slice.
• Object Structure: The Object struct has a field children which is a slice of integers representing the indices of child objects.

Expected Behavior:

The function should return a slice of integers representing the indices of unreachable objects. The order of indices in the returned slice is not important.

Edge Cases to Consider:

• Circular References: The object graph may contain circular references. Your algorithm should handle these correctly without infinite loops.
• Empty Object Graph: The input slice of objects may be empty.
• No Reachable Objects: All objects may be unreachable.
• Root Objects Pointing to Themselves: A root object might point to itself directly or indirectly.
• Root Objects Pointing to Unreachable Objects: A root object might point to an object that is ultimately unreachable.

Examples

Example 1:

Input:
objects := []Object{
    {children: []int{1}},
    {children: []int{2}},
    {children: []int{}},
}
roots := []int{0}

Output: [2]
Explanation: Object 0 points to object 1, which points to object 2. Object 0 is a root. Therefore, 0, 1, and 2 are reachable. Object 3 is not reachable.

Example 2:

Input:
objects := []Object{
    {children: []int{1}},
    {children: []int{0}},
    {children: []int{}},
}
roots := []int{0}

Output: [2]
Explanation: Object 0 points to object 1, which points back to object 0. Object 2 is not reachable.

Example 3:

Input:
objects := []Object{
    {children: []int{1}},
    {children: []int{2}},
    {children: []int{0}},
}
roots := []int{0}

Output: []
Explanation: Object 0 points to object 1, which points to object 2, which points to object 0. All objects are reachable.

Constraints

• The number of objects will be between 0 and 1000.
• The number of root objects will be between 0 and 100.
• Object indices will be valid (i.e., within the bounds of the objects slice).
• The algorithm should complete within 1 second. (This is a soft constraint, but excessive runtime will be penalized).
• The children slice of an object will contain only valid indices.

Notes

• You can use a sync.Mutex to protect shared data structures.
• Consider using a worker pool pattern to manage the goroutines.
• The reachable slice should be initialized with a capacity equal to the number of objects to avoid unnecessary reallocations.
• Focus on correctness and thread safety first, then optimize for performance.
• The Object struct is defined as follows:

type Object struct {
    children []int
}