And, technically, GCs collect non-garbage, and throw away what remains. They don’t care whether what they throw away contains cycles or not, but have to take care that they don’t keep running in circles when they follow links between objects while collecting the non-garbage.
The simplest way to do this is to use the low bit of the address (so long as you align your memory to at least 2 bytes this is fine as all addresses will end in 0) as a marker for whether you've already visited that pointer.
And yes, you're correct that GCs handle cycles without issue (that's a large part of the reason to use tracing GC over other memory management strategies like ObjC's auto-reference counting).
Don't know if any GCs use it, but if modifying the pointers is not possible then one alternative is Floyd's cycle-finding algorithm[1] which uses constant storage (two pointers).
"Finding cycles" is not really the problem a GC is trying to solve. It's trying to find all of the non-reachable data, across a possibly cyclic graph. It just has to ensure that it doesn't loop infinitely while traversing that graph.
I purposefully used the word 'efficient' in my original post. Of course you can find cycles many ways, but floyd's (or similar) are not acceptably fast and never can be in general.
Swift leaves it in the hand of programmers and says "use weak references".
Otherwise traditional GC use a copying mechanism, what doesn't end up copied is dead.
The old reference counting GC in Nim had that extra copying pass when a type could have cycles.
That said, it's very easy to tell if a type can have cycles or not at compile-time, you just need to check if it refers to itself i.e. does the Node type has a Node field (or a field that can recursively contain a Node field).
> easy to tell if a type can have cycles or not at compile-time, you just need to check if it refers to itself
Certainly useful at times as I suppose it may be used to ensure you don't have cycles (I imagine that could be useful for resource management) but 'can have cycles' is definitely not 'does have cycles'. It's the latter that's important here.
Cycle detection at point of creation (when a pointer is set). You can do a full scan of data structure graph after every malloc but that's equivalent to your GC, and clearly horribly, unacceptably expensive.
