I think this whole discussion is missing a couple of things. First, the *general* form of what you are talking about is called "dominance analysis". That is: "liveness of *this* reference dominates liveness of *that* reference". There are a bunch of forms of this, one of which is the ownership analysis form. If you twist your head, linear types can be seen as a special simple case of a dominance relation.
But there are a number of problems with all of this: 1. It places complex burdens on the compiler that are initially error prone and not likely to be robust under maintenance. 2. Since you don't trace unreachable stuff in any case, this doesn't really help deallocation. What is helps is *tracing*. 3. In practice, it doesn't simplify the tracing problem, because the dominated DAG will usually turn out to have references to non-dominated things that need to be traced. Where that is true, you either give up on exploiting the dominance relation or you end up doing extra book-keeping to implement the "skip marking" that is expensive to do. 4. You still have to deal with finalization. 5. You still have to deal with all of the corner cases. 6. You still have to deal with the problem that regions can grow in unbounded ways. Such regions can end up with non-live objects and need to be collected. The corner case issue means that you have to implement the full algorithm in any case. At that point, I think that engineering concerns probably motivate keeping it simple. It turns out that a relocating tracing algorithm can do a surprisingly good job discovering clustered objects. Since you end up having to trace them anyway, I think the goal should be to organize the heap for greater efficiency. Notably: - Copy avoidance when a cluster of objects is collectively live. - Hierarchical liveness marking. E.g. (1) this entire page is still live (2) this line is still live (3) this object is still live So now what you do when you trace an object into an empty frame is you keep track of how many *subsequent* objects were reached by that one, and let a mark on the initial object cover the subsequent objects as well. If you do this incrementally you can build up pretty effective clustering. But stepping back from all this, we know that the C4 algorithm actually works in practice, and I think that's where our focus should be. And incidental to that, I recently saw a post here confirming my theory about what they did after the Linux guys dorked them over to get efficient page access testing. Which is what I was going to do. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
