Comment by lisper
12 hours ago
> you only trace when you hit cycles
How do you tell when you've hit a cycle?
> hopefully design your language semantics to discourage cycles
Why? Cyclical structures can be very useful. For example, it can be very handy in many situations for a contained object to have a back-pointer to its container.
[UPDATE] Two responses have now pointed out that this particular case can be handled with weak pointers. But then I can just point to a general graph as an example where that won't work.
> For example, it can be very handy in many situations for a contained object to have a back-pointer to its container.
That's not a true cycle, it's just a back link for which "weak" reference counts suffice. The containment relation implies that the container "owns" the object, so we don't need to worry about the case where the container might just go away without dropping its contents first.
(Edit: I agree that when dealing with a truly general graph some form of tracing is the best approach. These problem domains are where tracing GC really helps.)
OK, then I'll pick a different example: a general graph.
If you put all the nodes into an array and use weakrefs (or indices) for node->node edges you move the node ownership to a single object which will make your garbage collection faster for either algorithm, and will also improve your memory locality.
"How do you apply algo X to a problem which has been narrowly-tailored and/or under-specified to specifically exclude X" isn't exactly a constructive inquiry.
7 replies →
> For example, it can be very handy in many situations for a contained object to have a back-pointer to its container.
Does it frequently need an owning reference though or would a weak reference suffice? Usually the latter situation suffices.
A fair point, but then you're still putting the burden on the programmer to figure out where a weak reference is appropriate.
But then I'll just choose a different example, like a general graph.
> How do you tell when you've hit a cycle?
https://pages.cs.wisc.edu/~cymen/misc/interests/Bacon01Concu...
TLDR there are heuristics which can give you a hint. And then you trigger a local trace to see.
> Why?
Because then you incur the cost of a trace -- and potentially paging in from slow-slow disk -- vs a simple atomic refcount.
Even just a localized trace on live objects is a pointer-chasing cache & branch prediction killer.