[Haskell-cafe] Real-time garbage collection for Haskell

[Job Vranish]

My current area of work is on realtime embedded software programming for
avionics systems. We do most of our coding in Ada but I've been dreaming of
using haskell instaed.

However, the garbage collector is actually one of the larger obsticles to
making this happen.

All of our avionics software needs to be certified by various regulatory
agencies, and there are varying levels of certification depending on
criticality. For the higher certification levels we would need to be able to
sure (or a least very very confidant) that the GC will collect everything
within a fixed amount of time, and that it won't take more than some fixed
amount of time per major from to do it.

A delay of a several milliseconds that could occur effectively at random is
completely unacceptable.

I would be very interested in alternative GC algorithms/approaches  that
would have a more deterministic/realtime behavior. I would be even be
willing to help out if there is other interest in this area :)


As a side note, I ran across an article on a way to use 100% reference
counting in a pure language by using weak references and being careful how
you preserve the weak/strong references during graph reduction:
http://comjnl.oxfordjournals.org/cgi/content/abstract/33/5/466
I don't want to pay $25 for the article though so I don't know how viable it
is. It would probably have lower performance than the current generational
GC but in this case I'd be willing to trade performance for determinism.
Has anyone heard of this algorithm before?

- Job


On Mon, Mar 1, 2010 at 9:53 AM, Thomas Schilling <nominolo at googlemail.com>wrote:

> On 28 February 2010 05:20, Luke Palmer <lrpalmer at gmail.com> wrote:
> > I have seen some proposals around here for SoC projects and other
> > things to try to improve the latency of GHC's garbage collector.  I'm
> > currently developing a game in Haskell, and even 100ms pauses are
> > unacceptable for a real-time game.  I'm calling out to people who have
> > seen or made such proposals, because I would be willing to contribute
> > funding and/or mentor a project that would contribute to this goal.
> > Also any ideas for reducing this latency in other ways would be very
> > appreciated.
>
> There is a SoC project suggestion to implement Immix's ideas [1] in
> GHC's GC.  Both already use similar overall designs.  Both split the
> heap into regions which may employ different collection strategies.
> However, Immix does not address real-time issues.
>
> The main difficulty with real-time GC is that, while first-generation
> collection is usually very fast, eventually you just have to collect
> the old generation and you have to do it all at once.  Sun's new
> Garbage-First ("G1") [2] collector therefore tracks pointers between
> regions, as opposed to just pointers from older two newer generations.
>  This allows collecting regions independently (and in parallel).  G1
> is still stop-the-world, although marking phase is concurrent.
> Tracking pointers between all regions can result in quite substantial
> space overheads, however, so G1 uses some heuristics to discover
> "popular objects" and treats them specially.  In a personal
> conversation Simon Marlow expressed to me that he intends to go
> further into this direction, but I don't know how high-priority it is.
>  In general I don't think true real-time is the goal in any case, but
> rather a general effort to keep GC-pauses short.
>
> Truly concurrent garbage collection is a whole different beast.
> Concurrent marking can be implemented efficiently with a write
> barrier.  I don't know of any fully concurrent GC scheme that gets by
> without a read barrier and significant space overhead, however.  There
> are certainly no plans from the GC HQ to implement a fully concurrent
> GC.
>
> [1]:
> http://www.cs.utexas.edu/users/speedway/DaCapo/papers/immix-pldi-2008.pdf
> [2]: http://research.sun.com/jtech/pubs/04-g1-paper-ismm.pdf
>
> --
> Push the envelope.  Watch it bend.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100301/bc7c6d5f/attachment.html