Real-time garbage collection for Haskell

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
50 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Real-time garbage collection for Haskell

Luke Palmer-2
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.

Thanks,
Luke
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Pavel Perikov
Did you really seen 100ms pauses?! I never did extensive research on this but my numbers are rather in microseconds range (below 1ms). What causes such a long garbage collection? Lots of allocated and long-living objects?

Pavel.

On 28.02.2010, at 8:20, Luke Palmer 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.
>
> Thanks,
> Luke
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Neil Davies-2
My experience agrees with Pavel.

I've never observed ones that size. I have an application that runs in  
'rate equivalent real-time' (i.e. there may be some jitter in the  
exact time of events but it does not accumulate). It does have some  
visibility of likely time of future events and uses that to perform  
some speculative garbage collection. GC is pretty short and i've not  
seen an effect > 1ms in those runs (all the usual caveats apply - my  
programs are not your programs etc).


Neil

On 28 Feb 2010, at 09:06, Pavel Perikov wrote:

> Did you really seen 100ms pauses?! I never did extensive research on  
> this but my numbers are rather in microseconds range (below 1ms).  
> What causes such a long garbage collection? Lots of allocated and  
> long-living objects?
>
> Pavel.
>
> On 28.02.2010, at 8:20, Luke Palmer 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.
>>
>> Thanks,
>> Luke
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Andrew Coppin
In reply to this post by Luke Palmer-2
Luke Palmer 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 guessing making the GC concurrent (i.e., so you can perform GC
without having to stop all Haskell threads) would probably help in the
multithreaded case...

(I'm also guessing this is slightly nontrivial to implement. :-) )

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Heinrich Apfelmus
In reply to this post by Luke Palmer-2
Luke Palmer 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.

Overly long garbage collection might also be a sign of space leaks.

But there are many other things that can go wrong in a real time system
and might explain your delays. For example, you might need to avoid
amortized time data structures like  Data.Sequence . Or for physics
simulations, you'd need to fix the time step ∆t, as described in

   http://gafferongames.com/game-physics/fix-your-timestep/

or numerical integration will deteriorate rather quickly.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Real-time garbage collection for Haskell

Derek Elkins
On Sun, Feb 28, 2010 at 10:03 AM, Heinrich Apfelmus
<[hidden email]> wrote:

> Luke Palmer 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.
>
> Overly long garbage collection might also be a sign of space leaks.
>
> But there are many other things that can go wrong in a real time system
> and might explain your delays. For example, you might need to avoid
> amortized time data structures like  Data.Sequence . Or for physics
> simulations, you'd need to fix the time step ∆t, as described in
>
>   http://gafferongames.com/game-physics/fix-your-timestep/
>
> or numerical integration will deteriorate rather quickly.

Incidentally, what's described there is a simplified version of the
frequency locked loops described in Massalin's thesis on Synthesis OS,
and it is used there for about the same purpose in a soft real-time
context.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.4871
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Luke Palmer-2
In reply to this post by Pavel Perikov
On Sun, Feb 28, 2010 at 2:06 AM, Pavel Perikov <[hidden email]> wrote:
> Did you really seen 100ms pauses?! I never did extensive research on this but my numbers are rather in microseconds range (below 1ms). What causes such a long garbage collection? Lots of allocated and long-living objects?

This is all hypothetical right now.  I heard some horror stories in
which people had to switch to the main game loop in C++ and only do
the AI logic in Haskell because of pauses.  I would rather not do
that, especially because this project is *about* proving Haskell as a
viable game development platform.  So I am trying to be prepared if I
do see something like that, so that it doesn't put the show on hold
for a few months.

Presumably large, long-living objects would cause the generation 0
collections to take a long time.  I am not sure if we will have any
said objects, but we can't rule it out...

Thanks for the positive reassurances, at least.  I'd like to hear from
people with the opposite experience, if there are any.

Luke
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Peter Verswyvelen-2
Sounds like we need to come up with some benchmarking programs so we
can measure the GC latency and soft-realtimeness...

PS: Regarding Haskell and games: the University of Utrecht teaches
Haskell in their brand new "game technology" course :-)

