I'm designing a very simple compiler (sort of academic research) and I'm thinking on implementing a simple reference counting GC and also a Mark and sweep. The idea is that reference counting can free dead objects very early when there are no cycles and also this leaves to the following idea: Mark and sweep usually involves some pauses because of the mark and sweep process has to iterate through a lot of references so: Shouldn't a previuos ref-counting make the mark and sweep faster (less elements)? Is this idea nonsense? I've never implemented such a complex thing before and I don't want to work a lot just to find it was a very bad idea.
5
votes
I think this is more or less what CPython does. docs.python.org/2/library/gc.html
– Fred Foo
@larsmans I never dove into the details, but from lurking on python-dev I get the impression that there are some significant differences between CPython's cycle collector and textbook mark and sweep GCs. Moreover, this doesn't necessarily mean it's better than plain mark and sweep: CPython may have both because it started with just refcounting, and when collecting cycles became important, removing refcounting was already out of reach (it certainly is now).
– user395760
3 Answers
3
votes
I intuitively agreed at first, but I came to the conclusion that this intuition is wrong. While ref-counting will remove some garbage before the mark and sweep GC (I'll call it msgc for short), this does not help msgc performance much. The marking phase never even looks at garbage, so early removal of garbage via refcounting doesn't speed up marking. I'm not too sure about the sweeping phase, as this depends on how you implement it, but I can imagine several strategies which are not affected by the amount of garbage enough to make this worthwhile.
Considering the added complexity, it's probably not worth it. You won't get too much performance out of a simple msgc anyway, and the added costs of refcounts (larger object header, slower assignment, etc.) diminish the gain if there even is one.
2
votes
delnan is correct that using ref counting in addition to mark & sweep will not speed up the mark & sweep phase significantly, but it still can serve an important purpose.
If nearly all objects are destroyed (via ref counting) as soon as they go out of scope, then your interpreter won't be amassing nearly as much memory, in which case the GC won't need to be called as often.
Reference counting happens in constant time, and the performance hit comes in such small pieces that the hit really isn't even comparable to that of a mark & sweep algorithm. It's a tradeoff, but from the users perspective, microscopic pauses happening every second might be better than sudden, arbitrary pauses that last for a notable length of time. Naturally it depends on the application.
That is the rationale of CPython's combination of the two techniques; the cyclic garbage collector will rarely (if ever) need to be called, because if the program has no or only a few cycles, most memory will be freed on the fly.
I can tell you from experience, though, implementing and maintaining even a simple interpreter that relies on ref counting can be an enormous pain (especially if you're using plain C).
1
votes
If you're designing a new GC language framework, deterministic resource acquisition/disposal semantics should be designed in rather than plugged in as an afterthought (as was the case with e.g. IDisposable). Reference counting shouldn't be relied upon as part of the GC, however, since maintaining absolutely-robust reference counts in a multi-threaded environment is expensive, and since one must absolutely positively avoid any possibility of memory getting reused while a reference exists, even if a reference count erroneously reports that an object is no longer needed. Note that prematurely releasing a resource is nowhere near as bad as prematurely releasing memory, since the code which frees the resource may invalidate the object encapsulating it. Even though the object would be dead, any references to it would be valid references to an identifiably-dead object. By contrast, if memory was recycled while a reference still existed, the reference itself would become invalid.
What I would suggest you look at doing if you want to maximize GC efficiency in a simple system would be to provide good support for securely freezing references stored in objects [e.g. provide that fields tagged readonly may only be written in the constructor before the object is frozen, and the constructor must freeze an object before exposing it to outside code]. The "mark" or "copy" phase of a GC has to examine every object that might have had new references written to it since the last GC cycle. If the GC is agnostic to which objects are mutable, it must either examine everything or else use write fences to set a flag the first time an object is modified after surviving a GC. If an object holds only immutable references, however, then any objects to which it holds references must be older than the object itself [the lifetime of a frozen object would begin when it is "frozen"--note that no reference to the object would exist outside the constructor at that point]. Consequently, objects which don't hold any mutable references could be ignored entirely by the garbage collector when performing higher-generation collections.
