<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML xmlns="http://www.w3.org/TR/REC-html40" 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"><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2900.3199" name=GENERATOR>
<STYLE>@font-face {
        font-family: Calibri;
}
@font-face {
        font-family: Tahoma;
}
@page Section1 {size: 612.0pt 792.0pt; margin: 72.0pt 72.0pt 72.0pt 72.0pt; }
P.MsoNormal {
        FONT-SIZE: 12pt; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman","serif"
}
LI.MsoNormal {
        FONT-SIZE: 12pt; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman","serif"
}
DIV.MsoNormal {
        FONT-SIZE: 12pt; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman","serif"
}
A:link {
        COLOR: blue; TEXT-DECORATION: underline; mso-style-priority: 99
}
SPAN.MsoHyperlink {
        COLOR: blue; TEXT-DECORATION: underline; mso-style-priority: 99
}
A:visited {
        COLOR: purple; TEXT-DECORATION: underline; mso-style-priority: 99
}
SPAN.MsoHyperlinkFollowed {
        COLOR: purple; TEXT-DECORATION: underline; mso-style-priority: 99
}
P {
        FONT-SIZE: 12pt; MARGIN-LEFT: 0cm; MARGIN-RIGHT: 0cm; FONT-FAMILY: "Times New Roman","serif"; mso-style-priority: 99; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto
}
SPAN.EmailStyle18 {
        COLOR: #1f497d; FONT-FAMILY: "Calibri","sans-serif"; mso-style-type: personal-reply
}
.MsoChpDefault {
        mso-style-type: export-only
}
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 vLink=purple link=blue>
<DIV>
<DIV><SPAN class=161195114-03012008><FONT face=Arial color=#0000ff size=2>Hello
Simon,</FONT></SPAN></DIV>
<DIV><SPAN class=161195114-03012008><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=161195114-03012008><FONT face=Arial color=#0000ff size=2>For
the record: I assume that by "<FONT color=#1f497d size=3>Boehm’s article on
finalisers</FONT>" you mean:</FONT></SPAN></DIV>
<DIV><SPAN class=161195114-03012008><PRE>@inproceedings{<A title=http://www.informatik.uni-trier.de/~ley/db/about/bibtex.html href="http://www.informatik.uni-trier.de/%7Eley/db/about/bibtex.html">DBLP</A>: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}
}</PRE></SPAN></DIV>
<DIV><SPAN class=161195114-03012008><FONT face=Arial color=#0000ff size=2>(which
is also at <A title=http://citeseer.ist.psu.edu/boehm03destructors.html
href="http://citeseer.ist.psu.edu/boehm03destructors.html">http://citeseer.ist.psu.edu/boehm03destructors.html</A>)?</FONT></SPAN></DIV></DIV><!-- Converted from text/rtf format -->
<P><SPAN lang=nl><FONT face=Arial size=2>Groetjes,</FONT></SPAN> <BR><SPAN
lang=nl><FONT face=Arial size=2> <><</FONT></SPAN> <BR><SPAN
lang=nl><FONT face=Arial size=2>Marnix</FONT></SPAN> <BR><SPAN lang=nl><FONT
face=Arial color=#808080 size=2>--</FONT></SPAN> <BR><SPAN lang=en-us><FONT
face=Arial color=#808080 size=2>Marnix Klooster |</FONT><FONT face=Arial
color=#000000 size=2></FONT> <FONT face=Arial color=#808080 size=2>Software
Engineer, ERP LN Enterprise Server |</FONT><B><FONT face=Arial color=#000000
size=2></FONT> <FONT face=Arial color=#800000 size=2>Infor</FONT></B><FONT
face=Arial color=#000000 size=2></FONT> <FONT face=Arial color=#808080 size=2>|
(+31 or 0)342-428511 |</FONT><U> <FONT face=Arial color=#0000ff
size=2>marnix.klooster@infor.com</FONT></U><FONT face=Arial color=#808080
size=2> | Infor Global Solutions (Barneveld) BV | P.O. box 143 | 3770 AC
Barneveld | The Netherlands</FONT></SPAN><SPAN lang=nl></SPAN></P>
<DIV> </DIV><BR>
<BLOCKQUOTE dir=ltr
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> haskell-bounces@haskell.org
[mailto:haskell-bounces@haskell.org] <B>On Behalf Of </B>Simon
Peyton-Jones<BR><B>Sent:</B> Thursday, 3 January, 2008 14:13<BR><B>To:</B>
Conal Elliott<BR><B>Cc:</B> haskell@haskell.org<BR><B>Subject:</B> RE:
[Haskell] garbage collection of Concurrent Haskell
threads?<BR></FONT><BR></DIV>
<DIV></DIV>
<DIV class=Section1>
<P class=MsoNormal><SPAN
style="FONT-SIZE: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'">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: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'"><o:p> </o:p></SPAN></P>
<P class=MsoNormal><SPAN
style="FONT-SIZE: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'">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: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'"><o:p> </o:p></SPAN></P>
<P class=MsoNormal><SPAN
style="FONT-SIZE: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'">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: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'"><o:p> </o:p></SPAN></P>
<P class=MsoNormal><SPAN
style="FONT-SIZE: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'">Simon<o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN
style="FONT-SIZE: 11pt; COLOR: #1f497d; FONT-FAMILY: 'Calibri','sans-serif'"><o:p> </o:p></SPAN></P>
<DIV
style="BORDER-RIGHT: medium none; PADDING-RIGHT: 0cm; BORDER-TOP: medium none; PADDING-LEFT: 4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: blue 1.5pt solid; PADDING-TOP: 0cm; BORDER-BOTTOM: medium none">
<DIV>
<DIV
style="BORDER-RIGHT: medium none; PADDING-RIGHT: 0cm; BORDER-TOP: #b5c4df 1pt solid; PADDING-LEFT: 0cm; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; PADDING-TOP: 3pt; BORDER-BOTTOM: medium none">
<P class=MsoNormal><B><SPAN lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Tahoma','sans-serif'">From:</SPAN></B><SPAN
lang=EN-US style="FONT-SIZE: 10pt; 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: 12pt">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: 11pt; 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: 11pt; COLOR: #1f497d"> </SPAN><SPAN
lang=EN-US><o:p></o:p></SPAN></P>
<P><SPAN lang=EN-US style="FONT-SIZE: 11pt; 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: 11pt; COLOR: #1f497d"> </SPAN><SPAN
lang=EN-US><o:p></o:p></SPAN></P>
<DIV
style="BORDER-RIGHT: medium none; PADDING-RIGHT: 0cm; BORDER-TOP: medium none; PADDING-LEFT: 4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 1.5pt solid; PADDING-TOP: 0cm; BORDER-BOTTOM: medium none">
<DIV>
<DIV
style="BORDER-RIGHT: medium none; PADDING-RIGHT: 0cm; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 0cm; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; PADDING-TOP: 3pt; BORDER-BOTTOM: medium none">
<P><B><SPAN lang=EN-US style="FONT-SIZE: 10pt">From:</SPAN></B><SPAN
lang=EN-US style="FONT-SIZE: 10pt"> <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: 12pt"><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></BLOCKQUOTE></BODY></HTML>