[GHC] #12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM

[GHC]

#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM
-------------------------------------+-------------------------------------
        Reporter:  slyfox            |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:  deriving-perf
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 Simon Peyton Jones <simonpj@…>):

 In [changeset:"517d03e41b4f5c144d1ad684539340421be2be2a/ghc" 517d03e/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="517d03e41b4f5c144d1ad684539340421be2be2a"
 Fix an asymptotic bug in the occurrence analyser

 Trac #12425 and #12234 showed up a major and long-standing
 bug in the occurrence analyser, whereby it could generate
 explonentially large program!

 There's a lot of commentary on #12425; and it's all described
 in Note [Loop breakers, node scoring, and stability]

 I did quite a lot of refactoring to make the code comprehensibe
 again (its structure had bit-rotted rather), so the patch
 looks bigger than it really is.

 Hurrah!

 I did a nofib run to check that I hadn't inadertently ruined
 anything:

 --------------------------------------------------------------------------------
         Program           Size    Allocs   Runtime   Elapsed  TotalMem
 --------------------------------------------------------------------------------
           fluid          -0.3%     -1.5%      0.01      0.01     +0.0%
          parser          -0.9%     +0.6%      0.04      0.04     +0.0%
          prolog          -0.1%     +1.2%      0.00      0.00     +0.0%

 --------------------------------------------------------------------------------
             Min          -0.9%     -1.5%     -8.6%     -8.7%     +0.0%
             Max          +0.1%     +1.2%     +7.7%     +7.8%     +2.4%
  Geometric Mean          -0.2%     -0.0%     -0.2%     -0.3%     +0.0%

 I checked what happened in 'prolog'.  It seems that we have a
 recursive data structure something like this

    f :: [blah]
    f x = build (\cn.  ...g...  )

    g :: [blah2]
    g y = ....(foldr k z (f y))....

 If we inline 'f' into 'g' we get better fusion than the other
 way round, but we don't have any way to spot that at the moment.
 (I wonder if we could do worker/wrapper for functions returning
 a 'build'?)  It was happening before by a fluke.

 Anyway I decided to accept this; it's relatively rare I think.
 }}}

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