On Mon, Mar 1, 2010 at 1:04 AM, Luke Palmer <[hidden email]> wrote:

> On Sun, Feb 28, 2010 at 2:06 AM, Pavel Perikov <[hidden email]> wrote:
>> Did you really seen 100ms pauses?! I never did extensive research on this but my numbers are rather in microseconds range (below 1ms). What causes such a long garbage collection? Lots of allocated and long-living objects?
>
> This is all hypothetical right now.  I heard some horror stories in
> which people had to switch to the main game loop in C++ and only do
> the AI logic in Haskell because of pauses.  I would rather not do
> that, especially because this project is *about* proving Haskell as a
> viable game development platform.  So I am trying to be prepared if I
> do see something like that, so that it doesn't put the show on hold
> for a few months.
>
> Presumably large, long-living objects would cause the generation 0
> collections to take a long time.  I am not sure if we will have any
> said objects, but we can't rule it out...
>
> Thanks for the positive reassurances, at least.  I'd like to hear from
> people with the opposite experience, if there are any.
>
> Luke
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Soenke Hahn
In reply to this post by Luke Palmer-2
On Monday 01 March 2010 01:04:37 am Luke Palmer wrote:

> On Sun, Feb 28, 2010 at 2:06 AM, Pavel Perikov <[hidden email]> wrote:
> > Did you really seen 100ms pauses?! I never did extensive research on this
> > but my numbers are rather in microseconds range (below 1ms). What causes
> > such a long garbage collection? Lots of allocated and long-living
> > objects?
>
> This is all hypothetical right now.  I heard some horror stories in
> which people had to switch to the main game loop in C++ and only do
> the AI logic in Haskell because of pauses.  I would rather not do
> that, especially because this project is *about* proving Haskell as a
> viable game development platform.  So I am trying to be prepared if I
> do see something like that, so that it doesn't put the show on hold
> for a few months.
>
> Presumably large, long-living objects would cause the generation 0
> collections to take a long time.  I am not sure if we will have any
> said objects, but we can't rule it out...
>
> Thanks for the positive reassurances, at least.  I'd like to hear from
> people with the opposite experience, if there are any.

Yes there are. I am working on a game with Haskell using OpenGL rendering.
I've done some frame time measurements lately and encountered single frames
needing more than 100ms to be rendered. I am currently trying to gather
information on what is going on in these 100ms and why. From what i
understand, the GC is running very often and just some (very few) of its runs
are very slow.

BTW: switching to parallel GC (either with -N1 or -N2 (on a dual core
machine)) made the behavior MUCH worse, for some reason.

Sönke


>
> Luke
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Thomas Schilling-2
In reply to this post by Luke Palmer-2
On 28 February 2010 05:20, Luke Palmer <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Job Vranish-2
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 <[hidden email]> wrote:
On 28 February 2010 05:20, Luke Palmer <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Sebastian Sylvan
In reply to this post by Luke Palmer-2


On Sun, Feb 28, 2010 at 5:20 AM, Luke Palmer <[hidden email]> 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.

Since we're talking games here (my profession), I'd point out that it would be cool to be able to supply "hints" to the GC about when might be a good time to do a GC (without unconditionally forcing it), games in particular have some pretty specific properties that may be exploitable. 

Presumably a non-trivial portion of the objects copied from the nursery/G0 are actually short-lived objects that just happened to have their short life-span overlap with the collection. So really, copying them to the next generation is a "mistake" in some sense. For games, though, we have a very good point that occurs regularly where we know that all/most short-lived objects will no longer be referenced - at the start of a fresh frame. 
So if we could do as many as possible of our G0 collections at that point we'd avoid "accidental copying" of objects that are actually short-lived into the older generation (which should reduce pressure on that older generation, as well as speed up G0 collection). Ideally we'd have some way of telling the GC to try to avoid running during the actual frame itself, too, by for example tuning the heap region sizes automatically.

 
--
Sebastian Sylvan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Henning Thielemann
In reply to this post by Luke Palmer-2

On Sat, 27 Feb 2010, Luke Palmer 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.

In my experiments with real-time audio signal processing I could always
find a culprit for buffer-underflows other than the garbage collector.
Sometimes it was a space leak (e.g. by adding a finalizer to the wrong
object), sometimes incorrect handling of time differences, and when
working with LLVM it was frequent recompilation of LLVM code.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Thomas Schilling-2
In reply to this post by Job Vranish-2
On 1 March 2010 16:27, Job Vranish <[hidden email]> wrote:
> 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.

Do you really think this is realistic?  Garbage collector aside,
Haskell's execution model is very difficult to predict, which I would
suspect is crucial for even soft real-time systems.  The whole concept
of lazy evaluation seems to run counter to the idea of real-time
systems.  Lazy evaluation essentially says "do as little as possible
*now*" at the expense of having to do it all later.  For a real-time
system you want almost the opposite; you want to make sure that you
complete all the required work in the current time slice.

A possible workaround would be to sprinkle lots of 'rnf's around your
code to make sure you don't build up a thunk or two that will delay
you later.  And if you do this, aren't you essentially programming in
a strict functional language (like SML or O'Caml)?  By careful
profiling you and auditing you can probably rule out most of the
potential bad cases, so it can be acceptable for a soft real-time
system (Galois did something like this, I believe).  But for avionics
systems you probably want to more assurances than that, don't you?

--
Push the envelope.  Watch it bend.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

John Van Enk
The whole concept of lazy evaluation seems to run counter to the idea of real-time systems.

Hi Thomas,

Lazy evaluation is okay since it has deterministic characteristics. We can predict what will happen quite accurately (heck, we can model it in simpler cases). It might take a while to get people comfortable with the concept, but it wouldn't be a show stopper (actually, some people would benefit greatly from lazy evaluation and referential transparency).

The GC throws a wrench in a system which would otherwise make it past certification with enough effort. If we can write a GC that can be modeled, we'd have an excellent case for using Haskell in aerospace.

/jve

On Mon, Mar 1, 2010 at 2:37 PM, Thomas Schilling <[hidden email]> wrote:
On 1 March 2010 16:27, Job Vranish <[hidden email]> wrote:
> 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.

Do you really think this is realistic?  Garbage collector aside,
Haskell's execution model is very difficult to predict, which I would
suspect is crucial for even soft real-time systems.  The whole concept
of lazy evaluation seems to run counter to the idea of real-time
systems.  Lazy evaluation essentially says "do as little as possible
*now*" at the expense of having to do it all later.  For a real-time
system you want almost the opposite; you want to make sure that you
complete all the required work in the current time slice.

A possible workaround would be to sprinkle lots of 'rnf's around your
code to make sure you don't build up a thunk or two that will delay
you later.  And if you do this, aren't you essentially programming in
a strict functional language (like SML or O'Caml)?  By careful
profiling you and auditing you can probably rule out most of the
potential bad cases, so it can be acceptable for a soft real-time
system (Galois did something like this, I believe).  But for avionics
systems you probably want to more assurances than that, don't you?

--
Push the envelope.  Watch it bend.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Job Vranish-2
In reply to this post by Thomas Schilling-2


On Mon, Mar 1, 2010 at 2:37 PM, Thomas Schilling <[hidden email]> wrote:
On 1 March 2010 16:27, Job Vranish <[hidden email]> wrote:
> 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.

A possible workaround would be to sprinkle lots of 'rnf's around your
code to make sure you don't build up a thunk or two that will delay
you later.  And if you do this, aren't you essentially programming in
a strict functional language (like SML or O'Caml)?  By careful
profiling you and auditing you can probably rule out most of the
potential bad cases, so it can be acceptable for a soft real-time
system (Galois did something like this, I believe).  But for avionics
systems you probably want to more assurances than that, don't you?

Yes and no.
It's true that lazy evaluation makes reasoning about timings a bit more difficult (and might not be usable in very time critical scenarios) but it is still has well defined deterministic behavior.

It's the referential transparency that saves us here. If you run a lazy function with the same objects (in the same evaluation state) it should _theoretically_ take the same amount of time to run. All of our toplevel inputs will be strict, and if we keep our frame-to-frame state strick, our variances in runtimes, given the same inputs, should be quite low modulo the GC.

Even our current code can take significantly different amounts of time to compute things depending on what you're doing. Some waypoints take longer to lookup from the database than others. Predicting the time to arrival can take significantly longer/shorter depending on seemingly trivial parameters, etc...

It matters less that code always takes the same amount of time to run (though it needs to always be less than the frame time)  and more so that it always takes the same amount of time to run given the same initial conditions.

- Job

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Neil Davies-2
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.  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.

Neil


On 1 Mar 2010, at 21:06, Job Vranish wrote:



On Mon, Mar 1, 2010 at 2:37 PM, Thomas Schilling <[hidden email]> wrote:
On 1 March 2010 16:27, Job Vranish <[hidden email]> wrote:
> 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.

A possible workaround would be to sprinkle lots of 'rnf's around your
code to make sure you don't build up a thunk or two that will delay
you later.  And if you do this, aren't you essentially programming in
a strict functional language (like SML or O'Caml)?  By careful
profiling you and auditing you can probably rule out most of the
potential bad cases, so it can be acceptable for a soft real-time
system (Galois did something like this, I believe).  But for avionics
systems you probably want to more assurances than that, don't you?

Yes and no.
It's true that lazy evaluation makes reasoning about timings a bit more difficult (and might not be usable in very time critical scenarios) but it is still has well defined deterministic behavior.

It's the referential transparency that saves us here. If you run a lazy function with the same objects (in the same evaluation state) it should _theoretically_ take the same amount of time to run. All of our toplevel inputs will be strict, and if we keep our frame-to-frame state strick, our variances in runtimes, given the same inputs, should be quite low modulo the GC.

Even our current code can take significantly different amounts of time to compute things depending on what you're doing. Some waypoints take longer to lookup from the database than others. Predicting the time to arrival can take significantly longer/shorter depending on seemingly trivial parameters, etc...

It matters less that code always takes the same amount of time to run (though it needs to always be less than the frame time)  and more so that it always takes the same amount of time to run given the same initial conditions.

- Job
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Thomas Schilling-2
On 1 March 2010 21:34, Neil Davies <[hidden email]> 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=10.1.1.30.1219


--
Push the envelope.  Watch it bend.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Jeremy Shaw-3
In reply to this post by Luke Palmer-2
I am just going to jump on the RT dogpile and mention that I too have wanted RT friendly GC in Haskell. I have attempted on more than one occasion to implement real-time audio applications in Haskell. But I tend to get a lot of buffer underruns, most likely due to GC.

For audio apps, there is a callback that happens every few milliseconds. As often as 4ms. The callback needs to finish as quickly as possible to avoid a buffer underruns. So, in theory, I believe I would want garbage collection to only happen in the time periods between when the callback is running. This wouldn't affect the total amount of time that garbage collection ran -- but it would help minimize the amount of time spent in the callback, which should reduce buffer underruns.

My feeling right now is that the 'best' solution might be something similar to synthesis OS. I would create a DSL for the realtime DSP code. Using harpy, this DSL would be compiled to assembly with execution time guarantees (as much as can be predicted on modern hardware). For a 'modular synth' this might actually be better than C code, because the effects of certain choices could be 'compiled in' instead of having to check the setting via a compare. (that is what Synthesis OS does).

- jeremy



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Real-time garbage collection for Haskell

Simon Cranshaw
In reply to this post by Pavel Perikov
On Sun, Feb 28, 2010 at 6:06 PM, Pavel Perikov <[hidden email]> wrote:
Did you really seen 100ms pauses?! I never did extensive research on this but my numbers are rather in microseconds range (below 1ms). What causes such a long garbage collection? Lots of allocated and long-living objects?


I am using an automated options trading system written in Haskell.  I'm more on the business side than the technical side of the issues so I'm not clear on all the details.  I can confirm that without tweaking the RTS settings we were seeing over 100ms GC pauses.  I've mainly been trying to minimise our overall response time and we were able to improve this by increasing the allocation area with -A.  I think this brought GC well under 100ms.  We are still working on analysis of this. 

I can also confirm, as others seem to have found, that under 6.12 the parallel GC seemed to make things much worse. I am always turning it off with -qg.  If there is a project to improve performance of the GC I could be interested to contribute.

Simon Cranshaw

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
123