[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:
  mikhail.vorozhtsov                 |
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.0.1
           Keywords:                 |  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:
-------------------------------------+-------------------------------------
 After upgrading to GHC 8.0.1 I've noticed that compilation time of one of
 my libraries got unacceptably long. Please find the attached test case.
 Here are some numbers from my machine:

 {{{
 $ time ~/Prefixes/ghc-7.10.3/bin/ghc -O -c -Rghc-timing TypeList.hs
 Regression.hs
 <<ghc: 19103924976 bytes, 1441 GCs, 73048470/256579104 avg/max bytes
 residency (18 samples), 542M in use, 0.000 INIT (0.002 elapsed), 14.163
 MUT (14.257 elapsed), 5.707 GC (5.830 elapsed) :ghc>>

 real    0m20.160s
 user    0m19.937s
 sys     0m0.197s
 $ time ~/Prefixes/ghc-8.0.1/bin/ghc -O -c -Rghc-timing TypeList.hs
 Regression.hs
 <<ghc: 147662211104 bytes, 9635 GCs, 190336418/433097448 avg/max bytes
 residency (38 samples), 1210M in use, 0.000 INIT (0.001 elapsed), 101.707
 MUT (101.840 elapsed), 27.907 GC (28.259 elapsed) :ghc>>

 real    2m10.195s
 user    2m9.773s
 sys     0m0.400s
 }}}

 Both versions are the official Debian 8 x86_64 binaries from haskell.org.
 I also compiled the git master and unfortunately it is affected as well.

 It is worth mentioning that turning off optimization makes the problem
 disappear:
 {{{
 $ time ~/Prefixes/ghc-8.0.1/bin/ghc -O0 -c -Rghc-timing TypeList.hs
 Regression.hs
 <<ghc: 3779057184 bytes, 225 GCs, 17923355/81566792 avg/max bytes
 residency (8 samples), 164M in use, 0.000 INIT (0.001 elapsed), 2.847 MUT
 (2.941 elapsed), 0.553 GC (0.572 elapsed) :ghc>>

 real    0m3.593s
 user    0m3.507s
 sys     0m0.073s
 }}}

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