#10788: performance regression involving minimum (and maybe Vector) -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by nomeata): In 7.8, both `minimum` and `sum` were non-fusing left-folds. In 7.10, `sum`, via `foldl`, is fusing, so this is the 5× improvement you observe. `minimum` is not easily foldable: It is a `foldl1`, which treats the first `(:)` different from the rest, and it is not clear how to fix that. So performance difference between `minimum` and `sum` in 7.10 can be explained. What needs to be investigated is why 7.10 degraded by 50% over 7.8. I do not expect Call Arity/foldl fusion to play a role here, but I might be wrong. BTW: One could reasonably expect the compiler to transform `minimum (x:xs)` into `foldl' min x xs`, which could then maybe fuse, but that does not seem to be the case. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10788: performance regression involving minimum (and maybe Vector) -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by rwbarton): It looks like more inlining happened in 7.10.1 at the definition site of `strictMinimum`, and the result was that the unfolding became too large for GHC to want to inline it at use sites. 7.8.4: {{{ Considering inlining: Data.List.strictMinimum arg infos [ValueArg, NonTrivArg] uf arity 2 interesting continuation CaseCtxt some_benefit True is exp: True is work-free: True guidance IF_ARGS [30 30] 80 0 discounted size = -10 ANSWER = YES strictMinimum :: GHC.Classes.Ord a -> [a] -> a {- Arity: 2, Strictness: , Unfolding: (\ @ a $dOrd :: GHC.Classes.Ord a ds :: [a] -> case ds of wild { [] -> Data.List.minimum1 @ a : ipv ipv1 -> Data.List.foldl' @ a @ a (GHC.Classes.min @ a $dOrd) ipv ipv1 }) -} }}} 7.10.1: {{{ Considering inlining: strictMinimum arg infos [ValueArg, NonTrivArg] interesting continuation CaseCtxt some_benefit True is exp: True is work-free: True guidance IF_ARGS [30 30] 200 0 discounted size = 110 ANSWER = NO strictMinimum :: Ord a => [a] -> a {- Arity: 2, Strictness: , Unfolding: (\ @ a $dOrd :: Ord a ds :: [a] -> case ds of wild { [] -> minimum1 @ a : ipv ipv1 -> let { k :: a -> a -> a = min @ a $dOrd } in letrec { go :: [a] -> a -> a {- Arity: 2, Strictness: -} = \ ds1 :: [a] eta :: a -> case ds1 of wild1 { [] -> eta : y ys -> case eta of z { DEFAULT -> go ys (k z y) } } } in go ipv1 ipv }) -} }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10788: performance regression involving minimum -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by nomeata): So one solution would be to mark `strictMinimum` as `INLINE`, so that its unfolding stays small and both `strictMinimum` and `foldl` will be inlined at the use site? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10788: performance regression involving minimum -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by nomeata): With {{{ {-# SPECIALIZE minimum :: [Int] -> Int #-} }}} instead of the rule rewriting it to strictMinimum, and *not* adding an INLINE pragma to `minimum`, I get good code in `GHC.List`, and this is being used here without too much inlining (it inlines the wrapper that distinguishes `[]` from a non-empty list and unboxes the int, but then calls the wrapper in `GHC.List.$wgo1`. Removing `INLINE` is important, as otherwise we’d be having this worker in every use of minimum. Even without `INLINE` we have this in the interface {{{ minimum :: Ord a => [a] -> a {- Arity: 2, Strictness: , Unfolding: (\ @ a11 $dOrd :: Ord a11 ds :: [a11] -> case ds of wild { [] -> minimum3 @ a11 : ipv ipv1 -> let { k :: a11 -> a11 -> a11 = min @ a11 $dOrd } in letrec { go :: [a11] -> a11 -> a11 {- Arity: 2, Strictness: -} = \ ds1 :: [a11] eta :: a11 -> case ds1 of wild1 { [] -> eta : y ys -> go ys (k eta y) } } in go ipv1 ipv }) -} }}} so more specialization in some client module seems to be possible. Adding `INLINEABLE` for reliability does not hurt, though. This seems to be the right thing to be doing here, but maybe not in general – how can I tell? This is all so brittle... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10788: performance regression involving minimum -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by nomeata):

Can you stand back and give a description of the brittle-ness?

I actually planned to write something to the list about this... and I [https://mail.haskell.org/pipermail/libraries/2015-September/026099.html now have]. In this particular case, I am quite happy with the `INLINEABLE`/`SPECIALIZE` solution, and will submit a DR soon. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10788: performance regression involving minimum -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by Joachim Breitner ): In [changeset:"dc671a1c06736b192e4a53f580e17356ffa7224e/ghc" dc671a1c/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="dc671a1c06736b192e4a53f580e17356ffa7224e" SPECIALIZE strictMinimum for Int and Integer This fixes a regression reported in #10788, where due to less inlining compared to earlier versions, we’d get worse code. With the SPECIALIZE, we get the good code, and moreover, the good code is in List.hs and _not_ inlined to the use site, so smaller code size and less compilation time. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10788: performance regression involving minimum -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: ekmett Type: bug | Status: closed Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by nomeata): And a slightly larger patch, which avoids the use of `strictMinimum`, for this is currently tested via Phabricator at Phab:1229. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10788: performance regression involving minimum -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: ekmett Type: bug | Status: closed Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj):

Update: I looked into this, and it seems that even if -ddump-simpl looks like this, with a space-leaky way of accumulating the argument, that in the CorePrep stage the evaluation of cmax is pulled before the call to go and alls is well. I did not know that there are still such things going on in that stage.

Suppose we have a function call `f (g x)` and `f` is strict. Then GHC keeps it looking like that so that rewrite rules apply easily. In `CorePrep` GHC just makes the order of evaluation explicit, by moving to {{{ case (g x) of y -> f y }}} There is no new analysis; the call always was call-by-value; but after `CorePrep` that fact is 100% explicit. I believe that the conclusion here is that GHC is behaving perfectly predictably; but library authors need to take a little care with pragmas and rules if they want to get predictable fusion. That's what your email in comment:9 is about, if I read it right. That is, you are not seeking any change to GHC. Correct? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10788#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler