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

On 01/03/2010 00:04, Luke Palmer wrote:

On Sun, Feb 28, 2010 at 2:06 AM, 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?

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.

By default GHC uses a generational GC with a 512KB nursery size, which means that most GC pauses will be very short but just occasionally you have to do a major GC and there's no upper bound on the pause time for that collection, because the whole live heap is traversed. The pause time for a major collection is proportional to the amount of live data, so the people who are experiencing very short pauses probably have little live data and/or have allocation patterns that means the old generation is collected very infrequently. Monolithic major GC is a big stinking scalability problem, and the only solutions are to do concurrent GC, incremental GC, or region-based GC. Both concurrent GC and incremental GC tend to add overheads to the mutator, because they need a read barrier. There was an incremental GC for GHC once [1], taking advantage of the built-in read barrier that we have whereby most closures are "entered", and it more-or-less worked but was quite complicated and had some code-size overhead. Nowadays part of this built-in read barrier has been eroded by pointer tagging, which makes things a bit more tricky. Region-based GC is a generalisation of generational GC, where you divide the heap into regions and track all pointers between regions, so a given collection can collect any subset of the regions. This basic idea is quite popular amongst the Java people these days, Thomas mentioned the G1 collector which does this and uses a concurrent mark phase to identify which regions to collect. Regardless of how you figure out which regions to collect, the basic idea of breaking up the old generation like this is a good way to reduce pause times. At the moment I'm focussed on something different: making individual processors able to collect their own heaps independently, so removing the stop-the-world requirement from minor GCs. This should help parallel throughput a lot, but won't fix the major GC pause times. I am slightly worried that the GC can't bear the extra complexity of adding both processor-independent GC *and* region-based GC or some other pause-time-reducing technique. But we'll see. I'll happily supervise/mentor anyone who wants to tackle this. Cheers, Simon [1] http://delivery.acm.org/10.1145/360000/351265/p257-cheadle.pdf?key1=351265&key2=8540457621&coll=GUIDE&dl=GUIDE&CFID=80115628&CFTOKEN=59704548