2 ms·
Wait, if the RC scheme has a cycle collector, how do you ensure there are no CC pauses for acyclic data? Every CC algorithm I know of uses heuristics to determi
by pcwalton 13y ago
Wait, if the RC scheme has a cycle collector, how do you ensure there are no CC pauses for acyclic data? Every CC algorithm I know of uses heuristics to determine when to scan the heap for cycles (usually when an RC drops from >2 to 1) and those can result in pauses proportional to the size of the live set on the heap, even when there are no cycles.
- rbehrends 13y agoI 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.
- pcwalton 13y agoIt's still proportional to the live set in the general case. In practice cycle collectors tend to have to scan a lot, leading to some severe pause times (30ms in Firefox used to be common until the ad-hoc ForgetSkippable was added). Heuristics that cycle collectors use tend to fall down a lot in practice, unfortunately.