[GHC] #11196: TypeInType performance regressions

[GHC]

#11196: TypeInType performance regressions
-------------------------------------+-------------------------------------
        Reporter:  goldfire          |                Owner:
            Type:  bug               |               Status:  new
        Priority:  high              |            Milestone:  8.0.2
       Component:  Compiler          |              Version:  7.11
      Resolution:                    |             Keywords:  TypeInType
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by goldfire):

 I had a thought while falling asleep last night about what may be causing
 all of this.

 Previously, `Type` had a constructor `FunTy :: Type -> Type -> Type`. Now,
 the situation is more complex, with a `TyBinder`:

 {{{#!hs
 data Type = ... | ForAllTy TyBinder Type | ...
 data TyBinder = Named TyVar VisibilityFlag | Anon Type
 }}}

 What was `FunTy arg res` is now `ForAllTy (Anon arg) res`. But this
 refactoring means that we have an extra box for ''every'' function type.
 And there are a lot of those. Chasing all of these boxes might mean that
 everything goes just a bit slower... which is exactly what I've observed.

 This refactoring was not forced by `TypeInType`, but Simon and I thought
 it to be a good idea. It does simplify things in a bunch of places. It
 could be undone -- somewhat labor-intensive, but not theoretically hard.
 Even better would be to have unboxed and unpacked sums, which would allow
 GHC to inline `TyBinder` into `Type`. It also might be possible to
 simulate unboxed and unpacked sums through something like this:

 {{{#!hs
 data Type = ...
           | ForAllTyNamed TyVar VisibilityFlag Type
           | ForAllTyAnon Type Type
           | ...

 repSplitForAllTy :: Type -> Maybe (TyBinder, Type)
 repSplitForAllTy (ForAllTyNamed tv vis ty) = Just (Named tv vis, ty)
 repSplitForAllTy (ForAllTyAnon arg res)    = Just (Anon arg, res)
 repSplitForAllTy _                         = Nothing

 pattern ForAllTy :: TyBinder -> Type -> Type
 pattern ForAllTy bndr ty <- (repSplitForAllTy -> Just (bndr, ty))
   where
     ForAllTy (Named tv vis) ty = ForAllTyNamed tv vis ty
     ForAllTy (Anon arg) res    = ForAllTyAnon arg res
 }}}

 With these definitions, it would seem you could use `ForAllTy` just as it
 is done now. And my guess is that matching against, say `(ForAllTy (Anon
 arg) res) -> ...`, as is done somewhat frequently, would induce GHC to
 inline all of the splitting and matching (and allocation of the very-
 temporary `TyBinder`). That would need to be tested. But perhaps this is
 the answer to our woes.

 If it's performant, this would also be a good recipe to disseminate to
 people clamoring for unboxed, unpackable sums. With the forthcoming
 support for pattern synonyms in TH (not for 8.0! but likely for 8.2), this
 might even be possible to automate and implement unpacked sums in TH until
 GHC can support them for real.

 I won't be testing this anytime soon, sadly. Perhaps someone else can in
 time for 8.0.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11196#comment:14>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler