#15131: Speed up certain Foldable NonEmpty methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.6.1 Component: Core Libraries | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4677 Wiki Page: | -------------------------------------+------------------------------------- Comment (by YitzGale): I just gave one or two examples in the reddit thread, but really all the methods need review. I'm not convinced about the default {{length}} being better. Perhaps switch the order, {{List.length as + 1}}. Does GHC not inline primitive {{+}}? And you do an extra {{+0}}. But if I'm wrong, the clear explanatory comment is highly appreciated. Why not just put the obvious trivial explicit implementation for every method? It would make the code cleaner and easier to read, without having to look up the default and then scratch your head about what gets optimized. Note that for historical reasons several methods for List are still implemented via {{foldl}}. That is in very rare cases better than {{foldl'}}, in many cases the same because GHC optimizes it, and in some cases worse. My opinion is that {{NonEmpty}} should always behave the same as {{List}}, whatever that may be. It's worth it to add one extra operation to the {{NonEmpty}} implementation so that we can refer to the List implementation and not hard-code a copy of it. Here's my alternative "patch" (sorry I don't know how to offer an alternative patch on Phab): {{{ #!haskell instance Foldable NonEmpty where elem x (a :| as) = x == a || x `List.elem` as foldl f z ~(a :| as) = List.foldl f (f z a) as foldl' f z ~(a :| as) = let z' = f z a in z' `seq` foldl' f z' as foldl1 f ~(a :| as) = List.foldl f a as foldr f z ~(a :| as) = f a (List.foldr f z as) foldr1 f ~(a :| as) = List.foldr f a as foldMap f ~(a :| as) = f a `mappend` foldMap f as fold ~(m :| ms) = m `mappend` fold ms length (_ :| as) = List.length as + 1 maximum (a :| as) = max a (List.maximum as) minimum (a :| as) = min a (List.minimum as) null _ = False product (a :| as) = a * List.product as sum (a :| as) = a + List.sum as toList (a :| as) = a : as -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15131#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15131: Speed up certain Foldable NonEmpty methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.6.1 Component: Core Libraries | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4677 Wiki Page: | -------------------------------------+------------------------------------- Comment (by YitzGale): Replying to [comment:3 dfeuer]:

Yours has to hold on to the "and then add one" while calculating the length of the list.

Are you sure GHC doesn't inline the {{{+1}}}? In any case, this is slightly better: {{{#!hs length (_ :| as) = List.foldl' (\c _ -> c+1) 1 as }}}

Same goes for `max` and `min`.

Yes, and also for {{{product}}} and {{{sum}}}, but I did that purposely. I want the semantics to be the same as for {{{List}}}, which is a bit weird because it uses {{{foldl}}}. And I don't want to hard-code a copy of the {{{foldl}}} here. I want it to be fixed automatically if we every get around to fixing it for List. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15131#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#15131: Speed up certain Foldable NonEmpty methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.6.1 Component: Core Libraries | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4677 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"b7139869c3c42c778fa9eb90058439323f548ec2/ghc" b7139869/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="b7139869c3c42c778fa9eb90058439323f548ec2" Improve some Foldable methods for NonEmpty * `length` is improved by using the default definition, while `foldr1` is improved by using a custom one. * Several methods had useless lazy pattern matches (i.e., the functions were actually strict in those arguments). Remove `~`s to clarify. Reviewers: hvr, bgamari, mpickering, nomeata Reviewed By: bgamari Subscribers: ygale, rwbarton, thomie, carter GHC Trac Issues: #15131 Differential Revision: https://phabricator.haskell.org/D4677 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15131#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler