Hello, I'm interested in research relating to memory management in Haskell. I'm at the point where I don't know enough to have very specific questions, but I'm especially interested in garbage collection in Haskell, and any available statistics (such as, how long does a thunk typically live before its evaluated, after its evaluated?), or tools that would let me get that sort of information more easily. If any one could be so kind as to point me to relevant research papers or other documentation, it would be very much appreciated. --Nathan Ricci
nricci01:
Hello,
I'm interested in research relating to memory management in Haskell. I'm at the point where I don't know enough to have very specific questions, but I'm especially interested in garbage collection in Haskell, and any available statistics (such as, how long does a thunk typically live before its evaluated, after its evaluated?), or tools that would let me get that sort of information more easily. If any one could be so kind as to point me to relevant research papers or other documentation, it would be very much appreciated.
Some research papers on GC and Haskell: http://haskell.org/haskellwiki/Research_papers/Runtime_systems#Garbage_colle... Simon Marlow has some recent papers on benchmarking costs in the runtime, http://www.haskell.org/~simonmar/bib/bib.html
2009/8/3 Nathan Ricci <nricci01@eecs.tufts.edu>:
Hello,
I'm interested in research relating to memory management in Haskell. I'm at the point where I don't know enough to have very specific questions, but I'm especially interested in garbage collection in Haskell, and any available statistics (such as, how long does a thunk typically live before its evaluated, after its evaluated?), or tools that would let me get that sort of information more easily. If any one could be so kind as to point me to relevant research papers or other documentation, it would be very much appreciated.
--Nathan Ricci
Hi Nathan, Whilst the work is not about memory management directly, you might find this paper interesting: Feedback Directed Implicit Parallelism Tim Harris and Satnam Singh http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf And maybe have a look at the work on optimistic evaluation in Haskell: Adaptive Evaluation of Non-Strict Programs (PhD thesis) http://berkeley.intel-research.net/rennals/ (there might be some analysis about the life of thunks in those references). Cheers, Bernie.
Nathan,
I'm interested in research relating to memory management in Haskell. I'm at the point where I don't know enough to have very specific questions, but I'm especially interested in garbage collection in Haskell, and any available statistics (such as, how long does a thunk typically live before its evaluated, after its evaluated?), or tools that would let me get that sort of information more easily. If any one could be so kind as to point me to relevant research papers or other documentation, it would be very much appreciated.
In the early to mid '90s we built various heap-profiling tools to examine the characteristics of heap data in lazy functional programs. You can find papers describing this work by Googling "heap profiling". You may be particularly interested in the investigation of "heap lag" and "heap drag" -- see for example the ICFP'96 paper. Others have worked on similar tools since, but I'm not sure how extensive heap profiling facilities are in ghc, the most widely used implementation of Haskell. Regards Colin R
I'm not quite sure how to describe this, but are you aware of any research into converting heap allocations into frames on a stack? For example, many C functions follow this kind of pattern: void doSomeStuff(..) { // allocate required resources int a,b,c; // finite amount of temp allocations on stack int* buffer = malloc(..); // larger (finite) allocation on heap // free resources free(buffer); // free heap allocations // stack allocs popped by compiler. } They key aspect is the amount of memory required is calculatable in advance and allocated/removed in a lump rather than a series of requests. No pointer-tracking/garbage collection is required. I can picture similar situations arising in Haskell where for suitable expressions the compiler could in theory determine that garbage collection would be unnecessary for a lump of temporary data and simply allocate/deallocate when starting/finishing evaluating the thunk. The goal being to simplify garbage collection for this kind of temporary allocation. Any thoughts? Ta, Sam -----Original Message----- From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Colin Runciman Sent: 04 August 2009 12:06 To: Nathan Ricci Cc: Haskell@haskell.org Subject: Re: [Haskell] memory management Nathan,
I'm interested in research relating to memory management in Haskell. I'm at the point where I don't know enough to have very specific questions, but I'm especially interested in garbage
collection
in Haskell, and any available statistics (such as, how long does a thunk typically live before its evaluated, after its evaluated?), or tools that would let me get that sort of information more easily. If any one
could be so kind as to point me to relevant research papers or other documentation, it would be very much appreciated.
In the early to mid '90s we built various heap-profiling tools to examine the characteristics of heap data in lazy functional programs. You can find papers describing this work by Googling "heap profiling". You may be particularly interested in the investigation of "heap lag" and "heap drag" -- see for example the ICFP'96 paper. Others have worked on similar tools since, but I'm not sure how extensive heap profiling facilities are in ghc, the most widely used implementation of Haskell. Regards Colin R _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Tue, Aug 4, 2009 at 7:30 AM, Sam Martin<sam.martin@geomerics.com> wrote:
I can picture similar situations arising in Haskell where for suitable expressions the compiler could in theory determine that garbage collection would be unnecessary for a lump of temporary data and simply allocate/deallocate when starting/finishing evaluating the thunk. The goal being to simplify garbage collection for this kind of temporary allocation.
Any thoughts?
Ta, Sam
Sounds like region inference to me. (https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference) -- gwern
Sounds like region inference to me. (https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference)
Thanks, yes, that's exactly what I had in mind. Is anything like this is done in GHC? Ta, Sam
On 04/08/2009 13:33, Sam Martin wrote:
Sounds like region inference to me. (https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference)
Thanks, yes, that's exactly what I had in mind.
Is anything like this is done in GHC?
Not at the moment, no. Bear in mind that with generational GC, allocating memory that quickly becomes garbage is quite cheap. Cheers, Simon
Hi, staying in the realm of the explicit and pragmatic, various libraries in Haskell do provide safe&explicit region/alloca/stack allocation actions, e.g., Foreign.Marshal.Alloc.allocaBytes :: Int -> (Ptr a -> IO b) -> IO b with the promise that the pointer doesn't escape here (you could constrain this using the type system, if you so wish..) I don't know if the GHC RTS still(?) provides hooks for allocating "alloca" objects specially. There's been some work on monadic regions too; worth looking at. hth --sigbjorn On 8/4/2009 15:49, Simon Marlow wrote:
On 04/08/2009 13:33, Sam Martin wrote:
Sounds like region inference to me. (https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference)
Thanks, yes, that's exactly what I had in mind.
Is anything like this is done in GHC?
Not at the moment, no.
Bear in mind that with generational GC, allocating memory that quickly becomes garbage is quite cheap.
Cheers, Simon
Hello Sigbjorn, Tuesday, August 4, 2009, 6:11:09 PM, you wrote:
this using the type system, if you so wish..) I don't know if the GHC RTS still(?) provides hooks for allocating "alloca" objects specially.
it's allocated as usual object, these are cheap anyway as far as it freed before minor GC occurs (which is called after each 512kb allocated, by default) afair, jhc uses region inference -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On Tue, Aug 4, 2009 at 2:49 PM, Simon Marlow <marlowsd@gmail.com> wrote:
On 04/08/2009 13:33, Sam Martin wrote:
Sounds like region inference to me.
(https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference)
Thanks, yes, that's exactly what I had in mind.
Is anything like this is done in GHC?
Not at the moment, no.
Bear in mind that with generational GC, allocating memory that quickly becomes garbage is quite cheap.
Speculation time... I have no real basis for this, and I'm quite possibly overlooking a lot of details... There may be other benefits to doing this kind of escape-analysis, aside from making short-lived allocations cheaper (which are indeed already quite cheap)... If you can associate a bunch of allocations with a point in the stack, even if it's very low in the stack (and thus long-lived), there's a lot less work that the GC needs to do to track all the other allocations (in the global heap), since there's just fewer of them. Also, each stack is associated with a specific thread, so it sort of brings you half-way to per-thread GC, in the sense that all the stack-based resource management is per-thread. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862
Also region inference is likely to be much less effective in a lazy language, because (I think that) data escapes the lifetime of its allocating procedure much more often. I don't know of any work that has even tried it. Simon | -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On | Behalf Of Simon Marlow | Sent: 04 August 2009 14:50 | To: Sam Martin | Cc: Colin Runciman; Haskell@haskell.org | Subject: Re: [Haskell] memory management | | On 04/08/2009 13:33, Sam Martin wrote: | >> Sounds like region inference to me. | >> (https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference) | > | > Thanks, yes, that's exactly what I had in mind. | > | > Is anything like this is done in GHC? | | Not at the moment, no. | | Bear in mind that with generational GC, allocating memory that quickly | becomes garbage is quite cheap. | | Cheers, | Simon | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell
I can see how laziness works against this, and agree it's probably not suitable for most lazy code. Generational GC does sound much more appropriate. But fair chunks of Haskell code can be known to be strict. Either from analysis of the code, or explicit instruction by the programmer. (I also have nested data parallelism in the back of my mind for some reason.) I'd risk a bet that these areas of code are probably your 'inner loops' and hence areas a programmer wouldn't want allocation/deallocation to occur unless absolutely necessary. Isn't region inference an attractive option for these situations? Cheers, Sam -----Original Message----- From: Simon Peyton-Jones [mailto:simonpj@microsoft.com] Sent: 06 August 2009 08:23 To: Simon Marlow; Sam Martin Cc: Colin Runciman; Haskell@haskell.org Subject: RE: [Haskell] memory management Also region inference is likely to be much less effective in a lazy language, because (I think that) data escapes the lifetime of its allocating procedure much more often. I don't know of any work that has even tried it. Simon | -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On | Behalf Of Simon Marlow | Sent: 04 August 2009 14:50 | To: Sam Martin | Cc: Colin Runciman; Haskell@haskell.org | Subject: Re: [Haskell] memory management | | On 04/08/2009 13:33, Sam Martin wrote: | >> Sounds like region inference to me. | >> (https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference) | > | > Thanks, yes, that's exactly what I had in mind. | > | > Is anything like this is done in GHC? | | Not at the moment, no. | | Bear in mind that with generational GC, allocating memory that quickly | becomes garbage is quite cheap. | | Cheers, | Simon | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell
Meacham's JHC was headed towards region inference for a while (and may still be), and I spent some time trying to use region inference in a research compiler of my own, and I think both projects effectively came to that same conclusion -- regions and laziness don't mix. Finding useful regions in a lazy language is hard. You can't effectively annotate them in the source due to laziness decoupling object lifetimes from that of your source stack frames, so you need to infer them once you've translated into some strict intermediate representation, and the regions you can infer are finicky and brittle at best. Region-based code optimization in ML tends to center around identifying which region is leaking and why, and without any sort of source code tie for the region system, that becomes a seriously black box. Thunks tend to hold onto lots of context, so minor source changes yield vastly different region profiles. Finally, all of the effort is called into question by the fact that regions alone can't even handle a lot of interesting cases, so you need a collector to boot. Tofte et al. wrote a retrospective at some point basically talking about the now-known limitations of region based memory management [ http://portal.acm.org/citation.cfm?id=993040 , pre-print: http://www.elsman.com/retro.pdf], which I think has the right balance of optimism and pragmatism where it comes to region-based memory management and talks about many of these issues. -Edward Kmett On Thu, Aug 6, 2009 at 3:22 AM, Simon Peyton-Jones <simonpj@microsoft.com>wrote:
Also region inference is likely to be much less effective in a lazy language, because (I think that) data escapes the lifetime of its allocating procedure much more often. I don't know of any work that has even tried it.
Simon
| -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On | Behalf Of Simon Marlow | Sent: 04 August 2009 14:50 | To: Sam Martin | Cc: Colin Runciman; Haskell@haskell.org | Subject: Re: [Haskell] memory management | | On 04/08/2009 13:33, Sam Martin wrote: | >> Sounds like region inference to me. | >> (https://secure.wikimedia.org/wikipedia/en/wiki/Region_inference) | > | > Thanks, yes, that's exactly what I had in mind. | > | > Is anything like this is done in GHC? | | Not at the moment, no. | | Bear in mind that with generational GC, allocating memory that quickly | becomes garbage is quite cheap. | | Cheers, | Simon | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
| In the early to mid '90s we built various heap-profiling tools to | examine the characteristics of heap data in lazy functional programs. | You can find papers describing this work by Googling "heap profiling". | You may be particularly interested in the investigation of "heap lag" | and "heap drag" -- see for example the ICFP'96 paper. Others have | worked on similar tools since, but I'm not sure how extensive heap | profiling facilities are in ghc, the most widely used implementation of | Haskell. GHC has pretty good heap profiling, including lag/drag/void. I hope they are still working smoothly, although I don't think they have received much love recently. Simon
On 06/08/2009 08:22, Simon Peyton-Jones wrote:
| In the early to mid '90s we built various heap-profiling tools to | examine the characteristics of heap data in lazy functional programs. | You can find papers describing this work by Googling "heap profiling". | You may be particularly interested in the investigation of "heap lag" | and "heap drag" -- see for example the ICFP'96 paper. Others have | worked on similar tools since, but I'm not sure how extensive heap | profiling facilities are in ghc, the most widely used implementation of | Haskell.
GHC has pretty good heap profiling, including lag/drag/void. I hope they are still working smoothly, although I don't think they have received much love recently.
The lag/drag/void stuff (aka biographical profiling) was a bit broken for a while after pointer tagging was introduced, but should be fine now. Cheers, Simon
participants (12)
-
Bernie Pope -
Bulat Ziganshin -
Colin Runciman -
Don Stewart -
Edward Kmett -
Gwern Branwen -
Nathan Ricci -
Sam Martin -
Sebastian Sylvan -
Sigbjorn Finne -
Simon Marlow -
Simon Peyton-Jones