[GHC] #13379: Space leak / quadratic behavior when inlining

[GHC]

#13379: Space leak / quadratic behavior when inlining
-------------------------------------+-------------------------------------
        Reporter:  jberryman         |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             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:                    |
-------------------------------------+-------------------------------------

Comment (by jberryman):

 Still looking into this slowly when I have time. It looks like this is a
 regression between ghc-7.10 and 8.0.1 at least. Here e.g. `# 50 lines` etc
 refers to 50 lines of

 {{{
 f bs >> f bs >> f bs >> f bs >> f bs >> f bs >> f bs >> f bs >> f bs >> f
 bs >> f bs >> f bs >> f bs >> f bs >> f bs >> f bs >>
 }}}

 With ghc 7.10 this looks slow but linear:

 {{{
 jberryman /tmp/again » time ghc-7.10.3  -fforce-recomp -O2 Main.hs # 25
 lines
 [1 of 1] Compiling Main             ( Main.hs, Main.o )
 Linking Main ...
 ghc-7.10.3 -fforce-recomp -O2 Main.hs  0.90s user 0.09s system 97% cpu
 1.018 total
 jberryman /tmp/again » time ghc-7.10.3  -fforce-recomp -O2 Main.hs # 50
 lines
 [1 of 1] Compiling Main             ( Main.hs, Main.o )
 Linking Main ...
 ghc-7.10.3 -fforce-recomp -O2 Main.hs  1.59s user 0.13s system 98% cpu
 1.744 total
 jberryman /tmp/again » time ghc-7.10.3  -fforce-recomp -O2 Main.hs # 100
 lines
 [1 of 1] Compiling Main             ( Main.hs, Main.o )
 Linking Main ...
 ghc-7.10.3 -fforce-recomp -O2 Main.hs  3.87s user 0.25s system 99% cpu
 4.146 total
 }}}

 And in 8.0 we have a regression and what looks like worse asymptotics:

 {{{
 jberryman /tmp/again » time ghc  -fforce-recomp -O2 Main.hs # 25 lines
 [1 of 1] Compiling Main             ( Main.hs, Main.o )
 Linking Main ...
 ghc -fforce-recomp -O2 Main.hs  2.41s user 0.15s system 99% cpu 2.583
 total
 jberryman /tmp/again » time ghc  -fforce-recomp -O2 Main.hs # 50 lines
 [1 of 1] Compiling Main             ( Main.hs, Main.o )
 Linking Main ...
 ghc -fforce-recomp -O2 Main.hs  7.36s user 0.21s system 99% cpu 7.586
 total
 jberryman /tmp/again » time ghc  -fforce-recomp -O2 Main.hs # 100 lines
 [1 of 1] Compiling Main             ( Main.hs, Main.o )
 Linking Main ...
 ghc -fforce-recomp -O2 Main.hs  27.99s user 0.45s system 99% cpu 28.463
 total
 jberryman /tmp/again » time ghc  -fforce-recomp -O2 Main.hs # 200 lines
 [1 of 1] Compiling Main             ( Main.hs, Main.o )
 Linking Main ...
 ghc -fforce-recomp -O2 Main.hs  122.58s user 6.40s system 84% cpu 2:33.50
 total
 }}}

 Also attached profiles using the ghc library via
 https://gist.github.com/nominolo/d18efaabf3e074d03969

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