Opened 3 years ago

Closed 3 years ago

#12990 closed bug (fixed)

Partially applied constructors with unpacked fields simplified badly

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

Description (last modified by bgamari)

When a constructor is partially applied to at least one unpacked field, the simplifier produces pretty lousy results.

data Foo a = Foo !Int a

silly :: ((a -> Foo a) -> r) -> r
silly f = f (Foo 3)

compiles to

-- RHS size: {terms: 9, types: 7, coercions: 0}
$WFoo :: forall a. Int -> a -> Foo a
$WFoo =
  \ (@ a_aqI) (dt_ayl :: Int) (dt_aym :: a_aqI[sk:1]) ->
    case dt_ayl of { I# dt_ayn -> Foo dt_ayn dt_aym }

-- RHS size: {terms: 2, types: 0, coercions: 0}
silly2 :: Int
silly2 = I# 3#

-- RHS size: {terms: 3, types: 3, coercions: 0}
silly1 :: forall a. a -> Foo a
silly1 = \ (@ a_ayG) -> $WFoo silly2

-- RHS size: {terms: 5, types: 9, coercions: 0}
silly :: forall a r. ((a -> Foo a) -> r) -> r
silly =
  \ (@ a_ayG) (@ r_ayH) (f_axY :: (a -> Foo a) -> r) -> f_axY silly1

That is, GHC represents Foo 3 as a closure containing a boxed Int. Manually eta-expanding would fix it.

silly :: ((a -> Foo a) -> r) -> r
silly f = f (\x -> Foo 3 x)

compiles to

-- RHS size: {terms: 5, types: 4, coercions: 0}
silly1 :: forall a. a -> Foo a
silly1 = \ (@ a_ayO) (x_ay9 :: a) -> Foo 3# x_ay9

-- RHS size: {terms: 5, types: 9, coercions: 0}
silly :: forall a r. ((a -> Foo a) -> r) -> r
silly =
  \ (@ a_ayO) (@ r_ayP) (f_ay8 :: (a -> Foo a) -> r) -> f_ay8 silly1

in which the Int is unpacked into the closure. This transformation is valid whenever the value to be stored unpacked is known not to be bottom, and is certainly a good idea if it's known to have been forced.

Change History (11)

comment:1 Changed 3 years ago by rwbarton

Inlining $WFoo into silly1 and then beta-reducing would also fix it (case of known constructor). I think that GHC thinks the inlining will be fruitless here for some reason.

comment:2 Changed 3 years ago by dfeuer

Actually, I guess the eta-expansion per se is always safe (because a strict constructor can never have a weird arity), and will lead to case-of-known-constructor when relevant. I don't have any opinion whatsoever about exactly how this should be fixed; I just want it fixed. I've had to write some unpleasantly long-winded code in containers to work around this. It shows up all over Traversable things, for instance.

data Node = Node2 !Int a a | Node3 !Int a a a
instance Traversable Node where
  traverse f (Node2 sz x y) =
    Node2 sz <$> f x <*> f y
  ...

is no good; GHC would box up the node size (which starts out unboxed!) just to put it in the closure passed to fmap.

Last edited 3 years ago by dfeuer (previous) (diff)

comment:3 Changed 3 years ago by simonpj

In MkId line 511 we have

             wrap_unf = mkInlineUnfolding (Just wrap_arity) wrap_rhs

The Just wrap_arity is what prevents GHC inlining the wrapper until it is saturated. Change it to Nothing to allow a partially-applied wrapper to inline.

Worth a try. I doubt it'd have any bad effects.

comment:4 Changed 3 years ago by mpickering

Keywords: Inlining added

comment:5 Changed 3 years ago by RyanGlScott

Cc: RyanGlScott added

comment:6 in reply to:  3 Changed 3 years ago by dfeuer

Replying to simonpj:

In MkId line 511 we have

             wrap_unf = mkInlineUnfolding (Just wrap_arity) wrap_rhs

The Just wrap_arity is what prevents GHC inlining the wrapper until it is saturated. Change it to Nothing to allow a partially-applied wrapper to inline.

Worth a try. I doubt it'd have any bad effects.

There's a comment right above that I don't know enough about GHC to interpret:

The Cpr info can be important inside INLINE rhss, where the wrapper constructor isn't inlined. And the argument strictness can be important too; we may not inline a constructor when it is partially applied. For example:

data W = C !Int !Int !Int
...(let w = C x in ...(w p q)...)...

we want to see that w is strict in its two arguments

Does this point to a reason not to inline partially-applied wrappers? If not, does it point to some additional change that should be made in parallel? Or does it become obsolete with this change?

comment:7 Changed 3 years ago by simonpj

No, it's fine. In the example, if we inline C we get

...(let w = \pq. case x of I# x1
                 case p of I# p1 ->
                 case q of I# q1 ->
                 C x1 p1 q1
    in ...(w p q)...)...

which is fine. The comment was just saying that if we choose not to inline then we do want w to see the strictness via C's strictness signature.

So please do give it a try.

comment:8 Changed 3 years ago by dfeuer

Differential Rev(s): D2891
Status: newpatch

The change Simon suggests does indeed seem to work. I get the code I want from my Traversable test case now.

comment:9 Changed 3 years ago by bgamari

Description: modified (diff)

comment:10 Changed 3 years ago by David Feuer <David.Feuer@…>

In 2be364ac/ghc:

Inline partially-applied wrappers

Suppose we have

```
data Node a = Node2 !Int a a | Node3 !Int a a a
instance Traversable Node where
  traverse f (Node2 s x y) = Node2 s <$> f x <*> f y
  ...

```

Since `Node2` is partially applied, we wouldn't inline its
wrapper.  The result was that we'd box up the `Int#` to put
the box in the closure passed to `fmap`. We now allow the wrapper
to inline when partially applied, so GHC stores the `Int#`
directly in the closure.

Reviewers: rwbarton, mpickering, simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: mpickering, thomie

Differential Revision: https://phabricator.haskell.org/D2891

GHC Trac Issues: #12990

comment:11 Changed 3 years ago by dfeuer

Milestone: 8.2.1
Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.