#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- 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 simonpj): What is the "new definition"? I'm pretty hazy about what exactly you are proposing here. Could you write it out explicitly and then the Core Libraries Committee can decide. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: patch 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: Phab:D844 -------------------------------------+------------------------------------- Changes (by nomeata): * status: new => patch * differential: => Phab:D844 Comment: Put this up at Phab:D844 and will push this once it validated. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: patch 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: Phab:D844 -------------------------------------+------------------------------------- Comment (by nomeata): I had a closer look, and the problem is the following: When we added the implementation {{{ last = foldl (\_ x -> x) (error "...")) }}} to `GHC.List` in #9339, we assumed (and I thought we checked, but maybe that not true) that GHC would optimize the core will look something like this: {{{ last :: forall a_ask. [a_ask] -> a_ask [GblId, Arity=1, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 60} Tmpl=\ (@ a_aTE) -> foldl @ a_aTE @ a_aTE (GHC.List.last2 @ a_aTE) (GHC.List.last1 @ a_aTE)] last = .. efficient implementation derived from foldl ... .. }}} This way, when using `last` in code compiled without `-O`, the efficient variant would be called, while with `-O` the unfolding would be used and optimized on the spot, possibly fusing, and producing good code if Call Arity kicks in. Unfortunately, this is what we see: {{{ last :: forall a_ask. [a_ask] -> a_ask [GblId, Arity=1, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 60}] last = \ (@ a_aTE) -> foldl @ a_aTE @ a_aTE (GHC.List.last2 @ a_aTE) (GHC.List.last1 @ a_aTE) }}} Now the question is: Why is the code not optimized in `GHC.List`? My guess is that we should have written {{{ last xs = foldl (\_ x -> x) (error "...")) xs }}} And indeed, this way, we get: {{{ Rec { GHC.List.last2 [Occ=LoopBreaker] :: forall a_aTF. [a_aTF] -> a_aTF -> a_aTF [GblId, Arity=2, Caf=NoCafRefs, Str=DmdType ] GHC.List.last2 = \ (@ a_aTF) (ds_a1Es :: [a_aTF]) (eta_B1 :: a_aTF) -> case ds_a1Es of _ [Occ=Dead] { [] -> eta_B1; : y_a1Ex ys_a1Ey -> GHC.List.last2 @ a_aTF ys_a1Ey y_a1Ex } end Rec } last :: forall a_ask. [a_ask] -> a_ask [GblId, Arity=1, Str=DmdType , Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [0] 30 0}] last = \ (@ a_aTF) (xs_ast :: [a_aTF]) -> GHC.List.last2 @ a_aTF xs_ast (GHC.List.last1 @ a_aTF) }}} which his nice, but now we lost the original definition. Next try, also adding `{-# INLINEABLE last #-}`, which yields. {{{ Rec { poly_go_r2F3 :: forall a_aTF. [a_aTF] -> a_aTF -> a_aTF [GblId, Arity=2, Caf=NoCafRefs, Str=DmdType ] poly_go_r2F3 = \ (@ a_aTF) (ds_a1Es :: [a_aTF]) (eta_B1 :: a_aTF) -> case ds_a1Es of _ [Occ=Dead] { [] -> eta_B1; : y_a1Ex ys_a1Ey -> poly_go_r2F3 @ a_aTF ys_a1Ey y_a1Ex } end Rec } last [InlPrag=INLINABLE[ALWAYS]] :: forall a_ask. [a_ask] -> a_ask [GblId, Arity=1, Str=DmdType , Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [0] 160 0 Tmpl= \ (@ a_aTF) (xs_ast [Occ=Once] :: [a_aTF]) -> foldr @ a_aTF @ (a_aTF -> a_aTF) (\ (ds_d1DA [Occ=Once] :: a_aTF) (ds1_d1DB [Occ=Once!, OS=OneShot] :: a_aTF -> a_aTF) _ [Occ=Dead, OS=OneShot] -> ds1_d1DB ds_d1DA) (id @ a_aTF) xs_ast (errorEmptyList @ a_aTF (build @ Char (\ (@ b_a1Fd) -> unpackFoldrCString# @ b_a1Fd "last"#)))}] last = \ (@ a_aTF) (xs_ast :: [a_aTF]) -> poly_go_r2F3 @ a_aTF xs_ast (lvl8_r2F2 @ a_aTF) }}} That looks better. The unfolding is a bit more complicated, as `foldl` is being lined, but that is presumably ok. I’ll create a pull request with this in a small while, for review and discussion. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: patch 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: Phab:D846 -------------------------------------+------------------------------------- Changes (by nomeata): * differential: Phab:D844 => Phab:D846 Comment: Second try: Phab:D846 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: patch 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: Phab:D847 -------------------------------------+------------------------------------- Comment (by rwbarton): Replying to [comment:5 nomeata]:

@rwbarton, just to make sure I don’t get you wrong: Are you talking about compiling a "normal" program using last, using a normally build compiler, or are you talking about compiling the base libraries without optimization, e.g. during GHC development?

I mean using a compiler built with "perf", e.g. the 7.10.1 release, and compiling the user program without optimization. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: patch 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: Phab:D847 -------------------------------------+------------------------------------- Comment (by nomeata):

And yet the comment is reasonably convincing. I'm not sure what to do here.

I think we are doing the right thing here. As far as I know, we also take the number of arguments given by the user as an indication when things should inline or not; if we eta-expand PAPs, we take this possibility of control away from the user. In this particular case: What if I had written `last` this way intentional, so that the rule for `foldl` would _not_ fire here, but only after `last` was inlined at a position where it is passed an argument? (Or am I talking non-sense if we are talking about PAPs, in contrast to functions that might be eta-expanded more.) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: patch 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: Phab:D847 -------------------------------------+------------------------------------- Comment (by nomeata): Ah, right, the template is stored before this happens; good. What is our motivation to eta-expand PAPs? In this case, it is to allow for RULES to fire. Is it not likely that in order for RULES to fire, we might have to eta-expand beyond a coercion? So it does not gain a lot in robustness. I’m inclined to wait for more than just this example to give this a shot, after all, implementing the heuristics (“if it is a PAP, and there is a chance to eta-expand, but only up to the next coercion...”) does not really make the code simpler... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: patch 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: Phab:D847 -------------------------------------+------------------------------------- Comment (by nomeata):

Maybe. But eta expansion is in general a tremendously good thing. I'd love just to try it.

Looks like I forgot to cross-reference the ticket where I started working on this: #10319 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata 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: Phab:D847 -------------------------------------+------------------------------------- Changes (by nomeata): * status: patch => closed * resolution: => fixed Comment: Fixing this, as `last` works as intended now. Further discussion about a more general solution can happen at #10319. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10260: last uses too much space with optimizations disabled -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: nomeata Type: bug | Status: merge 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: Phab:D847 -------------------------------------+------------------------------------- Comment (by nomeata): Probably. I’m always unsure about the policy here. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10260#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler