On Mon, Aug 4, 2014 at 9:23 AM, Jonathan S. Shapiro <[email protected]> wrote:
> 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. Obviously I agree here. My thought experiment isn't a practical bit-c related proposal, but more a thought experiment brought to some smart people for feedback. It's notoriously hard to find people who even care about these topics. For practical pauseless GC, today I'd bet on C4 or Ulterior Reference Counting with pauseless cycle finding. 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. > That's good to know. My thought-experiment was born out of considering how to handle heap lifetime which can't be statically analyzed - without tracing. Programs with manual-memory management handle this with runtime clean-up code (aka "manually freeing everything that needs to be freed")... so I wondered how far one can get if we put less burden on static-analysis and more burden on a run-time ownership dominance api protocol. > > 1. Since you don't trace unreachable stuff in any case, this doesn't > really help deallocation. What is helps is *tracing*. > > Yes. Tracing is a real performance burden when tenured churn is high and there is lots of live-data. I'm interested in ways to help that. > > 1. 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. > > GCs are complicated, so it's hard for me to unambiguously understand what you meant here by "simplify". The goal of my thought experiment is to find a way to remove chunks of memory from the view of tracing, so tracing doesn't have to have as much of a heap-size proportional cost. Programs with manual memory allocation still beat the overall performance of C4, because they don't have to inefficiently trace the live heap like C4 does. My thought was a random brainstorm about how to help close that performance gap.
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
