Let's address another GC misconception: that you can divide GC algorithms into "perfectly precise" ones like tracing and "imprecise" ones like reference counting without cycle collection.
2
9
1
45
In fact, all GCs use some sort of conservative heuristic. The real problem GCs are trying to solve is to identify memory the program will never use again. This is a dynamic problem, and so a truly precise solution runs up against the halting problem.
3
1
26
Precise tracing GCs approximate this problem by identifying memory that is no longer *reachable* from a set of root objects. This is a narrower set than the set of data the program will dynamically use again. The difference is why you can still have leaks in e.g. JS.
6
1
1
22
Replying to @pcwalton
In some JS leaks, the program *does* use the object again, but doesn't need to. (Consider the extreme example of a cache that never evicts entries; cache lookup still examines them.) So you could say "use again" is *still* too conservative since some future uses are unneeded.

Aug 20, 2019 · 8:36 PM UTC

1
2
Replying to @davidbaron @pcwalton
Yeah, you'd need some kind of definition that involves observational equivalence. I saw something like this in a paper many years back, but I can't find it now.
1