Garbage Collection

Hi,


I'm glad to see that there is interest in improving MLton's
GC. I would, in principle, also be very interested in
working on this and incorporating what I have into MLton,
though I'm not a student and I cannot justify spending time
on it without some kind of funding, so I suppose that the
Google Summer of Code is not the right platform for me.
I would, however, like to give some input and pointers.

I put my M.Sc. thesis on garbage collection online earlier on:
http://www.cex3d.net/cexl/memorymanagement/

My implementation is a two-generation GC with a copy
collector as the first generation and a mark-region
collector as the second generation, in the style of
the Immix collector from:

Stephen M. Blackburn and Kathryn S. McKinley. ”Immix:
A Mark-Region Garbage Collector with Space Efficiency,
Fast Collection, and Mutator Performance”. In PLDI’08.
ACM, June, 2008.

I would very highly recommend reading at least this
article on Immix, to the extent of claiming that you
don't know the state of the art in garbage collection
if you haven't read it ;-)

Also, my implementation features a statically typed
memory traversal for marking, which has some code
generation overhead but should otherwise be very efficient,
though the current scheme likely needs a small improvement
to avoid the problem with shared data taking (worst-case)
exponential time (extending the static scheme with a mark
bit in the second and subsequent pointers of record/tuple
nodes with at least two nested memory nodes should be enough).

The implementation also has incremental marking on the second
generation, to try to bound the maximum pause times on GC to
make it suitable for interactive applications like games.
There were some issues in getting this to work reliably,
though possibly it's just the timer that is buggy.

This incremental marking approach comes mainly from:

A. Demmers, M. Weiser, B. Hayes, H. Boehm, D. Bobrow and S. Shenker. 
”Combining Generational and Conservative Garabage Collection:
Framework and Implementations”. In ACM Symposium on the Pinciples
of Programming Languages, pages 261-269. ACM, 1990.

I would also recommend this article for some deep and
interesting insights into GC designs ;-)

Notes and limitations of my current simplistic implementation:

1) The remark above on record tagging vs. shared data is important
2) The remark above on the timer / incremental part is important
3) No support for large memory objects (needs special handling
    and is part of the full mark-region / Immix design)
4) Memory defragmentation was not implemented
    (also part of the full mark-region / Immix design)
5) It avoids many tags and therefore has low memory overhead,
    but will likely not support many of MLton's more advanced
    (non-SML) features, such as profiling, finalization etc.
    I.e. maybe this could be an alternative GC for production
    Standard ML compilation only, not debugging or certain
    of the non-standard features
6) Incorporating the static code-generating tagging scheme
    into MLton is probably not trivial...
7) No support for multi-threaded applications, though it
    should be possible to add to the implementation, but I
    suppose that MLton currently doesn't support this anyway?
    (with threads running truly in parallel, that is)

Notes on MLton's current GC (though I'm still using MLton 20070826):

*) It seems to be to be a major performance bottleneck
    for efficient Standard ML code execution in MLton.
    This is based on experience from many real-life examples
*) It does not seem to support more than 2GB of data on
    32-bit machines, despite the website stating 4GB.
    Even on a 64-bit machine it seems to only want to go
    slightly above 2GB.
    Maybe this was improved since the 2007 version?
    Otherwise, I suspect that the "one single large heap"
    design might be part of the reason for this? The mark-region
    scheme from the Immix article and my implementation would
    be one way to overcome this

I am CC'ing this directly to your mails since I suspect
that my mail will not go to the list due to my mail setup
(at least this has been a problem in the past).


Cheers
Johnny Andersen
-- 
http://www.cex3d.net/inverse/ - 3D models from images automatically
http://www.hardcoreprocessing.com
http://www.anoq.net/music/ - creative instrumental electronic music

------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite
It's a free troubleshooting tool designed for production
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://p.sf.net/sfu/appdyn_d2d_ap2