Opened 2 years ago

Last modified 16 months ago

#11068 new bug

Make Generic/Generic1 methods inlinable

Reported by: glguy Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.10.2
Keywords: Generics, newcomer, Inlining Cc: kosmikus, dreixel, RyanGlScott, sweirich
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D1447
Wiki Page:

Description

Efficient code generation with GHC.Generics relies on the optimizer being able to completely remove the generic representation of a type. Marking these methods as inlinable ensures that this will be possible even for larger types.

I'm working on techniques for transforming generically derived lenses and traversals which rely on taking advantage of the Functor and Applicative laws. This patch supports that work.

https://github.com/glguy/generic-traverse

Change History (11)

comment:1 Changed 2 years ago by glguy

Differential Rev(s): D1447Phab:D1447

comment:2 Changed 2 years ago by dreixel

INLINABLE on these methods definitely sounds like a good idea to me. Are there any concerns regarding interface file size increase?

comment:3 Changed 2 years ago by osa1

I remember chatting with some people at ICFP about optimizing Generics code. The problem was that sometimes GHC is able to optimize Generics-based code so that it doesn't use Generics methods anymore. For example, using Generics-based default method of NFData sometimes works well, generated code is same as hand-written code. But in some cases it never optimizes enough to eliminate Generics methods. For example, in my tests I was never able to eliminate Generics methods in Generics-based default implementation of Binary. I'm wondering if after this patch GHC is able to optimize such instances. @glguy have you tried anything like this?

Looks like a good improvement to me, +1.

comment:4 Changed 2 years ago by simonpj

Cc: kosmikus dreixel added

Sounds interesting! Do you have a human-readable description of

  • the problem you are trying to solve; e.g. is it precisely the problem described in Pedro's papers "Optimisation of Generic Programs through Inlining" and "Optimizing SYB is Easy!")?
  • the approach you are taking to solve it?

Adding Andres (kosmikus) who is in charge of generics in GHC, and Pedro (dreixel).

Simon

comment:5 Changed 2 years ago by glguy

Hi Simon,

The problem I'm working on is indeed related to José's work. I'm solving the problem that GHC doesn't use Appliative and Functor laws to rewrite code using Haskell instead of rewrite rules. I "run" the code at a lifted version of the desired type f that uses the Applicative laws to rewrite a term to be left associated in the <*>s and using a single <$>.

Using this technique allows me to derive efficient code that is generic in terms of Functor and Applicative on a case by case basis rather than with global rules.

type Traversal' s a = forall f. Applicative f => (a -> f a) -> s -> f s

badTraversal :: Traversal' (Int,Int,Int) Int 
badTraversal f (x,y,z) =
  pure (\x' (y',z') -> (x',y',z')) <*> f x <*> ((,) <$> f y <*> f z)

goodTraversal :: Traversal' (Int,Int,Int) Int
goodTraversal = boggling badTraversal
-- generated core is roughly: \f (x,y,z) -> (,,) <$> f x <*> f y <*> f z

The code from badTraversal could have been easily generated using GHC.Generics, but the efficient version can be recovered using the boggling operation defined in repository mentioned above.

As far as my request to add the inline pragma, I think I might have misunderstood what GHC was doing. My goal was to ensure that from/to/from1/to1 would be able to inline across module boundaries even when their definitions were large due to the type being large. However after revisiting my test case I was struggling to reproduce that the change fixed anything, so I closed the change request (but forgot to change this ticket)

Last edited 2 years ago by glguy (previous) (diff)

comment:6 Changed 23 months ago by bgamari

Cc: RyanGlScott added

Adding RyanGlScott who has done some great work with generics recently.

comment:7 Changed 23 months ago by thomie

Keywords: Generics added

comment:8 Changed 17 months ago by mpickering

Keywords: newcomer Inlining added

comment:9 Changed 17 months ago by RyanGlScott

mpickering, you marked this as newcomer, but I'm not sure how easy this is to get right. glguy already tried to fix this with https://phabricator.haskell.org/D1447, but he remarked in comment:5 that he "was struggling to reproduce that the change fixed anything". glguy, what exactly did you mean by this? I think some clarification on what the challenge here is would be needed before someone tries to dive in on this.

Last edited 16 months ago by RyanGlScott (previous) (diff)

comment:10 Changed 17 months ago by mpickering

There is at least some investigative work to be done. It seems no one has checked whether the unfoldings of from, to, from1 , to1 were ever making it into the interface files. If they are, then adding an inlinable pragma won't achieve anything but if they aren't then it is probably worth adding the pragma as Pedro suggested. Feel free to remove the tag if you disagree.

comment:11 Changed 16 months ago by sweirich

Cc: sweirich added
Note: See TracTickets for help on using tickets.