<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=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
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";}
p.Code, li.Code, div.Code
{mso-style-name:Code;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Courier New";}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
.MsoPapDefault
{mso-style-type:export-only;
margin-top:6.0pt;
margin-right:0cm;
margin-bottom:6.0pt;
margin-left:0cm;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US">Think of this like worker/wrapper. Given ‘crazy’, with some large body, you want to turn it into<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US">crazy x = build (\cn. craxy’ c n x)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US">{-# INLINE crazy #-}<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US">Now you can inline crazy everywhere, which will allow a consuming foldr to cancel with the build. And without duplicating all the code.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US">But if there *<b>is</b>* no foldr, you’ll end up with calls like (crazy’ (:) []) , which will be considerably less efficient than the original function.
So you really want *<b>both</b>* crazy’ <b>and</b> crazy’ specialised to (:) and [].<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US">GHC doesn’t do this automatically, because it really works well if the body of crazy is a good producer. But you could imagine automating it.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri","sans-serif";color:#1F497D;mso-fareast-language:EN-US"><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 #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri","sans-serif""> Libraries [mailto:libraries-bounces@haskell.org]
<b>On Behalf Of </b>David Feuer<br>
<b>Sent:</b> 27 July 2014 20:29<br>
<b>To:</b> Haskell Libraries<br>
<b>Subject:</b> Issues resulting from inlining build<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p>I think I finally figured out the deeper problem behind an issue I was having getting some things to fuse fully. I'm hoping someone has a brilliant idea for getting around it. Of course, it may be that someone else has thoroughly studied the matter and determined
that there's no good solution. Suppose we write<o:p></o:p></p>
<p>crazy :: T -> [U]<br>
crazy x = some $ long $ fusion $ pipeline<o:p></o:p></p>
<p>oops f = map f $ crazy x<br>
uhOh c n = foldr c n $ crazy Pig<br>
ohMy = take bignum $ crazy amigo<o:p></o:p></p>
<p>When GHC compiles crazy, it rewrites the pieces of the pipeline to build/foldr forms, fuses them, and produces<o:p></o:p></p>
<p>crazy x = build someBigFunction<o:p></o:p></p>
<p>In then inlines build, producing<o:p></o:p></p>
<p>crazy x = anotherBiggy<o:p></o:p></p>
<p>So far, this looks reasonably sensible, but it's likely bad. The problem is that GHC will (rightly) conclude that `build someBigFunction` is too big to inline, and therefore the fusion will break at that boundary and we'll produce intermediate lists in the
functions that use crazy. Now if we were playing the part of the compiler by hand, we would likely factor out someBigFunction and then *refrain from inlining build*. That is, we would get<o:p></o:p></p>
<p>{-# NOINLINE crazyB #-}<br>
crazyB x = someBigFunction<o:p></o:p></p>
<p>crazy = nonInliningBuild crazyB<o:p></o:p></p>
<p>Since we've factored out someBigFunction into crazyB, we can now safely inline crazy itself, allowing the pipeline to continue beyond it. The problem, of course, is that when we *don't* fuse beyond, there is some performance penalty (I have not tried to
measure it yet) to passing in (:) and [] at runtime instead of fixing them at compile time.<o:p></o:p></p>
</div>
</div>
</body>
</html>