#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.6.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by danilo2): One more thing - the source code uses `-XStrict` but even without using it and putting everywhere bang patterns by hand I got exactly the same results. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.6.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by danilo2): Ok, I've got one more important notice. If I put the `NOINLINE` pragma on the `runTokenParser` function, the `test0` is working 14 times slower. And this is interesting because `runTokenParser` does a simple pattern matching and then evaluates the `Text.span` function. So the `Text.span` (mapping a function to 100000 Chars) takes a tiny fraction of time of this computation. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.6.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by danilo2): @simonpj I'll try to prepare you some version without criterion this weekend (sorry for that, I'm working almost literally 24h/day now). Thank you for looking into this issue! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: infoneeded Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by danilo2): @simonpj I removed Criterion as dependency here and get the same results. Compile it and pass the resulting eecutable a number - `0`, `1` or `2` to execute `test0`, `test1` or `test2` respectively. https://github.com/wdanilo/ghc-bug-peg- optimization/blob/master/src/Main.hs -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * Attachment "Main.hs" added. Variant of Main.hs I used for debugging -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): (NB: this comment does not respond to `test2`, which I'm still investigating.) I can see what is happening in `test0` vs `test1`. In `test0` we get {{{ lvl_sdWb :: Char -> Bool [LclId, Arity=1] lvl_sdWb = \ (c_X402 :: Char) -> case c_X402 of { GHC.Types.C# ipv_sbcB [Dmd=] -> case ipv_sbcB of { __DEFAULT -> GHC.Types.False; 'e'# -> GHC.Types.True; 's'# -> GHC.Types.True; 't'# -> GHC.Types.True } } $wtest0_sdEs = \ (ww_sdEo :: GHC.Prim.ByteArray#) (ww_sdEp :: GHC.Prim.Int#) (ww_sdEq :: GHC.Prim.Int#) -> case $sunion_scrz lvl_scJr lvl_sdWa of dt_X4yi [Dmd=] { __DEFAULT -> case $sunion_scrz lvl_scJp dt_X4yi of dt_X4yq { __DEFAULT -> $wrunTokenParser_sdDw (Main.Many @ Char (Main.Tokens @ Char dt_X4yq lvl_sdWb)) ww_sdEo ww_sdEp ww_sdEq } } }}} So `SpecConstr` will specialise `$wrunTokenParser` thus: {{{ RULES "SC:$wrunTokenParser1" [2] forall (sc_se8A :: GHC.Prim.Int#) (sc_se8z :: GHC.Prim.Int#) (sc_se8y :: GHC.Prim.ByteArray#) (sc_se8x :: Set Char). $wrunTokenParser_sdDw (Main.Many @ Char (Main.Tokens @ Char sc_se8x lvl_sdWb)) sc_se8y sc_se8z sc_se8A = $s$wrunTokenParser_se8G sc_se8A sc_se8z sc_se8y sc_se8x] }}} Notice, in particular, `lvl_sdWb`, which is a top-level constant (not forall'd by the RULE): the specialised `runTokenParser` knows exactly what that function is, and that makes the inner loop fast. The fact that it is specialised for `Many` and `Tokens` is incidental, because `runTokenParser` is not recursive; it's the loop inside (which comes from `span`) that is rendered fast by knowing the function given to `span`. In contrast, `test1` doesn't get any specialisation. {{{ test1 = runTokenParser testGrammar1 }}} Even if you manually eta-expand it, by writing {{{ test3 src = runTokenParser testGrammar1 src }}} we still get nothing useful {{{ Main.$wtest3 = \ (ww_sdIT :: GHC.Prim.ByteArray#) (ww1_sdIU :: GHC.Prim.Int#) (ww2_sdIV :: GHC.Prim.Int#) -> $wrunTokenParser_resz testGrammar1_r23E ww_sdIT ww1_sdIU ww2_sdIV }}} What happened in `test0` (the fast case) is that the programmer manually inlined `testGrammar1_r23E`: {{{ testGrammar1_r23E = case Main.$sunion lvl17_resE lvl19_resH of dt_X4B6 { __DEFAULT -> case Main.$sunion lvl18_resG dt_X4B6 of dt1_X4Be { __DEFAULT -> Main.Many @ Char (Main.Tokens @ Char dt1_X4Be lvl10_ress) } } }}} But GHC is super-cautious about doing so in `test3`, in case we duplicate the work of computing `testGrammar1`: Those `union`s might be expensive! And `test3` might be applied to many different `src` arguments. In contrast, in `test1` you manually put the grammar inside the `\src`. --------------- '''Analysis''' There are two problems: 1. In `test3`, GHC's caution about inlining `testGrammar1` is (in general) reasonable. Perhaps the Right Thing is to ignore the problem of work-duplication if the user supplies an INLINE pragma, which you do in this case, presumably for that exact reason. Let's see: danilo2, what led you to the INLINE pragma on `testGrammar1`? 2. `test1` is not eta-expanded, because it's a partial application: see `Note [Do not eta-expand PAPs]` in `SimplUtils`. And because it is not eta-expanded, `runTokenParser` doesn't get enough arguments and `SpecConstr` doesn't consider under-saturated calls. Moreover, even `test0` is fragile: it's entirely possible that the full- laziness pass will float out all those let-bindings (for `s1`, `s2` etc) to top level, since they are independent of `src` ------------- '''Workarounds''' A robust improvement is to use `oneShot`: {{{ test3 = oneShot (runTokenParser testGrammar1) }}} The magic `oneShot` function eta-expands its argument to a one-shot lambda: {{{ test3 = \src[one-shot] -> runTokenParser testGrammar1 src }}} Now at least, if `testGrammar1` is inlined, it won't get floated out again. Next thing: make this the ''only'' occurrence of `testGrammar1`; then there is no duplication issue when inlining it, so we get {{{ test3 = \src[one-shot] -> runTokenParser (...code for the grammar...) src }}} In the test case, `testGrammar1` is used in two different tests, so it currently won't get inlined (lest we have work duplication); but in your real code it is probably used only once, I guess. Last thing: remove the INLINE pragma on `testGrammar1`. It may seem silly but if a binding has an INLINE pragma, even if it is used exactly once it is not inlined. Why not? See `Note [Stable unfoldings and preInlineUnconditionally]`. This really is silly: see Fix 1 below. -------------- '''Fixing it properly''' * '''Fix 1''': concerning `Note [Stable unfoldings and preInlineUnconditionally]`, perhaps we should not do this for arity-0 bindings. * '''Fix 2''': perhaps we should honour INLINE pragmas on 0-arity bindings, and simply inline them at every usage site regardless. It's not so clear how to solve the eta-expansion problem. Ideas * we could try to make `SpecConstr` deal with under-saturated calls; and/or * we could eta-expand PAPs provided no coercions were involved. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => SpecConstr Comment: OK, re comment:12, this is an old problem: see Trac #4448. The current (horrible) solution is to take control explicitly, like this {{{ import GHC.Type( SPEC(..) ) runTokenParser :: SPEC -> Grammar Char -> Text -> Result runTokenParser = \sp grammar stream -> case grammar of Tokens _ tst -> let head = Text.head stream in if tst head then Success (Text.tail stream) (Text.singleton head) else Fail Many (Tokens _ tst) -> let (!consumed, !rest) = Text.span tst stream in Success rest consumed X !grammar -> runTokenParser sp grammar stream }}} Notice that `SPEC` argument. It's not actually used, but it tells `SpecConstr` to specialise the call regardless of whether the function scrutinises the argument (see Trac #4448 for a simpler example). That indeed makes `test2` work nicely. I don't claim that it's nice. At all. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by danilo2): @simonpj, @sgraf, first of all, thank you very much for your time, taking look at this issue and investigating it so deeply. Thanks to it I have hope we will fix it! 1. First of all I'm simply amazed by the amount of workarounds here. I know I was writing this before in other tickets, but I care a lot about predictive performance in GHC. All the described things show me that its worse than I thought, see the following points. 2. In order to write high performance code we need invariants. Rules that we can follow and we can trust that they allow us get **exactly** the behavior we want. One of the most important invariants to me (probably the most important one) was always that if I use the INLINE pragma, the code will be inlined if the call is saturated and it will have exactly the same behavior if I just copy paste it there. I always understood that the INLINE pragma is exactly for this - to very precisely guide GHC how to optimize the code. Learning that GHC does not really inline all explicitly marked saturated calls and sometimes it gets better specialization when removing the INLINE pragma is just insane. it breaks the most primitive invariant that we can rely on and without it we cannot predict just anything about the performance of code we write. For me this is critical error. 3. Moreover I strongly disagree with the sentence that the "fix would be to remove INLINE pragma" because this leaves us in a world where GHC performance is completely unknown and we have to randomly enable / disable things hoping that it will magically get better. I suspect @sgraf that you didn't mean "fix" but instead a "dirty workaround for now", but I preferred to emphasize my worries regarding this matter. 4. Answering your question @simonpj, I completely understand that GHC is super-cautious about inlining things and making the code bigger, but that is exactly the reason why we can fine tune the behavior by telling GHC that we in reality want it to be inlined, right? Exactly this led me to use INLINE pragma here. When writing this code I know I will have here some very tight loops to be optimized and I know that no matter what it sohuld be inlined. 5. I'm surprised that `test1` is not eta expanded. How can I be sure my functions get eta expanded? I have read the `Note [Do not eta-expand PAPs]` but it's still not clear to me. What are the "invariants here". If I write high performance code should I always manually eta-expand functions? Should I rewrite it to `test1 = \t -> runTokenParser testGrammar1 t`? Please correct me if my thinking is wrong here. 6. Regarding the `test2`, specialization and over-specialising things. I see the problem and I don't know what approach would be good here. The only thing that is clear to me is that the change to code is so small, that nobody should expect such drastic performance changes and we should have a clear way of preventing such things from happening (again - invariant of how to write high performance code when we want to wrap some data in a compile-known constructor just to refactor things). 7. Looking at the source code I don't see any mention of the `SPEC` in GHC.Type. Where it cames from and where can I learn more about it? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by danilo2): @simonpj I know, I'm sorry I was not clear enough. That sentence was regarding the post of @sgraf (citing it: `So, the fix to apply in your situation seems to be to eta-expand test1 and omit the INLINE pragma.`) :) Yes, making GHC always listen to INLINE will help me regarding 2,3,4! 5. This is very interesting. Would you be so nice and tell me jsut a little more aobut it - where can I learn about it and why such design decisions were made? 6. :) 7. Very interesting. Thank you for sharing the knowledge! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I have created #15578 for the proposed INLINE-of-0-ary things change. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):

Yes, exactly. I'm not happy with doing this (or rather having to anticipate doing this), either.

I've got lost. What exactly is "this"? Are you happy with what I propose in #15578? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by danilo2): @sgraf I would be truly surprised if 1% of library authors who ever used the INLINE pragma are aware how in reality it gets resolved. Moreover, you cannot rely on it because you don't have any clear guidance how to write high performance code with the current behavior, so I'm pretty sure there is nobody consciously relying on this behavior. I'd love to see this fixed according to SPJ proposal! :) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 15578 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by George): * related: => 15578 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15519: Minor code refactoring leads to drastic performance degradation -------------------------------------+------------------------------------- Reporter: danilo2 | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 8.8.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15578 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by maoe): * cc: maoe (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15519#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler