Tracing collection: find the objects reachable from roots

Represent each allocated object as a node and each traced strong reference as a directed edge. Roots can include references reported by stacks, registers, globals, and runtime handles, according to the implementation. Start with their targets, then repeatedly follow outgoing edges until no new node is discovered. A cycle reachable from a root remains live under this criterion. A cycle disconnected from all roots does not. This is different from reference counting's local incoming-edge total, which cannot by itself distinguish those two situations.

A collector needs cooperation from the language implementation to identify references correctly. A precise runtime knows which fields and execution locations contain managed references; a conservative approach can treat some pointer-like patterns as possible references and retain additional objects. Native handles, interior pointers, and runtime-specific weak or finalization semantics complicate the simple graph. Our exercises use precise strong edges and no finalizers. State those assumptions before claiming that every unreachable object will be reclaimed immediately or that a hidden native address is automatically understood by the collector.

A simple stop-the-world mark-sweep collector first marks reachable objects while application mutation is stopped, then makes unmarked storage available for reuse. Moving collectors instead relocate some surviving objects and update the references needed to find them. Not every tracing collector moves objects, and not every phase must stop application threads. Concurrent collection needs barriers and coordination to keep the graph argument valid while the application changes it. These implementation choices affect pauses, CPU cost, fragmentation, and how native code may hold addresses.

Reclaiming an object for the runtime allocator does not necessarily return the corresponding physical pages to the operating system. The runtime may retain heap capacity for later allocations, and process memory also includes stacks, native libraries, code, metadata, and external buffers. Compare metrics with matching boundaries. A falling live-object total alongside stable resident memory is not sufficient evidence that collection failed. Conversely, increasing live payload after repeated collections suggests a retention path or workload change that more frequent collections alone cannot remove.

A service can allocate many short-lived temporary objects while maintaining a modest live heap. Another can allocate slowly but keep every request in a global history list, producing steadily increasing live memory. The first stresses allocation and collection throughput; the second has an application retention policy. To investigate, compare allocation profiles with post-collection live-object paths under the same workload. Identify which root keeps an unexpected object reachable. Removing a registry entry, listener, or cached result may solve the cause more directly than changing collector settings.

The probability lab approximates the count of surviving equal-sized independent objects, rather than traversing a graph. Set n=20 and survival probability p=0.25: predict a mean of five survivors and variance 3.75. Increasing p raises the mean even if the total number allocated remains fixed. If each survivor occupies 64 bytes, the expected payload is 320 bytes in this artificial cohort. Real object reachability is often highly correlated through shared graph structure. Use the lab to separate survivor fraction from allocation count, then explain why it cannot decide which nodes a tracing collector must mark.