Considerations for Control flow hint implementation.

[Andreas Klebinger]

Thank your for the feedback Simon!

This indeed seems like the way to go. I tried that and
adding weights to core this way only added 0.1% allocations on average 
for -O2.

Cheers,
Andreas




Simon Peyton Jones schrieb:
>
> Alternative 1: Putting the weights directly into the case alternative 
> tuple
>
> Rather than putting it in the tuple, you could put it in the AltCon
>
> type Alt b = (AltCon, [b], Expr b)
>
> data AltCon = DataAlt Freq DataCon | LitAlt Freq Literal | DEFAULT Freq
>
> 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
>
> Simon
>
> *From:*ghc-devs <ghc-devs-bounces at haskell.org> *On Behalf Of *Andreas 
> Klebinger
> *Sent:* 30 November 2018 11:37
> *To:* ghc-devs at haskell.org
> *Subject:* Considerations for Control flow hint implementation.
>
> Hello Devs,
>
> I've started thinking about the implementation of 
> https://github.com/ghc-proposals/ghc-proposals/pull/182 recently. (Add 
> control flow hint pragmas.)
>
> For this purpose I've rebased *D4327 *"WIP: Add likelyhood to 
> alternatives from stg onwards" which already does a lot of the work at 
> the Cmm/Stg level.
>
> The issue I ask you for feedback now is how to best attach branch 
> weights to case alternatives in core.
>
> My prefered approach would be to expand core data types to include 
> them unconditionally.
> While this is quite far reaching in the amount of code it touches it 
> would be rather straight forward to implement:
>
> Alternative 1: Putting the weights directly into the case alternative 
> tuple:
> + It it's trivial to check which places manipulate case alternatives 
> as they will initially fail to compile.
> + It's very mechanical, almost all use sites won't actually change the 
> weight.
> + It's easy to keep this working going forward as any new 
> optimizations can't "forget" they have to consider them.
> - It will introduce a cost in compiler performance.
> - New optimization who don't have to care about branchweights still 
> have to at least pipe them through.
> - While syntactically heavy in terms of real complexity it's a simply 
> approach.
>
> Alternative 2:  Putting the weights into the case constructor.
> + Might give better compiler performance as I expect us to rebuild 
> cases less often than alternatives.
> - Seems kind of clunky.
> - Weaker coupling between case alternatives and their weights.
>
> Or we could use ticks:
> + There is some machinery already there
> + Can be turned off for -O0
> + Can be ignored when convenient.
> - Can be ignored when convenient.
> - Very weak coupling between case alternatives and their weights.
> - The existing machinery doesn't exactly match the needs of this.
> - We would have to extend tick semantics to a degree where complexity 
> might grow too large
>   for me to successfully implement this.
> - If new optimizations end up just removing these ticks because they 
> are allowed to  then
>   the whole exercise becomes rather pointless.
> - Makes it harder to ensure all relevant code paths in GHC are 
> actually updated.
>
> In particular there is currently no tick category which can stick to 
> case alternatives but just get's removed in case
> it get's in the way of optimizations.
> The closest match is SoftScope which allows ticks to be floated up, 
> something that could impact performance quite badly
> in this case. As then we might float something intended to mark a 
> branch as unlikely into another branch that is actually
> along the hot path.
>
> I think the core variant(s) mostly stand and fall with the actual 
> compile time impact. For -O0 the impact
> would be negligible as the compile time is already dominated by 
> codegen and typechecking. For the rest
> it's hard to say.
>
> So I'm looking for feedback on this. Maybe you have other suggestions 
> I haven't considered?
> How much compile time cost increase would be acceptable for what kind 
> of performance boost?
>
> Cheers,
> Andreas Klebinger
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20181201/3115b705/attachment.html>