garbage collection of Concurrent Haskell threads?
The classic paper "The Incremental Garbage Collection of Processes" ( http://citeseer.ist.psu.edu/baker77incremental.html) describes "futures" and how particularly garbage collecting them when their pending result is no longer referenced. I've been playing with an implementation of futures in Concurrent Haskell (http://haskell.org/haskellwiki/Reactive), using MVars, and I'm stumped about how to GC non-winning threads in a race between futures ("parallel or"). I'm having winner kill loser, which seems to work fine, though is potentially dangerous w.r.t locked resources. Still, the elegance of a GC-based solution appeals to me. Has anyone explored process GC ideas for Concurrent Haskell (or STM)? Futures are implemented using Concurrent Haskell's MVars. I first tried using STM and TVars, simply using orElse to implement mappend for futures. However, I didn't see how to avoid nesting "atomically", which yielded a run-time error. If anyone has ideas about using STM & TVars for futures, I'd love to hear. Thanks, - Conal
GHC already garbage-collects threads that are blocked on an MVar that is otherwise inaccessible (and hence cannot be updated). More precisely, GHC sends the thread an asynchronous exception (ThreadBlocked or something), so that it has a chance to clean up. So perhaps the GC you want is already implemented? Simon From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Conal Elliott Sent: 24 December 2007 00:15 To: haskell@haskell.org Subject: [Haskell] garbage collection of Concurrent Haskell threads? The classic paper "The Incremental Garbage Collection of Processes" (http://citeseer.ist.psu.edu/baker77incremental.html) describes "futures" and how particularly garbage collecting them when their pending result is no longer referenced. I've been playing with an implementation of futures in Concurrent Haskell ( http://haskell.org/haskellwiki/Reactive), using MVars, and I'm stumped about how to GC non-winning threads in a race between futures ("parallel or"). I'm having winner kill loser, which seems to work fine, though is potentially dangerous w.r.t locked resources. Still, the elegance of a GC-based solution appeals to me. Has anyone explored process GC ideas for Concurrent Haskell (or STM)? Futures are implemented using Concurrent Haskell's MVars. I first tried using STM and TVars, simply using orElse to implement mappend for futures. However, I didn't see how to avoid nesting "atomically", which yielded a run-time error. If anyone has ideas about using STM & TVars for futures, I'd love to hear. Thanks, - Conal
Thanks, Simon. If I understand the mechanism you're describing, it discards readers of an empty MVar when there are no other references to the MVar *because* the MVar can never get written. And if there are other readers but no writers, then I'm guessing GC wouldn't know that, and none of the readers get discarded. Is that so? I think Baker & Hewitt's trick was analogous to discarding writers of an already full MVar when there are readers (readMVar) but no takers (takeMVar). (Though not quite, since readMVar is implemented via takeMVar & putMVar.) I guess that effectively means IVars instead of MVars. In either direction (blocked reader or blocked writer), the interface of MVars (or IVars) would seem to prevent an accurate analysis, since GC wouldn't know whether a Var reference was for reading or writing. Right? A simple solution might be to hide the Var itself and instead expose reader and writer halves. If there's an analysis problem at all, does that solution make sense? Cheers, - Conal On Dec 24, 2007 1:02 AM, Simon Peyton-Jones <simonpj@microsoft.com> wrote:
GHC already garbage-collects threads that are blocked on an MVar that is otherwise inaccessible (and hence cannot be updated). More precisely, GHC sends the thread an asynchronous exception (ThreadBlocked or something), so that it has a chance to clean up.
So perhaps the GC you want is already implemented?
Simon
*From:* haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] *On Behalf Of *Conal Elliott *Sent:* 24 December 2007 00:15 *To:* haskell@haskell.org *Subject:* [Haskell] garbage collection of Concurrent Haskell threads?
The classic paper "The Incremental Garbage Collection of Processes" ( http://citeseer.ist.psu.edu/baker77incremental.html) describes "futures" and how particularly garbage collecting them when their pending result is no longer referenced. I've been playing with an implementation of futures in Concurrent Haskell ( http://haskell.org/haskellwiki/Reactive), using MVars, and I'm stumped about how to GC non-winning threads in a race between futures ("parallel or"). I'm having winner kill loser, which seems to work fine, though is potentially dangerous w.r.t locked resources. Still, the elegance of a GC-based solution appeals to me. Has anyone explored process GC ideas for Concurrent Haskell (or STM)?
Futures are implemented using Concurrent Haskell's MVars. I first tried using STM and TVars, simply using orElse to implement mappend for futures. However, I didn't see how to avoid nesting "atomically", which yielded a run-time error. If anyone has ideas about using STM & TVars for futures, I'd love to hear.
Thanks, - Conal
The GC discards an MVar when there are only blocked readers on it. But there can be any number of blocked readers. So long as the read remains in the future, however, the GC doesn't recover it, because it has no way to know that the thread will only read it and not write it. Your idea of splitting the MVar into two halves, a read end and a write end, might well improve this situation somewhat. But, like finalisers, it's dangerous to rely on reachability arguments for anything that's really important. Boehm's article on finalisers explains why. My guess is that the same remarks would apply to MVars. Simon From: conal.elliott@gmail.com [mailto:conal.elliott@gmail.com] On Behalf Of Conal Elliott Sent: 24 December 2007 18:49 To: Simon Peyton-Jones Cc: haskell@haskell.org Subject: Re: [Haskell] garbage collection of Concurrent Haskell threads? Thanks, Simon. If I understand the mechanism you're describing, it discards readers of an empty MVar when there are no other references to the MVar *because* the MVar can never get written. And if there are other readers but no writers, then I'm guessing GC wouldn't know that, and none of the readers get discarded. Is that so? I think Baker & Hewitt's trick was analogous to discarding writers of an already full MVar when there are readers (readMVar) but no takers (takeMVar). (Though not quite, since readMVar is implemented via takeMVar & putMVar.) I guess that effectively means IVars instead of MVars. In either direction (blocked reader or blocked writer), the interface of MVars (or IVars) would seem to prevent an accurate analysis, since GC wouldn't know whether a Var reference was for reading or writing. Right? A simple solution might be to hide the Var itself and instead expose reader and writer halves. If there's an analysis problem at all, does that solution make sense? Cheers, - Conal On Dec 24, 2007 1:02 AM, Simon Peyton-Jones <simonpj@microsoft.com<mailto:simonpj@microsoft.com>> wrote: GHC already garbage-collects threads that are blocked on an MVar that is otherwise inaccessible (and hence cannot be updated). More precisely, GHC sends the thread an asynchronous exception (ThreadBlocked or something), so that it has a chance to clean up. So perhaps the GC you want is already implemented? Simon From: haskell-bounces@haskell.org<mailto:haskell-bounces@haskell.org> [mailto:haskell-bounces@haskell.org<mailto:haskell-bounces@haskell.org>] On Behalf Of Conal Elliott Sent: 24 December 2007 00:15 To: haskell@haskell.org<mailto:haskell@haskell.org> Subject: [Haskell] garbage collection of Concurrent Haskell threads? The classic paper "The Incremental Garbage Collection of Processes" (http://citeseer.ist.psu.edu/baker77incremental.html) describes "futures" and how particularly garbage collecting them when their pending result is no longer referenced. I've been playing with an implementation of futures in Concurrent Haskell ( http://haskell.org/haskellwiki/Reactive), using MVars, and I'm stumped about how to GC non-winning threads in a race between futures ("parallel or"). I'm having winner kill loser, which seems to work fine, though is potentially dangerous w.r.t locked resources. Still, the elegance of a GC-based solution appeals to me. Has anyone explored process GC ideas for Concurrent Haskell (or STM)? Futures are implemented using Concurrent Haskell's MVars. I first tried using STM and TVars, simply using orElse to implement mappend for futures. However, I didn't see how to avoid nesting "atomically", which yielded a run-time error. If anyone has ideas about using STM & TVars for futures, I'd love to hear. Thanks, - Conal
Hello Simon, For the record: I assume that by "Boehm's article on finalisers" you mean: @inproceedings{DBLP <http://www.informatik.uni-trier.de/%7Eley/db/about/bibtex.html> :conf/popl/Boehm03, author = {Hans-Juergen Boehm}, title = {Destructors, finalizers, and synchronization}, booktitle = {POPL}, year = {2003}, pages = {262-272}, ee = {http://doi.acm.org/10.1145/640128.604153}, bibsource = {DBLP, http://dblp.uni-trier.de} } (which is also at http://citeseer.ist.psu.edu/boehm03destructors.html)? Groetjes, <>< Marnix -- Marnix Klooster | Software Engineer, ERP LN Enterprise Server | Infor | (+31 or 0)342-428511 | marnix.klooster@infor.com | Infor Global Solutions (Barneveld) BV | P.O. box 143 | 3770 AC Barneveld | The Netherlands ________________________________ From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Simon Peyton-Jones Sent: Thursday, 3 January, 2008 14:13 To: Conal Elliott Cc: haskell@haskell.org Subject: RE: [Haskell] garbage collection of Concurrent Haskell threads? The GC discards an MVar when there are only blocked readers on it. But there can be any number of blocked readers. So long as the read remains in the future, however, the GC doesn't recover it, because it has no way to know that the thread will only read it and not write it. Your idea of splitting the MVar into two halves, a read end and a write end, might well improve this situation somewhat. But, like finalisers, it's dangerous to rely on reachability arguments for anything that's really important. Boehm's article on finalisers explains why. My guess is that the same remarks would apply to MVars. Simon From: conal.elliott@gmail.com [mailto:conal.elliott@gmail.com] On Behalf Of Conal Elliott Sent: 24 December 2007 18:49 To: Simon Peyton-Jones Cc: haskell@haskell.org Subject: Re: [Haskell] garbage collection of Concurrent Haskell threads? Thanks, Simon. If I understand the mechanism you're describing, it discards readers of an empty MVar when there are no other references to the MVar *because* the MVar can never get written. And if there are other readers but no writers, then I'm guessing GC wouldn't know that, and none of the readers get discarded. Is that so? I think Baker & Hewitt's trick was analogous to discarding writers of an already full MVar when there are readers (readMVar) but no takers (takeMVar). (Though not quite, since readMVar is implemented via takeMVar & putMVar.) I guess that effectively means IVars instead of MVars. In either direction (blocked reader or blocked writer), the interface of MVars (or IVars) would seem to prevent an accurate analysis, since GC wouldn't know whether a Var reference was for reading or writing. Right? A simple solution might be to hide the Var itself and instead expose reader and writer halves. If there's an analysis problem at all, does that solution make sense? Cheers, - Conal On Dec 24, 2007 1:02 AM, Simon Peyton-Jones <simonpj@microsoft.com> wrote: GHC already garbage-collects threads that are blocked on an MVar that is otherwise inaccessible (and hence cannot be updated). More precisely, GHC sends the thread an asynchronous exception (ThreadBlocked or something), so that it has a chance to clean up. So perhaps the GC you want is already implemented? Simon From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Conal Elliott Sent: 24 December 2007 00:15 To: haskell@haskell.org Subject: [Haskell] garbage collection of Concurrent Haskell threads? The classic paper "The Incremental Garbage Collection of Processes" (http://citeseer.ist.psu.edu/baker77incremental.html) describes "futures" and how particularly garbage collecting them when their pending result is no longer referenced. I've been playing with an implementation of futures in Concurrent Haskell ( http://haskell.org/haskellwiki/Reactive), using MVars, and I'm stumped about how to GC non-winning threads in a race between futures ("parallel or"). I'm having winner kill loser, which seems to work fine, though is potentially dangerous w.r.t locked resources. Still, the elegance of a GC-based solution appeals to me. Has anyone explored process GC ideas for Concurrent Haskell (or STM)? Futures are implemented using Concurrent Haskell's MVars. I first tried using STM and TVars, simply using orElse to implement mappend for futures. However, I didn't see how to avoid nesting "atomically", which yielded a run-time error. If anyone has ideas about using STM & TVars for futures, I'd love to hear. Thanks, - Conal
participants (3)
-
Conal Elliott -
Marnix Klooster -
Simon Peyton-Jones