[GHC] #8095: TypeFamilies painfully slow

[GHC]

#8095: TypeFamilies painfully slow
-------------------------------------+-------------------------------------
        Reporter:  MikeIzbicki       |                Owner:  goldfire
            Type:  bug               |               Status:  new
        Priority:  high              |            Milestone:  8.4.1
       Component:  Compiler (Type    |              Version:  7.6.3
  checker)                           |
      Resolution:                    |             Keywords:  TypeFamilies
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #5321, #11598,    |  Differential Rev(s):
  #12506                             |
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by mbieleck):

 Thanks for the response.

 Replying to [comment:36 goldfire]:
 > Using `mkUnsafeCo` should happen only from `unsafeCoerce#`. There's
 nothing unsafe going on here, yet the Core code will be littered with what
 appear to be unsafe coercions.

 I realize that. I just picked any variant of `UnivCo` to quickly test if
 this has any chance of working (and actually improving compile times). Of
 course the right thing to do is to introduce a new `UnivCoProvenance`
 specifically for this case.

 > By the way, I say "may fix" above because this approach might still
 create the coercion, only to throw it away. If we prevent the creation of
 the coercion a little earlier, we might have more luck.

 Yes, it might still create the coercion, but at least it will prevent the
 simplifier from processing it repeatedly later.

 > I don't think the simple solution here is quite the right approach that
 will continue to work in the long term.

 Who said we can't make incremental improvements? If this would be put
 behind a flag, it should not harm anyone.

 For the record, here are some timing results (using Types.hs from the
 ticket):

 {{{
 $ ./timing.sh
 GHC=inplace/bin/ghc-stage2
     N        old       omit   old_tail  omit_tail
   200   0m0.465s   0m0.404s   0m1.674s   0m0.445s
   400   0m0.695s   0m0.504s  0m10.745s   0m0.645s
   600   0m1.077s   0m0.614s  0m28.975s   0m0.985s
   800   0m1.565s   0m0.755s    timeout   0m1.446s
  1000   0m2.225s   0m1.075s    timeout   0m2.435s
  1200   0m3.167s   0m1.426s    timeout   0m3.575s
  1400   0m4.236s   0m1.705s    timeout   0m5.045s
  1600   0m5.786s   0m1.654s    timeout   0m4.775s
  1800   0m5.756s   0m1.955s    timeout   0m6.156s
  2000   0m7.215s   0m3.106s    timeout   0m9.865s
 }}}

 `old` is the default behavior, `omit` is my patch. `_tail` variants use
 the tail recursive type family.

 The reason I'm so desperate is that it greatly affects my code. I'm using
 extensible (Vinyl) records computed using some type families. For bigger
 records, GHC just runs out of memory. This patch helps.

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