[GHC] #13280: Consider deriving more Foldable methods
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Runtime Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- We currently derive `foldMap` and `foldr`, but some others may deserve attention as well. * The most critical spots are probably `length` and `null`. Deriving these instead of using the defaults can change the orders of growth! Given `data Tree a = Bin !(Tree a) a !(Tree a) | Tip`, we surely don't want `null` to traverse the whole spine of the tree when it's quite immediately obvious that `Bin` is never null. And if a constructor contains a type with a very efficient `length` or `null` implementation (e.g., one that stores its own size), we certainly want to use that. * `foldl` typically ends up with rather different code than `foldr` (for a recursive type) even after simplification. We need to check whether this has a performance impact, but my bet is that it will in cases where the optimizer can't understand what's going on well enough. * `foldl'` and `foldr'` are a bit tricky. Ideally, if we have something like `data T a = C (G a) a | ...` then we'd like to be able to use `G`'s `foldl'` definition to define `T`'s. Unfortunately, different types in the wild have different `foldl'` semantics (and indeed the semantics for `[]` changed by mistake fairly recently). So we have to decide to what extent the derived semantics should depend on the choices of included types. I think we should probably just depend, because that seems likely what people will expect and want. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13280> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 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): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * owner: (none) => dfeuer -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13280#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) * keywords: => deriving-perf -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13280#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Note about `length`, so I don't forget: For the nested case, {{{#!hs Con ... f (g a) ... }}} the way to make sure we never do worse than the default `length` definition (assuming the recursively called `length` is good) is to use {{{#!hs length (Con ... fga ...) = ... + foldl' (\acc x -> acc + length x) 0 fga + ... }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13280#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by David Feuer <David.Feuer@…>): In [changeset:"bf5e0eab60a11d494671793740122e381a707c1a/ghc" bf5e0ea/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="bf5e0eab60a11d494671793740122e381a707c1a" Derive the definition of null We can sometimes produce much better code by deriving the definition of `null` rather than using the default. For example, given data SnocList a = Lin | Snoc (SnocList a) a the default definition of `null` will walk the whole list, but of course we can stop as soon as we see `Snoc`. Similarly, if a constructor contains some other `Foldable` type, we want to use its `null` rather than folding over the structure. Partially fixes Trac #13280 Reviewers: austin, bgamari, RyanGlScott Reviewed By: RyanGlScott Subscribers: rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D3402 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13280#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: 8.6.1 => 8.8.1 Comment: Is there anything else to be done here? Perhaps `length`? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13280#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC