<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:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@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:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
p.Code, li.Code, div.Code
{mso-style-name:Code;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:108.0pt;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
font-weight:bold;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.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;}
/* List Definitions */
@list l0
{mso-list-id:1166556015;
mso-list-template-ids:-1304134914;}
@list l1
{mso-list-id:1463694496;
mso-list-type:hybrid;
mso-list-template-ids:475190434 134807553 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;
mso-bidi-font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;
mso-bidi-font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;
mso-bidi-font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;
mso-bidi-font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;
mso-bidi-font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;
mso-bidi-font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></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="WordSection1">
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Wow – tricky stuff! I would never have thought of trying to optimise that program, but it’s fascinating that you get lots and lots of them from FRP.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<ul style="margin-top:0cm" type="disc">
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo2"><span style="mso-fareast-language:EN-US">Don’t lose this thread! Make a ticket, or a wiki page. If the former, put the main payload (including Alexis’s examples) into the Descriptions,
not deep in the discussion. <o:p></o:p></span></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo2"><span style="mso-fareast-language:EN-US">I wonder whether it’d be possible to adjust the FRP library to generate easier-to-optimise code. Probably not, but worth asking.<o:p></o:p></span></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo2"><span style="mso-fareast-language:EN-US">Alexis’s proposed solution relies on
<o:p></o:p></span></li><ul style="margin-top:0cm" type="circle">
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level2 lfo2"><span style="mso-fareast-language:EN-US">Specialising on a function argument. Clearly this must be possible, and it’d be very beneficial.<o:p></o:p></span></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level2 lfo2"><span style="mso-fareast-language:EN-US">Unrolling one layer of a recursive function. That seems harder: how we know to *<b>stop</b>* unrolling as we successively simplify? One idea:
do one layer of unrolling by hand, perhaps even in FRP source code:<o:p></o:p></span></li></ul>
</ul>
<p class="Code"><span style="mso-fareast-language:EN-US">add1rec = SF (\a -> let !b = a+1 in (b,add1rec))<o:p></o:p></span></p>
<p class="Code"><span style="mso-fareast-language:EN-US">add1 = SF (\a -> let !b = a+1 in (b,add1rec))<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="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">From:</span></b><span lang="EN-US"> ghc-devs <ghc-devs-bounces@haskell.org>
<b>On Behalf Of </b>Sebastian Graf<br>
<b>Sent:</b> 29 March 2020 15:34<br>
<b>To:</b> Alexis King <lexi.lambda@gmail.com><br>
<b>Cc:</b> ghc-devs <ghc-devs@haskell.org><br>
<b>Subject:</b> Re: Fusing loops by specializing on functions with SpecConstr?<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Hi Alexis,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
I've been wondering the same things and have worked on it on and off. See my progress in
<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2Fissues%2F855%23note_149482&data=02%7C01%7Csimonpj%40microsoft.com%7Cab7afece6b43485f5e5508d7d3ee4cfc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637210892758857668&sdata=BWptTEUj%2BcKu1cEkYiFtDuBRHKKzl%2BkVxUzV%2FRIje1c%3D&reserved=0" target="_blank">
https://gitlab.haskell.org/ghc/ghc/issues/855#note_149482</a> and <a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2Fissues%2F915%23note_241520&data=02%7C01%7Csimonpj%40microsoft.com%7Cab7afece6b43485f5e5508d7d3ee4cfc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637210892758867663&sdata=w5cJDvwz0e1RWq3c%2BrG12McHTt9H%2FkMzRnUlyAS22bM%3D&reserved=0" target="_blank">
https://gitlab.haskell.org/ghc/ghc/issues/915#note_241520</a>.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
The big problem with solving the higher-order specialisation problem through SpecConstr (which is what I did in my reports in #855) is indeed that it's hard to<o:p></o:p></p>
<ol start="1" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
Anticipate what the rewritten program looks like without doing a Simplifier pass after each specialisation, so that we can see and exploit new specialisation opportunities. SpecConstr does use the simple Core optimiser but, that often is not enough IIRC (think
of ArgOccs from recursive calls). In particular, it will not do RULE rewrites. Interleaving SpecConstr with the Simplifier, apart from nigh impossible conceptually, is computationally intractable and would quickly drift off into Partial Evaluation swamp.<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
Make the RULE engine match and rewrite call sites in all call patterns they can apply.<br>
I.e., `f (\x -> Just (x +1))` calls its argument with one argument and scrutinises the resulting Maybe (that's what is described by the argument's `ArgOcc`), so that we want to specialise to a call pattern `f (\x -> Just <some expression using x>)`, giving
rise to the specialisation `$sf ctx`, where `ctx x` describes the `<some expression using x>` part. In an ideal world, we want a (higher-order pattern unification) RULE for `forall f ctx. f (\x -> Just (ctx x)) ==> $sf ctx`. But from what I remember, GHC's
RULE engine works quite different from that and isn't even concerned with finding unifiers (rather than just matching concrete call sites without meta variables against RULEs with meta variables) at all.<o:p></o:p></li></ol>
</div>
<div>
<p class="MsoNormal">Note that matching on specific Ids binding functions is just an approximation using representional equality (on the Id's Unique) rather than some sort of more semantic equality. My latest endeavour into the matter in #915 from December
was using types as the representational entity and type class specialisation. I think I got ultimately blocked on thttps://<a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2Fissues%2F17548&data=02%7C01%7Csimonpj%40microsoft.com%7Cab7afece6b43485f5e5508d7d3ee4cfc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637210892758877658&sdata=x6YJBWtNzzX2ad05yr2KoAE7G42A7agIFINws0VI%2BeY%3D&reserved=0" target="_blank">gitlab.haskell.org/ghc/ghc/issues/17548</a>,
but apparently I didn't document the problematic program.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Maybe my failure so far is that I want it to apply and optimise all cases and for more complex stream pipelines, rather than just doing a better best effort job.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Hope that helps. Anyway, I'm also really keen on nailing this! It's one of my high-risk, high-reward research topics. So if you need someone to collaborate/exchange ideas with, I'm happy to help!<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">All the best,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Sebastian<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">Am So., 29. März 2020 um 10:39 Uhr schrieb Alexis King <<a href="mailto:lexi.lambda@gmail.com">lexi.lambda@gmail.com</a>>:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p class="MsoNormal">Hi all,<br>
<br>
I have recently been toying with FRP, and I’ve noticed that<br>
traditional formulations generate a lot of tiny loops that GHC does<br>
a very poor job optimizing. Here’s a simplified example:<br>
<br>
newtype SF a b = SF { runSF :: a -> (b, SF a b) }<br>
<br>
add1_snd :: SF (String, Int) (String, Int)<br>
add1_snd = second add1 where<br>
add1 = SF $ \a -> let !b = a + 1 in (b, add1)<br>
second f = SF $ \(a, b) -><br>
let !(c, f') = runSF f b<br>
in ((a, c), second f')<br>
<br>
Here, `add1_snd` is defined in terms of two recursive bindings,<br>
`add1` and `second`. Because they’re both recursive, GHC doesn’t<br>
know what to do with them, and the optimized program still has two<br>
separate recursive knots. But this is a missed optimization, as<br>
`add1_snd` is equivalent to the following definition, which fuses<br>
the two loops together and consequently has just one recursive knot:<br>
<br>
add1_snd_fused :: SF (String, Int) (String, Int)<br>
add1_snd_fused = SF $ \(a, b) -><br>
let !c = b + 1<br>
in ((a, c), add1_snd_fused)<br>
<br>
How could GHC get from `add1_snd` to `add1_snd_fused`? In theory,<br>
SpecConstr could do it! Suppose we specialize `second` at the call<br>
pattern `second add1`:<br>
<br>
{-# RULE "second/add1" second add1 = second_add1 #-}<br>
<br>
second_add1 = SF $ \(a, b) -><br>
let !(c, f') = runSF add1 b<br>
in ((a, c), second f')<br>
<br>
This doesn’t immediately look like an improvement, but we’re<br>
actually almost there. If we unroll `add1` once on the RHS of<br>
`second_add1`, the simplifier will get us the rest of the way. We’ll<br>
end up with<br>
<br>
let !b1 = b + 1<br>
!(c, f') = (b1, add1)<br>
in ((a, c), second f')<br>
<br>
and after substituting f' to get `second add1`, the RULE will tie<br>
the knot for us.<br>
<br>
This may look like small potatoes in isolation, but real programs<br>
can generate hundreds of these tiny, tiny loops, and fusing them<br>
together would be a big win. The only problem is SpecConstr doesn’t<br>
currently specialize on functions! The original paper, “Call-pattern<br>
Specialisation for Haskell Programs,” mentions this as a possibility<br>
in Section 6.2, but it points out that actually doing this in<br>
practice would be pretty tricky:<br>
<br>
> Specialising for function arguments is more slippery than for<br>
> constructor arguments. In the example above the argument was a<br>
> simple variable, but what if it was instead a lambda term? [...]<br>
><br>
> The trouble is that lambda abstractions are much more fragile than<br>
> constructor applications, in the sense that simple transformations<br>
> may make two abstractions look different although they have the<br>
> same value.<br>
<br>
Still, the difference this could make in a program of mine is so<br>
large that I am interested in exploring it anyway. I am wondering if<br>
anyone has investigated this possibility any further since the paper<br>
was published, or if anyone knows of other use cases that would<br>
benefit from this capability.<br>
<br>
Thanks,<br>
Alexis<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-devs&data=02%7C01%7Csimonpj%40microsoft.com%7Cab7afece6b43485f5e5508d7d3ee4cfc%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637210892758877658&sdata=tTFc4DHgkLgTxAomYoFk7xsNGp8oiOWH8Hd4KcDrqvc%3D&reserved=0" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</div>
</body>
</html>