5 ms·
Yes. The general term these days is tracing garbage collection. (https://en.wikipedia.org/wiki/Tracing_garbage_collection https://en.wikipedia.org/wiki/Tracing_
by wahern 10y ago
Yes. The general term these days is tracing garbage collection. (https://en.wikipedia.org/wiki/Tracing_garbage_collection https://en.wikipedia.org/wiki/Tracing_garbage_collection)
There are all kinds of bells & whistles you can add on top of the general approach, mostly time-space tradeoffs, such as with a copying collector. But the overall time-space complexity generally remains the same. Sometimes it can get worse, like when you add concepts like ephemerons.
- ysleepy 10y agoWell defining the java GC as tracing is underspecifying it a bit. Virtually all GCs are non-refcount, AFAIK mostly because touching refcounters all the time destroys memory performance. A tracing GC can do that in a batched and parallel fashion. And then you realize that they are more or less the same in the end: https://pdfs.semanticscholar.org/91dc/a25f8cb407fc68218f7d5adb912e7db35e81.pdf https://pdfs.semanticscholar.org/91dc/a25f8cb407fc68218f7d5a... "A Unified Theory of Garbage Collection" TL;DR: Refcount and tracing are a duality.
- wahern 10y agoThat paper discusses a reference counting GC which also has a trace phase in order to reclaim cycles. "Reference counting must perform extra graph iterations in order to complete collection of cyclic data. This is typically viewed as a major drawback of reference counting" What that paper really shows is the equivalence of any kind of tracing collector. In practice when people refer to reference counting it's usually implied that there's no trace phase, and that the GC cannot reclaim cycles. Perl, Swift, etc, are the typical examples. Python is the counter example because it does reference counting and tracing.