I am not sufficiently familiar with the inner details of Nimrod's GC implementation to give you a full answer, but, no, you don't have to scan the entire live h

I am not sufficiently familiar with the inner details of Nimrod's GC implementation to give you a full answer, but, no, you don't have to scan the entire live heap to reclaim cycles. The technique is called "trial deletion" and only has to traverse potential cycles. Strictly speaking, a type-agnostic implementation may have to traverse all objects reachable from an object whose reference count was decremented since the previous pass, but in a strongly typed language you can skip that for all objects that can't be part of a cycle. Nimrod at least makes use of that information in asgnRefNoCycle() in system/gc.nim. Obviously, if everything on the heap is part of one big cycle, then, yes, you'll have to scan the entire heap.