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

Thomas Schilling nominolo at googlemail.com
Mon Mar 1 17:01:25 EST 2010

On 1 March 2010 21:34, Neil Davies <semanticphilosopher at googlemail.com> wrote:
> I don't know that hanging your hat on the deterministic coat hook is the
> right thing to do.
> The way that I've always looked at this is more probabilistic - you want the
> result to arrive within a certain time frame for a certain operation with a
> high probability.

That's where I would think the difference between hard and soft
real-time lies, as I understand it.  Of course, "real" hard real-time
of course is practically impossible on modern hardware due to caches,
branch prediction, out-of-order execution and such like.

> There is always the probability that the h/w will fail
> anyway - you could even reason that the software taking too long is just  a
> transient fault that clears - random (non-correlated - preferably a
> bernoulli choice) failures are OK, non-deterministic ones aren't.
> This probabilistic, low probability of being at the tail of timing, approach
> would give a lot more flexibility in any form of (say incremental) GC - you
> may not be able to bound the incremental steps absolutely but a strong
> probabilistic bound might well be more achievable.

The Garbage-First paper showed some promising but not spectacular
successes in keeping the soft real-time goal.  I don't know the
correct numbers off the top of my head, but I think they missed the
deadline in > 5% of the cases.  I would assume that it should be < 1%
if you want to treat it as a random failure.  I understand that in a
fault-tolerant systems you have to handle worse things than that, but
you make assumptions about the likelihood of each kind of error
(otherwise you may run into QoS issues).

As Job and John have pointed out, though, laziness per se doesn't seem
to be an issue, which is good to hear.  Space leaks might, but there
is no clear evidence that they are particularly harder to avoid than
in strict languages.  As Röjemo and Runciman put it: "By using heap
profiles on a lazy language we find problems with lazy languages.
Using it on a strict language we would find problems with strict
languages too." [1] (very recommended paper, btw.)

[1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

Push the envelope.  Watch it bend.

More information about the Haskell-Cafe mailing list