[GHC] #8095: TypeFamilies painfully slow

[GHC]

#8095: TypeFamilies painfully slow
-------------------------------------+-------------------------------------
       Reporter:  MikeIzbicki        |             Owner:
           Type:  bug                |            Status:  new
       Priority:  normal             |         Milestone:
      Component:  Compiler (Type     |           Version:  7.6.3
  checker)                           |  Operating System:  Unknown/Multiple
       Keywords:                     |   Type of failure:  Compile-time
   Architecture:  Unknown/Multiple   |  performance bug
     Difficulty:  Unknown            |         Test Case:
     Blocked By:                     |          Blocking:
Related Tickets:  5321               |
-------------------------------------+-------------------------------------
 I'm using the TypeFamilies extension to generate types that are quite
 large.  GHC can handle these large types fine when they are created
 manually, but when type families get involved, GHC's performance dies.

 Unlike in ticket #5321, using tail recursion does not eliminate the
 problem, and the order of arguments greatly affects compile time.

 I've attached a file Types.hs that demonstrates the problems.  This file
 generates another Haskell file which has the problems.  It takes 3 flags.
 The first is the size of the type to generate, the second is which type
 family function to use, and the third is whether to call the type family
 or just use a manually generated type.

 Here are my performance results:

 Using non-tail recursion, I get these results.  I have to increase the
 stack size based on the size of the type I want to generate.

 {{{
 $ ./Types 200 a a > test.hs && time ghc test.hs > /dev/null -fcontext-
 stack=250
 real    0m2.973s
 $ ./Types 300 a a > test.hs && time ghc test.hs > /dev/null -fcontext-
 stack=350
 real    0m6.018s
 $ ./Types 400 a a > test.hs && time ghc test.hs > /dev/null -fcontext-
 stack=450
 real    0m9.995s
 $ ./Types 500 a a > test.hs && time ghc test.hs > /dev/null -fcontext-
 stack=550
 real    0m15.645s
 }}}
 Tail recursion generates much slower compile times for some reason, and I
 still need to adjust the stack size:
 {{{
 $ ./Types 200 b a > test.hs && time ghc test.hs > /dev/null -fcontext-
 stack=250
 real    0m16.120s
 }}}
 Changing the order of arguments to the recursive type family greatly
 changes the run times:
 {{{
 $ ./Types 200 c a > test.hs && time ghc test.hs > /dev/null -fcontext-
 stack=250
 real    0m6.095s
 }}}
 Without the type family, I get MUCH better performance:
 {{{
 $ ./Types 10000 a d > test.hs && time ghc test.hs > /dev/null
 real    0m2.271s
 }}}

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