Opened 3 years ago

Last modified 9 months ago

#13280 new task

Consider deriving more Foldable methods

Reported by: dfeuer Owned by: dfeuer
Priority: normal Milestone: 8.10.1
Component: Compiler Version: 8.0.1
Keywords: deriving-perf Cc: RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Change History (8)

comment:1 Changed 3 years ago by dfeuer

Owner: set to dfeuer

comment:2 Changed 3 years ago by RyanGlScott

Cc: RyanGlScott added
Keywords: deriving-perf added

comment:3 Changed 2 years ago by dfeuer

Note about length, so I don't forget:

For the nested case,

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

length (Con ... fga ...) = ... + foldl' (\acc x -> acc + length x) 0 fga + ...
Last edited 2 years ago by dfeuer (previous) (diff)

comment:4 Changed 2 years ago by David Feuer <David.Feuer@…>

In bf5e0ea/ghc:

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

comment:5 Changed 2 years ago by bgamari

Milestone: 8.2.18.4.1

Given that 8.2.1-rc1 is imminent, I'm bumping these off to the 8.4

comment:6 Changed 20 months ago by bgamari

Milestone: 8.4.18.6.1

This ticket won't be resolved in 8.4; remilestoning for 8.6. Do holler if you are affected by this or would otherwise like to work on it.

comment:7 Changed 15 months ago by bgamari

Milestone: 8.6.18.8.1

Is there anything else to be done here? Perhaps length?

comment:8 Changed 9 months ago by osa1

Milestone: 8.8.18.10.1

Bumping milestones of low-priority tickets.

Note: See TracTickets for help on using tickets.