Re: Considerations for Control flow hint implementation.
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 *On Behalf Of *Andreas Klebinger *Sent:* 30 November 2018 11:37 *To:* ghc-devs@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 ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
RE: Considerations for Control flow hint implementation.
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 On Behalf Of Andreas Klebinger Sent: 30 November 2018 11:37 To: ghc-devs@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 ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
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 ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
