[MLton-devel] Optimizing garbage collection efficiency paper

[Stephen Weeks]

> I read an interesting article in the last issue of TOPLAS on the impact 
> of liveness analysis on garbage collection efficiency.
> 
> The main result of the paper is that garbage-collection oriented 
> liveness schemes focused on intraprocedural liveness analysis of local 
> variables are weaker, in the sense that a bunch of useless data is 
> retained, than interprocedural liveness for local + globals. Their 
> benchmarks are performed on C/C++/Eiffel code though.
> 
> I presume that MLTON, as most ML implementations, uses for determining 
> GC roots an intraprocedural analysis ?

Yes.  MLton's liveness analysis runs on a traditional control-flow
graph of basic blocks with the usual definition of defs/uses.  Here's
one idea we've had as to how interprocedural analysis might be
helpful.  I haven't seen the paper yet, so I don't know if it's
related.

If one has globals that are of unbounded size, then one must be
careful to blackhole a global after its last reference.  An
interprocedural analysis is required to determine when this is.  We
could do this analysis easily on our IL, and considered it years ago,
but decided instead to adopt the simpler approach of not allowing
globals of unbounded size.  So, our globalization pass does a simple
size analysis based on types (see typeIsSmall in
closure-convert/globalize.fun) and only globalizes variables that it
can prove hold small values.

Our current approach may cost in terms of performance, since the large
values that aren't globalized must be carried around in closures or on
the stack.  But, we don't have to do the blackholing, since the large
values will become unreachable after their last reference.  It would
be interesting for someone to implement the blackholing analysis in
MLton to see what happens.  Globalization of small values is a big win
in some cases, IIRC, so I could imagine getting some gains from
globalizing large values.

We have been very careful in MLton to consider space-safety when doing
any optimization, and I don't know of any cases where MLton is not
safe-for-space.  I would be interested to understand if this paper
brings up a space-leak that applies to MLton.


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel