[MLton] Paging friendly GC?

[Stephen Weeks]

> However, I seem to recall that MLton uses a 'generational mark-sweep'  
> algorithm...?

Yes, that is what MLton uses when memory gets tight.

> I know that MLton performs very poorly once the heap size exceeds
> physical memory. The system thrashes to death. So, when I saw this,
> I thought maybe those of you with a clue might care:
>
> http://www.cs.umass.edu/~emery/pubs/f034-hertz.pdf
> 
> Is this relevant / useful for MLton?

Yes.  It is a nice idea that could be applied to MLton's collector.
My guess is that it would be a one to two month project.

For those who haven't read the paper, the idea is to add to the
collector an additional (oldest) generation consisting of all the
pages that are not resident in memory.  The garbage collector doesn't
visit this oldest generation, and hence doesn't cause page faults.  A
single bit in the header of each object (a "bookmark") is used to keep
track of the existence of an intergenerational pointer from the oldest
generation to the object.  As pages are moved between memory and disk,
the runtime maintains the bookmarks (this requires OS cooperation to
inform of the movement).

Applying the technique to MLton would require a substantial rewrite
because of MLton's use of a monolithic heap.  There are also changes
due to the fact that the runtime can't move objects pointed to by
objects in the oldest generation, since you don't want to visit the
out-of-RAM page to update the pointer.  There's also the problem of
avoiding space leaks from keeping dead off-disk objects alive too
long.  None of those problems is insurmountable; they just take work.

The main problem in practice is that the technique requires
cooperation from the OS that doesn't seem to be available in stock
kernels.  They have a 600 line kernel mod for Linux.  I don't know how
much, if any, of the benefit can be achieved on a stock kernel.

> Could something like this make a self-compile feasible with < 512MB RAM?

I doubt it would help much.  In self compiles, there really is that
much live data, and it's all touched by the mutator frequently.