#9339: last is not a good consumer -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Operating System: Unknown/Multiple Differential Revisions: | Type of failure: Runtime Architecture: | performance bug Unknown/Multiple | Test Case: Difficulty: Unknown | Blocking: Blocked By: | Related Tickets: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:1 nomeata]:

What general fusion work are you referring to? I only know about the improvements for fusing foldl, which doesn’t seem to apply here.

I was under the impression (possibly bogus) that the `foldl` fix involved some new transformation that could have other effects.

Although maybe it could. How about this definition:

{{{ myLast2 :: [a] -> a myLast2 = foldl (\_ x -> x) undefined }}}

While `last` yields 800051648 bytes, and `myLast` yields 560084432 bytes, this runs in 51648 bytes (i.e. it fuses completely).

That looks wonderful. Is it certain to be changed to a `foldl'` in cases where it ''doesn't'' fuse?

Admitted, the resulting code looks almost stupidly efficient (at least if I write `10^7` as `10000` – I’m unjustifiably surprised that that is not constant-folded):

Imagine the confusion if it were! Yes, `map f [m..n] !! p` ''could'' be optimized to O(1) whenever `m` has a known-sane type, but then all the newbies and half the oldies would get mixed up when little changes had radical performance impacts. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9339#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9339: last is not a good consumer -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Operating System: Unknown/Multiple Differential Revisions: | Type of failure: Runtime Architecture: | performance bug Unknown/Multiple | Test Case: Difficulty: Unknown | Blocking: Blocked By: | Related Tickets: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:3 nomeata]:

...

That looks wonderful. Is it certain to be changed to a foldl' in cases where it doesn't fuse?

Hopefully not. `foldl'` would force the accumulator, which we do *not* want here (otherwise the `undefined` would be forced, or `last [undefined, 1]` would not work).

Yes, you're right. I got mixed up a bit.

I didn’t do further testing with that idea, it just crossed my mind. It maybe the that this implementation is only good when fusing works – would you mind trying to find out?

I don't have anything beyond 7.8.3, and on 7.8.3 your code doesn't fuse. Could you maybe try it? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9339#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9339: last is not a good consumer -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Operating System: Unknown/Multiple Differential Revisions: | Type of failure: Runtime Architecture: | performance bug Unknown/Multiple | Test Case: Difficulty: Unknown | Blocking: Blocked By: | Related Tickets: | -------------------------------------+------------------------------------- Comment (by nomeata): Ok, let’s do this systematically. My benchmarks: One possibly fusing invocation of `last`: {{{ main = print $ Last.last $ filter odd $ [1::Int ..100000000] }}} and one non-fusing {{{ f = id {-# NOINLINE f #-} main = print $ Last.last $ f $ filter odd $ [1::Int ..100000000] }}} I am comparing the existing implementation of `last`, which is {{{ last [] = errorEmptyList "last" last (x:xs) = last' x xs where last' y [] = y last' _ (y:ys) = last' y ys }}} with the simpler {{{ last = foldl (\_ x -> x) (errorEmptyList "last") }}} Just for fun (and because GHC HEAD still compiles), here the numbers with GHC-7.6: {{{ LastTestFusing.hs <> LastTestNonFusing.hs <> NewLastTestFusing.hs <> NewLastTestNonFusing.hs <> }}} No significant difference in either of these. Now the interesting numbers are those with ghc HEAD, and for that I have to wait for the compilation to finish... So here they are: {{{ LastTestFusing.hs <> LastTestNonFusing.hs <> NewLastTestFusing.hs <> NewLastTestNonFusing.hs <> }}} We see that the new implementation performs the same in the non-fusing case, but much better in the fusing case. Why does it even allocate in the fusing case? Because it needs to box them for the recursive call: {{{ Rec { main_go :: Int# -> Int -> Int main_go = \ (x :: Int#) (eta :: Int) -> case remInt# x 2 of _ { __DEFAULT -> case x of wild { __DEFAULT -> main_go (+# wild 1) (I# wild); 100000000 -> lvl }; 0 -> case x of wild { __DEFAULT -> main_go (+# wild 1) eta; 100000000 -> eta } } end Rec } }}} Guess that’s unavoidable here. Also, to make sure that some integer unboxing doesn’t skew the comparison, here the numbers with `Integer`: {{{ <> LastTestNonFusing.hs <> NewLastTestFusing.hs <> NewLastTestNonFusing.hs <> }}} This only confirms the previous findings. TL;DR: Implementing `last` with `foldl` has no negative consequences, but works nicely when fused. I don’t expect that to happen often, but it’s still nice to have, and actually simplifies the existing library implementation. If noone complains, I’ll push this soon. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9339#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9339: last is not a good consumer -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Operating System: Unknown/Multiple Differential Revisions: D86 | Type of failure: Runtime Architecture: | performance bug Unknown/Multiple | Test Case: Difficulty: Unknown | Blocking: Blocked By: | Related Tickets: | -------------------------------------+------------------------------------- Changes (by nomeata): * differential: => D86 Comment: Code for review at https://phabricator.haskell.org/D86 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9339#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9339: last is not a good consumer -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Operating System: Unknown/Multiple Differential Revisions: Phab:D86 | Type of failure: Runtime Architecture: | performance bug Unknown/Multiple | Test Case: Difficulty: Unknown | Blocking: Blocked By: | Related Tickets: | -------------------------------------+------------------------------------- Comment (by Joachim Breitner ): In [changeset:"b709f0a047dc036de15dc43d3b0ab88d3e32c5e6/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="b709f0a047dc036de15dc43d3b0ab88d3e32c5e6" Make last a good consumer Summary: Make last a good consumer simply by implementing it as foldl. This fixes Trac: #9339. Thanks to David Feuer for bringing it up. Test Plan: perf/should_run/T9339 + general validation Reviewers: austin Reviewed By: austin Subscribers: phaskell, simonmar, relrod, carter Differential Revision: https://phabricator.haskell.org/D86 Trac Issues: #9339 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9339#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler