<html><head>
<meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type">
</head><body bgcolor="#FFFFFF" text="#000000">Thank your for the
feedback Simon!<br>
<br>
This indeed seems like the way to go. I tried that and<br>
adding weights to core this way only added 0.1% allocations on average
for -O2.<br>
<br>
Cheers,<br>
Andreas<br>
<br>
<br>
<br>
<br>
<span>Simon Peyton Jones schrieb:</span><br>
<blockquote
cite="mid:AM0PR83MB03086EB70D7B76EA7B58B653ADD30@AM0PR83MB0308.EURPRD83.prod.outlook.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
<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;}
@font-face
{font-family:"Segoe UI";
panose-1:2 11 5 2 4 2 4 2 2 3;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:black;}
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.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:9.0pt;
font-family:"Courier New";
color:black;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:black;}
span.js-issue-title
{mso-style-name:js-issue-title;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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]-->
<div class="WordSection1">
<p class="MsoNormal">Alternative 1: Putting the weights directly into
the case alternative tuple<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Rather than putting it in the tuple, you could put
it in the AltCon<o:p></o:p></p>
<p class="Code">type Alt b = (AltCon, [b], Expr b)<o:p></o:p></p>
<p class="Code">data AltCon = DataAlt Freq DataCon | LitAlt Freq Literal
| DEFAULT Freq<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal">My guess is that a lot more current code pattern
matches on those triples than pattern matches on the AltCon itself. And
AltCon isn’t used for anything else<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Simon<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><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 <a class="moz-txt-link-rfc2396E" href="mailto:ghc-devs-bounces@haskell.org"><ghc-devs-bounces@haskell.org></a>
<b>On Behalf Of </b>Andreas Klebinger<br>
<b>Sent:</b> 30 November 2018 11:37<br>
<b>To:</b> <a class="moz-txt-link-abbreviated" href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a><br>
<b>Subject:</b> Considerations for Control flow hint implementation.<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Hello Devs,<br>
<br>
I've started thinking about the implementation of <a
moz-do-not-send="true"
href="https://github.com/ghc-proposals/ghc-proposals/pull/182">
https://github.com/ghc-proposals/ghc-proposals/pull/182</a> recently. (<span
class="js-issue-title">Add control flow hint pragmas.)</span><br>
<br>
For this purpose I've rebased <b><span
style="font-size:10.0pt;font-family:"Segoe
UI",sans-serif;color:#464C5C">D4327
</span></b>"WIP: Add likelyhood to alternatives from stg onwards" which
already does a lot of the work at the Cmm/Stg level.<br>
<br>
The issue I ask you for feedback now is how to best attach branch
weights to case alternatives in core.<br>
<br>
My prefered approach would be to expand core data types to include them
unconditionally.
<br>
While this is quite far reaching in the amount of code it touches it
would be rather straight forward to implement:<br>
<br>
Alternative 1: Putting the weights directly into the case alternative
tuple:<br>
+ It it's trivial to check which places manipulate case alternatives as
they will initially fail to compile.<br>
+ It's very mechanical, almost all use sites won't actually change the
weight.<br>
+ It's easy to keep this working going forward as any new optimizations
can't "forget" they have to consider them.<br>
- It will introduce a cost in compiler performance.<br>
- New optimization who don't have to care about branchweights still have
to at least pipe them through.<br>
- While syntactically heavy in terms of real complexity it's a simply
approach.<br>
<br>
Alternative 2: Putting the weights into the case constructor.<br>
+ Might give better compiler performance as I expect us to rebuild cases
less often than alternatives.<br>
- Seems kind of clunky.<br>
- Weaker coupling between case alternatives and their weights.<br>
<br>
Or we could use ticks:<br>
+ There is some machinery already there<br>
+ Can be turned off for -O0<br>
+ Can be ignored when convenient.<br>
- Can be ignored when convenient.<br>
- Very weak coupling between case alternatives and their weights.<br>
- The existing machinery doesn't exactly match the needs of this.<br>
- We would have to extend tick semantics to a degree where complexity
might grow too large<br>
for me to successfully implement this.<br>
- If new optimizations end up just removing these ticks because they are
allowed to then<br>
the whole exercise becomes rather pointless.<br>
- Makes it harder to ensure all relevant code paths in GHC are actually
updated. <br>
<br>
In particular there is currently no tick category which can stick to
case alternatives but just get's removed in case<br>
it get's in the way of optimizations.<br>
The closest match is SoftScope which allows ticks to be floated up,
something that could impact performance quite badly<br>
in this case. As then we might float something intended to mark a branch
as unlikely into another branch that is actually<br>
along the hot path.<br>
<br>
I think the core variant(s) mostly stand and fall with the actual
compile time impact. For -O0 the impact<br>
would be negligible as the compile time is already dominated by codegen
and typechecking. For the rest<br>
it's hard to say.<br>
<br>
So I'm looking for feedback on this. Maybe you have other suggestions I
haven't considered?<br>
How much compile time cost increase would be acceptable for what kind of
performance boost?<br>
<br>
Cheers,<br>
Andreas Klebinger<o:p></o:p></p>
</div>
</div>
</blockquote>
<br>
</body></html>