#13001: EnumFromThenTo is is not a good producer -------------------------------------+------------------------------------- Reporter: George | Owner: Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: MacOS X | Architecture: x86_64 Type of failure: Runtime | (amd64) performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by akio): I tested a [https://github.com/takano- akio/ghc/commit/930d42755e6753ba695157b96b8d651263b1934c a patch] and indeed marking `*FB` functions `INLINE[0]` seems to help. However this change increases binary sizes of some programs in nofib: {{{ -------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- gen_regexps -0.3% 0.0% 0.000 0.000 0.0% puzzle +0.8% 0.0% 0.089 0.090 0.0% reptile +0.8% -0.0% 0.008 0.008 0.0% -------------------------------------------------------------------------------- Min -0.3% -0.0% -7.3% -7.1% 0.0% Max +0.8% +0.0% +7.8% +7.7% +1.8% Geometric Mean +0.0% -0.0% +0.2% +0.2% +0.0% }}} I have only looked at the code for `puzzle` so far. The increase in the code size seems to come from inlining `efdtInt*FB` into a derived `Enum` instance declaration. I wonder if this change is acceptable. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13001#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13001: EnumFromThenTo is is not a good producer -------------------------------------+------------------------------------- Reporter: George | Owner: Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: MacOS X | Architecture: x86_64 Type of failure: Runtime | (amd64) performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): It's true that doing more inlining will generally improve things, but we could be a bit more forensic about this. Just sprinkling more inline pragmas, some of which may do no good, is a bit of a blunt instrument. I checked the code for `testFromThenTo`, compiled with -O, and got {{{ Foo.$wtestFromThenTo = \ (ww_s2vE :: GHC.Prim.Int#) -> case GHC.Prim.tagToEnum# @ Bool (GHC.Prim.<# ww_s2vE 0#) of { False -> case ww_s2vE of wild2_a2uk { __DEFAULT -> case GHC.Real.$wf1 10# wild2_a2uk of ww4_a2uE { __DEFAULT -> GHC.Enum.efdtIntUpFB @ (Int -> Int) (GHC.List.lengthFB @ Int) (id @ Int) 0# 2# ww4_a2uE Foo.testFromThenTo2 }; 0# -> Foo.testFromThenTo1 }; True -> GHC.Real.^2 } }}} Fusion has happened (there is a use of the `foldr/build` rule), but the call to `edftIntUpFB` remains. That's not necessarily bad. As you'll see, it's not a tiny function: {{{ efdtIntUpFB :: (Int -> r -> r) -> r -> Int# -> Int# -> Int# -> r efdtIntUpFB c n x1 x2 y -- Be careful about overflow! | isTrue# (y <# x2) = if isTrue# (y <# x1) then n else I# x1 `c` n | otherwise = -- Common case: x1 <= x2 <= y let !delta = x2 -# x1 -- >= 0 !y' = y -# delta -- x1 <= y' <= y; hence y' is representable -- Invariant: x <= y -- Note that: z <= y' => z + delta won't overflow -- so we are guaranteed not to overflow if/when we recurse go_up x | isTrue# (x ># y') = I# x `c` n | otherwise = I# x `c` go_up (x +# delta) in I# x1 `c` go_up x2 }}} BUT the bad thing is that it allocated loads of `Int` values! Why does it do that? Becuase the function passed to it (`c` in the above definition) takes an `Int` as its argument. So if `efdtIntUpFB` isn't inlined, it ''must'' allocate an `Int` box for every iteration. Bad! But this is an internal function. Suppose we gave it this signature: {{{ efdtIntUpFB :: (Int# -> r -> r) -> r -> Int# -> Int# -> Int# -> r -- ^^^ NB Int# not Int }}} Now it won't allocate! Can we make the rest of the pieces fit together now? Would you like to have a try? I also looked at the call to `lengthFB` in the above optimised code. It's defined like this: {{{ lengthFB :: x -> (Int -> Int) -> Int -> Int lengthFB _ r = \ !a -> r (a + 1) }}} Uh-ho! More `Int` boxes! So I tried rewriting the `length` moving parts (in `GHC.List`) like this: {{{ {-# INLINE xlength #-} xlength :: [a] -> Int xlength xs = I# (xlenAcc xs 0#) xlenAcc :: [a] -> Int# -> Int# xlenAcc [] n = n xlenAcc (_:ys) n = xlenAcc ys (n +# 1#) {-# RULES "xlength" [~1] forall xs . xlenAcc xs = foldr xlengthFB idXlength xs "xlengthList" [1] foldr xlengthFB idXlength = xlenAcc #-} -- The lambda form turns out to be necessary to make this inline -- when we need it to and give good performance. {-# INLINE [0] xlengthFB #-} xlengthFB :: x -> (Int# -> Int#) -> Int# -> Int# xlengthFB _ r = \ a -> r (a +# 1#) {-# INLINE [0] idXlength #-} idXlength :: Int# -> Int# idXlength x = x }}} That compiles fine. Even if it generates the same code as before, GHC will have to do less work to optimise it, so it's a win. Would you like to try that change to `length` and see if it is an improvement? Maybe you can do the same for `efdtIntUpFB`? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13001#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13001: EnumFromThenTo is is not a good producer -------------------------------------+------------------------------------- Reporter: George | Owner: Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: MacOS X | Architecture: x86_64 Type of failure: Runtime | (amd64) performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I think perhaps you mean that in the call {{{ I# x `c` go_up (x +# delta) }}} since GHC doesn't know `c` is strict, it'll allocate a thunk for the second argument. Quite true. And that does mean it'd be good to inline `efdtIntUpFB`, I agree. But still, fewer Int boxes is better regardless. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13001#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13001: EnumFromThenTo is is not a good producer -------------------------------------+------------------------------------- Reporter: George | Owner: Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: MacOS X | Architecture: x86_64 Type of failure: Runtime | (amd64) performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I think that's a reasonable point. If you follow it up, could you include a Note to explain the reasoning? And refer to the Note from the relevant INLINE pragmas? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13001#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13001: EnumFromThenTo is is not a good producer -------------------------------------+------------------------------------- Reporter: George | Owner: akio Type: bug | Status: new Priority: low | Milestone: Component: libraries/base | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: x86_64 Type of failure: Runtime | (amd64) performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2951 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"09bce7accd330e99b1667f8b4eda7def722d6f0c/ghc" 09bce7ac/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="09bce7accd330e99b1667f8b4eda7def722d6f0c" Mark *FB functions INLINE[0] (Fixes #13001) When fusion rules successfully fire, we are left with calls to *FB functions. They are higher-order functions, and therefore they often benefit from inlining. This is particularly important when then final consumer is a strict fold (foldl', length, etc.), because not inlining these functions means allocating a function closure for each element in the list, which often is more costly than what fusion eliminates. Nofib shows a slight increase in the binary size: ------------------------------------------------------------------------ Program Size Allocs Runtime Elapsed TotalMem ------------------------------------------------------------------------ gen_regexps -0.3% 0.0% 0.000 0.000 0.0% puzzle +0.8% 0.0% 0.089 0.090 0.0% reptile +0.8% -0.0% 0.008 0.008 0.0% ------------------------------------------------------------------------ Min -0.3% -0.0% -7.3% -7.1% 0.0% Max +0.8% +0.0% +7.8% +7.7% +1.8% Geometric Mean +0.0% -0.0% +0.2% +0.2% +0.0% ------------------------------------------------------------------------ Reviewers: simonpj, austin, hvr, bgamari Reviewed By: simonpj Subscribers: simonpj, thomie Differential Revision: https://phabricator.haskell.org/D2951 GHC Trac Issues: #13001 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13001#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13001: EnumFromThenTo is is not a good producer -------------------------------------+------------------------------------- Reporter: George | Owner: akio Type: bug | Status: new Priority: low | Milestone: 8.4.1 Component: libraries/base | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: x86_64 Type of failure: Runtime | (amd64) performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2951 Wiki Page: | -------------------------------------+------------------------------------- Comment (by George): although this is low priority, it looks like it is done. Is there any reason not to put it into 8.4.1? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13001#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler