<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0cm;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
p
        {mso-style-priority:99;
        mso-margin-top-alt:auto;
        margin-right:0cm;
        mso-margin-bottom-alt:auto;
        margin-left:0cm;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
span.EmailStyle18
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page Section1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.Section1
        {page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-GB link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>The GC discards an MVar when there are only <b>blocked</b>
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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Your idea of splitting the MVar into two halves, a read end and
a write end, might well improve this situation somewhat.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Simon<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<div style='border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt'>
<div>
<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'>
<p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:
"Tahoma","sans-serif"'>From:</span></b><span lang=EN-US style='font-size:10.0pt;
font-family:"Tahoma","sans-serif"'> conal.elliott@gmail.com
[mailto:conal.elliott@gmail.com] <b>On Behalf Of </b>Conal Elliott<br>
<b>Sent:</b> 24 December 2007 18:49<br>
<b>To:</b> Simon Peyton-Jones<br>
<b>Cc:</b> haskell@haskell.org<br>
<b>Subject:</b> Re: [Haskell] garbage collection of Concurrent Haskell threads?<o:p></o:p></span></p>
</div>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal style='margin-bottom:12.0pt'>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? <br>
<br>
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. <br>
<br>
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? <br>
<br>
Cheers, - Conal<o:p></o:p></p>
<div>
<p class=MsoNormal>On Dec 24, 2007 1:02 AM, Simon Peyton-Jones <<a
href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>> wrote:<o:p></o:p></p>
<div>
<div>
<p><span lang=EN-US style='font-size:11.0pt;color:#1F497D'>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. </span><span lang=EN-US><o:p></o:p></span></p>
<p><span lang=EN-US style='font-size:11.0pt;color:#1F497D'> </span><span
lang=EN-US><o:p></o:p></span></p>
<p><span lang=EN-US style='font-size:11.0pt;color:#1F497D'>So perhaps the GC
you want is already implemented?<br>
<br>
Simon</span><span lang=EN-US><o:p></o:p></span></p>
<p><span lang=EN-US style='font-size:11.0pt;color:#1F497D'> </span><span
lang=EN-US><o:p></o:p></span></p>
<div style='border:none;border-left:solid windowtext 1.5pt;padding:0cm 0cm 0cm 4.0pt;
border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color blue'>
<div>
<div style='border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0cm 0cm 0cm;
border-color:-moz-use-text-color -moz-use-text-color'>
<p><b><span lang=EN-US style='font-size:10.0pt'>From:</span></b><span
lang=EN-US style='font-size:10.0pt'> <a
href="mailto:haskell-bounces@haskell.org" target="_blank">haskell-bounces@haskell.org</a>
[mailto:<a href="mailto:haskell-bounces@haskell.org" target="_blank">haskell-bounces@haskell.org</a>]
<b>On Behalf Of </b>Conal Elliott<br>
<b>Sent:</b> 24 December 2007 00:15<br>
<b>To:</b> <a href="mailto:haskell@haskell.org" target="_blank">haskell@haskell.org</a><br>
<b>Subject:</b> [Haskell] garbage collection of Concurrent Haskell threads?</span><span
lang=EN-US><o:p></o:p></span></p>
</div>
</div>
<div>
<p><span lang=EN-US> <o:p></o:p></span></p>
<p style='margin-bottom:12.0pt'><span lang=EN-US>The classic paper "The
Incremental Garbage Collection of Processes" (<a
href="http://citeseer.ist.psu.edu/baker77incremental.html" target="_blank">http://citeseer.ist.psu.edu/baker77incremental.html</a>)
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 ( <a
href="http://haskell.org/haskellwiki/Reactive" target="_blank">http://haskell.org/haskellwiki/Reactive</a>),
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)?<br>
<br>
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. <br>
<br>
Thanks, - Conal<br>
<br>
<o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
</div>
</body>
</html>