[GHC] #9872: Runing type functions is too slow

[GHC]

#9872: Runing type functions is too slow
-------------------------------------+-------------------------------------
              Reporter:  simonpj     |            Owner:
                  Type:  bug         |           Status:  closed
              Priority:  normal      |        Milestone:
             Component:  Compiler    |          Version:  7.8.3
            Resolution:  fixed       |         Keywords:
      Operating System:              |     Architecture:  Unknown/Multiple
  Unknown/Multiple                   |       Difficulty:  Unknown
       Type of failure:              |       Blocked By:
  None/Unknown                       |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by goldfire):

 I have some work-in-progress [https://github.com/goldfirere/ghc/tree/wip
 /opt-flatten here] that cuts allocation amounts for the T9872x cases by
 half. I'm still twiddling knobs to find the best combination of settings,
 but the high-order bit is this: try to reduce a type family (in
 `flatten_exact_fam_app_fully`) '''before''' flattening the arguments. Only
 if that fails do we flatten the arguments.

 This works well if we have something like

 {{{
 type family F a where
   F a = G a
 type family G a
 type family H a where
   H Bool = Char
 }}}

 and we call `F (H Bool)`. The current (HEAD) flattener will flatten `H
 Bool`, then reduce `F Char` to `G Char`, then flatten `Char` ''again'',
 then try to reduce `G Char`. With my patch, it just reduces `F (H Bool)`
 to `G (H Bool)`, then tries to reduce `G`, fails, and then reduces `H
 Bool` to `Char`. This saves one flattening. But, you can imagine it saving
 a lot more (and it does, in practice).

 On current tests, it works better not to use the flat-cache (which amounts
 to memoization of type-level functions) for this very-eager reduction.
 I'll look forward to trying Janek's tests, which satisfies a direct need:
 I've been worried that I'm overspecializing to the existing tests, and
 fresh tests will help.

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