Re: [Haskell-cafe] Real-time garbage collection for Haskell
On 2010-03-05 10:50 +0100 (Fri), Henning Thielemann wrote: Curt Sampson schrieb: Understanding the general techniques for this sort of thing and seeing where you're likely to need to apply them isn't all that difficult, once you understand the problem. (It's probably much easier if you don't have to work it out all for yourself, as I did. Someone needs to write the how to manage lazyness in Haskell guide.) My attempt in this direction: http://www.haskell.org/haskellwiki/Laziness_is_not_always_good http://www.haskell.org/haskellwiki/Maintaining_laziness Unfortunately, neither of these address the problem of the day-to-day programmer: what are the typical ways I introduce space leaks, and how do I stop doing that? cjs -- Curt Sampson c...@cynic.net +81 90 7737 2974 http://www.starling-software.com The power of accurate observation is commonly called cynicism by those who have not got it.--George Bernard Shaw ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
Curt Sampson schrieb: Understanding the general techniques for this sort of thing and seeing where you're likely to need to apply them isn't all that difficult, once you understand the problem. (It's probably much easier if you don't have to work it out all for yourself, as I did. Someone needs to write the how to manage lazyness in Haskell guide.) My attempt in this direction: http://www.haskell.org/haskellwiki/Laziness_is_not_always_good http://www.haskell.org/haskellwiki/Maintaining_laziness ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On 2010-03-02 11:33 +0900 (Tue), Simon Cranshaw wrote: I can confirm that without tweaking the RTS settings we were seeing over 100ms GC pauses. Actually, we can't quite confirm that yet. We're seeing large amounts of time go by in our main trading loop, but I'm still building the profiling tools to see what exactly is going on there. However, GC is high on our list of suspects, since twiddling the GC parameters can improve things drastically. On 2010-03-02 00:06 -0500 (Tue), John Van Enk wrote: Would a more predictable GC or a faster GC be better in your case? (Of course, both would be nice.) Well, as on 2010-03-01 17:18 -0600 (Mon), Jeremy Shaw wrote: 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. I think we're in about the same position. Ideally we'd never have to stop for GC, but that's obviously not practical; what will hurt pretty badly, and we should be able to prevent, is us gathering up a bunch of market data, making a huge pause for a big GC, and then generating orders based on that now oldish market data. We'd be far better off doing the GC first, and then looking at the state of the market and doing our thing, because though the orders will still not get out as quickly as they would without the GC, at least they'll be using more recent data. I tried invoking System.Mem.performGC at the start of every loop, but that didn't help. Now that I know it was invoking a major GC, I can see why. :-) But really, before I go much further with this: On 2010-03-01 14:41 +0100 (Mon), Peter Verswyvelen wrote: Sounds like we need to come up with some benchmarking programs so we can measure the GC latency and soft-realtimeness... Exactly. Right now I'm working from logs made by my own logging and profiling system. These are timestamped, and they're good enough to get a sense of what's going on, but incomplete. I also have the information from the new event logging system, which is excellent in terms of knowing exactly when things are starting and stopping, but doesn't include information about my program, nor does it include any sort of GC stats. Then we have the GC statistics we get with -S, which don't have timestamps. My plan is to bring all of this together. The first step was to fix GHC.Exts.traceEvent so that we can use that to report information about what the application is doing. In 6.12.1 it segfaults, but we have a fix (see http://hackage.haskell.org/trac/ghc/ticket/3874) and it looks as if it will go into 6.12.2, even. The next step is to start recording the information generated by -S in the eventlog as well, so that not only do we know when a GC started or stopped in relation to our application code, but we know what generation it was, how big the heap was at the time, how much was collected, and so on and so forth. Someone mentioned that there were various other stats that were collected but not printed by -S; we should probably throw those in too. With all of that information it should be much easier to figure out where and when GC behaviour is causing us pain in low-latency applications. However: now that Simon's spent a bunch of time experimenting with the runtime's GC settings and found a set that's mitigated much of our problem, other things are pushing their way up my priority list. Between that and an upcoming holiday, I'm probably not going to get back to this for a few weeks. But I'd be happy to discuss my ideas with anybody else who's interested in similar things, even if just to know what would be useful to others. What do you guys think about setting up a separate mailing list for this? I have to admit, I don't follow haskell-cafe much due to the high volume of the list. (Thus my late presence in this thread.) I would be willing to keep much closer track of a low-volume list that dealt with only GC stuff. I'd even be open to providing hosting for the list, using my little baby mailing list manager written in Haskell (mhailist). It's primitive, but it does handle subscribing, unsubscribing and forwarding of messages. cjs -- Curt Sampson c...@cynic.net +81 90 7737 2974 http://www.starling-software.com The power of accurate observation is commonly called cynicism by those who have not got it.--George Bernard Shaw ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
cjs: On 2010-03-01 19:37 + (Mon), Thomas Schilling wrote: A possible workaround would be to sprinkle lots of 'rnf's around your code As I learned rather to my chagrin on a large project, you generally don't want to do that. I spent a couple of days writing instance of NFData and loading up my application with rnfs and then watched performance fall into a sinkhole. I believe that the problem is that rnf traverses the entirety of a large data structure even if it's already strict and doesn't need traversal. My guess is that doing this frequently on data structures (such as Maps) of less than tiny size was blowing out my cache. And rnf will do the traversal whether it is needed or not. Imo, it is better to ensure the structures you want are necessarily strict by definition, so that only the minimum additional evaluation is necessary. 'rnf' really is a hammer, but not everything is a nail. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On Thu, Mar 4, 2010 at 11:10 AM, Don Stewart d...@galois.com wrote: cjs: On 2010-03-01 19:37 + (Mon), Thomas Schilling wrote: A possible workaround would be to sprinkle lots of 'rnf's around your code As I learned rather to my chagrin on a large project, you generally don't want to do that. I spent a couple of days writing instance of NFData and loading up my application with rnfs and then watched performance fall into a sinkhole. I believe that the problem is that rnf traverses the entirety of a large data structure even if it's already strict and doesn't need traversal. My guess is that doing this frequently on data structures (such as Maps) of less than tiny size was blowing out my cache. And rnf will do the traversal whether it is needed or not. Imo, it is better to ensure the structures you want are necessarily strict by definition, so that only the minimum additional evaluation is necessary. Isn't the downside of strict structures the implicit nature of the 'strictification'? You lose the fine grained control of when particular values should be strict. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
Sorry, no. We wanted a basic bound on the jitter - the application is not one that creates much (if any) long lived heap. Having just seen Simon's email on the fact that performGC forces a major GC - i think that there is some new mileage here with making the speculative GC's minor ones. More control needs some more instrumentation of how much mutation is occurring and ways of estimating how much of that is short and long lived - I know that past history is not necessarily a good indicator of future actions - but visibility of the counters that being kept would help. Neil On 3 Mar 2010, at 00:00, Jason Dusek wrote: 2010/02/28 Neil Davies semanticphilosop...@googlemail.com: 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. Do you have information on how it behaves without speculative GC? -- Jason Dusek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On Monday 01 March 2010 03:16:25 pm Sönke Hahn wrote: 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. FYI: These high frame times were caused by a space leak. With the help of the excellent hp2any-manager i found that out and where to put the needed strictness annotations. Sönke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
Jeremy Shaw schrieb: 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). I'm currently doing this with LLVM - which is more portable and better optimizing than a plain X86 assembler: http://code.haskell.org/synthesizer/llvm/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On 2010-03-01 19:37 + (Mon), Thomas Schilling wrote: A possible workaround would be to sprinkle lots of 'rnf's around your code As I learned rather to my chagrin on a large project, you generally don't want to do that. I spent a couple of days writing instance of NFData and loading up my application with rnfs and then watched performance fall into a sinkhole. I believe that the problem is that rnf traverses the entirety of a large data structure even if it's already strict and doesn't need traversal. My guess is that doing this frequently on data structures (such as Maps) of less than tiny size was blowing out my cache. I switched strategies to forcing a deep(ish) evaluation of only newly constructed data instead. For example, after inserting a newly constructed object into a Map, I would look it up and force evaluation only of the result of that lookup. That solved my space leak problem and made things chug along quite nicely. Understanding the general techniques for this sort of thing and seeing where you're likely to need to apply them isn't all that difficult, once you understand the problem. (It's probably much easier if you don't have to work it out all for yourself, as I did. Someone needs to write the how to manage lazyness in Haskell guide.) The difficult part of it is that you've really got to stay on top of it, because if you don't, the space leaks come back and you have to go find them again. It feels a little like dealing with buffers and their lengths in C. On 2010-03-01 16:06 -0500 (Mon), Job Vranish wrote: 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. This is exactly the approach I need to take for the trading system. I basically have various (concurrent) loops that process input, update state, and possibly generate output. The system runs for about six hours, processing five million or so input messages with other loops running anywhere from hundreds of thousands to millions of times. The trick is to make sure that I never, ever start a new loop with an unevaluated thunk referring to data needed only by the previous loop, because otherwise I just grow and grow and grow Some tool to help with this would be wonderful. There's something for y'all to think about. On 2010-03-01 22:01 + (Mon), Thomas Schilling wrote: 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 I mentioned above, overall I find them so. Any individual space leak you're looking at is easy to fix, but the constant vigilance is difficult. cjs -- Curt Sampson c...@cynic.net +81 90 7737 2974 http://www.starling-software.com The power of accurate observation is commonly called cynicism by those who have not got it.--George Bernard Shaw ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
2010/02/28 Neil Davies semanticphilosop...@googlemail.com: 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. Do you have information on how it behaves without speculative GC? -- Jason Dusek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 lrpal...@gmail.com wrote: On Sun, Feb 28, 2010 at 2:06 AM, Pavel Perikov peri...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On Monday 01 March 2010 01:04:37 am Luke Palmer wrote: On Sun, Feb 28, 2010 at 2:06 AM, Pavel Perikov peri...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On 28 February 2010 05:20, Luke Palmer lrpal...@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 nomin...@googlemail.comwrote: On 28 February 2010 05:20, Luke Palmer lrpal...@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On Sun, Feb 28, 2010 at 5:20 AM, Luke Palmer lrpal...@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. 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On 1 March 2010 16:27, Job Vranish job.vran...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 nomin...@googlemail.comwrote: On 1 March 2010 16:27, Job Vranish job.vran...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On Mon, Mar 1, 2010 at 2:37 PM, Thomas Schilling nomin...@googlemail.comwrote: On 1 March 2010 16:27, Job Vranish job.vran...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 nomin...@googlemail.com wrote: On 1 March 2010 16:27, Job Vranish job.vran...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On 1 March 2010 21:34, Neil Davies semanticphilosop...@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=10.1.1.30.1219 -- Push the envelope. Watch it bend. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On Sun, Feb 28, 2010 at 6:06 PM, Pavel Perikov peri...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
Simon, Would a more predictable GC or a faster GC be better in your case? (Of course, both would be nice.) /jve On Mon, Mar 1, 2010 at 9:33 PM, Simon Cranshaw simon.crans...@gmail.comwrote: On Sun, Feb 28, 2010 at 6:06 PM, Pavel Perikov peri...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
John, I suspect speed is more important than timing. In practice I don't mind a pause for a gc when nothing is happening in the market. It's when the market is moving fast that we particularly want to keep our response time low. Busy times may continue for long periods though and I'm not sure if being able to defer gc (if that's what you're suggesting) would be possible for that long. We are still studying how the gc times are interacting with our response times and so hopefully I will have a better answer to this later on. Simon On Tue, Mar 2, 2010 at 2:06 PM, John Van Enk vane...@gmail.com wrote: Simon, Would a more predictable GC or a faster GC be better in your case? (Of course, both would be nice.) /jve On Mon, Mar 1, 2010 at 9:33 PM, Simon Cranshaw simon.crans...@gmail.comwrote: On Sun, Feb 28, 2010 at 6:06 PM, Pavel Perikov peri...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Real-time garbage collection for Haskell
On Sun, Feb 28, 2010 at 2:06 AM, Pavel Perikov peri...@gmail.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Real-time garbage collection for Haskell
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
