How does the GC know there aren't any cyclic references in there to avoid tracing all the pointers the same way?
nb if it used an arena allocator then it could simply not do anything on free as long as it was acceptable to reclaim the memory later.
nb if it used an arena allocator then it could simply not do anything on free as long as it was acceptable to reclaim the memory later.
Mark-and-sweep, as well as generational-collectors, walk through all references starting from the root of all variables. In college-level toy garbage collectors, you usually use 1-bit of the pointers to mark where your algorithm has been to (or not). EDIT: The top 16-bits of x86_64 systems are often ignored, because x86 CPUs (AMD Ryzen or Intel i7 / Xeons) only have 48-bit physical memory space, and are a common set of bits used for this "marking" process)
Its basically just a depth-first-search or breadth-first-search over the graph of memory pointers. Its pretty simple in concept, but lots of details depending on performance considerations.