[GHC] #12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O)

[GHC]

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level
lists and -O)
-------------------------------------+-------------------------------------
        Reporter:                    |                Owner:  (none)
  mikhail.vorozhtsov                 |
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:  Inlining
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by RyanGlScott):

 Well hot dang. It turns out that commit
 2b74bd9d8b4c6b20f3e8d9ada12e7db645cc3c19 (Stop the specialiser generating
 loopy code) is once again responsible for fixing the problem!

 {{{
 Commit 92a4f908f2599150bec0530d688997f03780646e (Spelling typos)
 <<ghc: 161228659408 bytes, 6342 GCs, 101585298/269563168 avg/max bytes
 residency (15 samples), 712M in use, 0.001 INIT (0.001 elapsed), 53.742
 MUT (53.674 elapsed), 5.431 GC (5.420 elapsed) :ghc>>

 real    0m59.150s
 user    0m59.020s
 sys     0m0.224s

 Commit 2b74bd9d8b4c6b20f3e8d9ada12e7db645cc3c19 (Stop the specialiser
 generating loopy code)
 <<ghc: 7146221432 bytes, 755 GCs, 30379988/108444792 avg/max bytes
 residency (10 samples), 240M in use, 0.001 INIT (0.001 elapsed), 3.583 MUT
 (3.603 elapsed), 0.890 GC (0.888 elapsed) :ghc>>

 real    0m4.549s
 user    0m4.440s
 sys     0m0.096s
 }}}

 For reference, the time for GHC 7.10.3 was:

 {{{
 <<ghc: 19108000616 bytes, 1539 GCs, 62086227/176263896 avg/max bytes
 residency (20 samples), 453M in use, 0.001 INIT (0.001 elapsed), 9.188 MUT
 (9.210 elapsed), 3.974 GC (3.972 elapsed) :ghc>>

 real    0m13.477s
 user    0m13.128s
 sys     0m0.104s
 }}}

 So now it's even //better// than it used to be! That's pretty cool.

 I don't have any particular insight as to why that commit made things so
 much better, but sure enough, `TypeList.hs` contains some classes with
 significant superclasses:

 {{{#!hs
 class (FindElem 'HeadElem a l ~ 'Elem p) => ElemAt p (a :: k) (l :: [k])
 where
   elemWitness :: Proxy a -> Proxy l -> ElemWitness p a l

 class IsElem t (ElemsOf a) => ElemOf a t where
 }}}

 So it's entirely possible that their corresponding dictionaries are just
 getting optimized better. It would be great to have someone verify this at
 the Core level.

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