#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 rwbarton): Even the space usage is quadratic, so something does seem amiss here. I recommend cutting the example down to at most 100 lines if you want to compile it in a reasonable amount of time. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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):

How did an example like this arise in practice?

In attempting to space profile some code where there seemed to be a constant small amount of allocation at each call site I tried creating a file like this one. I filed the bug because it seemed likely that this was evidence of performance issues in more realistic code.

I'm not too surprised this is a difficult case ... we end up (eventually) re-associating everything the other way

Ah, interesting! This does seem to be related to `(>>)` and not the code I marked `INLINE` in the Main file. The code compiles quickly with: {{{ import Prelude hiding ((>>)) import qualified Prelude as P infixr 1 >> {-# NOINLINE (>>) #-} (>>) = (P.>>) }}} The NOINLINE is necessary, and we see `f` get inlined everywhere. But my naive response, knowing nothing about how to implement an inliner, and looking at a 191kb core file with a bunch of nested: {{{ of _ [Occ=Dead] { (# ipv, ipv1 #) -> case hPutStr2 stdout ipv1 True ipv of _ [Occ=Dead] { (# ipv2, ipv3 #) -> case hPutStr2 stdout ipv1 True ipv2 of _ [Occ=Dead] { (# ipv4, ipv5 #) -> case hPutStr2 stdout ipv1 True ipv4 of _ [Occ=Dead] { (# ipv6, ipv7 #) -> case hPutStr2 stdout ipv1 True ipv6 ... }}} ...is that I could do this inlining case manually in milliseconds (vs ~40 seconds for whatever number of lines I was just testing with) with vim, sed, a bash script, etc. and without GB of memory for my working set. And so I am inclined to believe that there is a space leak here. Who knows if real code will benefit from fixing it though. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: dfeuer (added) Comment: If the `NOINLINE` is necessary, then I think I must be quite wrong about the source of the problem. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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

#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: | -------------------------------------+------------------------------------- Changes (by jberryman): * Attachment "ghc-wrap.h.7.10.pdf" added. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Changes (by jberryman): * Attachment "ghc-wrap.h.8.0.pdf" added. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 dfeuer): I'm working on bisecting this now. Unfortunately, the version/time function is far from monotone, so there may well be multiple issues involved. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: 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: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => Inlining -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): The first weird thing to notice about this problem is that 45d9a15c4b85a2ed89579106bdafd84accf2cb39 is all about LHSes of `RULES`, but there ''aren't any'' rules in the test module. So something seems to have gone wrong with one of the "knock on" changes. Compiling before and after with `-v3` indicates that the simplifier iteration immediately after float out takes ''much'' longer, and produces somewhat more coercions. That iteration takes many times longer than any other. Most of the coercions, before and after, go away after that iteration, stabilizing quickly at 19. Surprisingly, `-dverbose-core2core` looks exactly the same before and after that commit, suggesting something went funny with the size calculations, although I can't see how. In HEAD, the number of coercions never goes up above 19. Furthermore, the time problem has ''moved''. Now, the long iteration is the very first one after desugaring! Ugh. I haven't yet tried to find where the time shift took place. But the fact that there ''was'' one makes me suspect that the new implementation could have accidentally strictified something it shouldn't have. I don't understand what's going on well enough to know what. Perhaps the fact that a couple pure functions have turned monadic? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

...

In HEAD [...] the time problem has moved. Now, the long iteration is

#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: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:14 MikolajKonarski]: the very first one after desugaring

May it have anything to do with the "early inlining" changes?

Simon thinks so. And he thinks this whole problem has to do with simplifying the same expressions many times. Simon, have you worked out how to fix this yet? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"a1b753e8b1475659440f524b3e66dfbea31c5787/ghc" a1b753e8/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="a1b753e8b1475659440f524b3e66dfbea31c5787" Cure exponential behaviour in the simplifier This patch nails a Bad Bug exposed in Trac #13379. Roughly, a deeply-nested application like f (f (f ....) ) ) could make the simplifier go exponential -- without producing an exponential-sized result! The reason was that we - simplified a (big) function argument - then decided to inline the function - then preInilneUnconditionally the argument - and then re-simplified the big argument And if the "big argument" itself had a similar structure things could get very bad. Once I'd understood, it was easy to fix: * See Note Note [Avoiding exponential behaviour] for an overview * The key change is that Simplify.simplLam now as a case for (isSimplified dup). This is what removes the perf bug. * But I also made simplCast more parsimonious about simplifying, avoiding doing so when the coercion is Refl * And similarly I now try to avoid simplifying arguments where possible before applying rules. See Note [Trying rewrite rules] The latter two points tackle common cases, and in those cases make the simplifier take fewer iterations. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: (none) Type: bug | Status: merge Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * testcase: => perf/compile/T13379 * status: new => merge Comment: I claim this is fixed. The second patch fixes a problem that the first one exposed; so merge them both. Would someone like to verify it's fixed in real live contexts? The `Main.hs` attachement is ok -- it's in the regression tests now. I forgot to mention, but the first (main) patch produces some perf improvements in `tests/perf/compiler`: {{{ T9020: 14% reduction in compiler allocation T12425: 5% reduction in compiler allocation }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: merge => closed * resolution: => fixed Comment: comment:17 merged to `ghc-8.2` as 09249f93089517ace8aae6d0652716f6fac18e3e and comment:18 as f9aa658ba8293832a6622323b58063a379b16901. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by George): * cc: George (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: closed => new * resolution: fixed => -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Indeed it probably would be better. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by jberryman): I forgot to add: I haven't checked out a build with the fix here to see if it fixes this other performance issue, but their test case seems to be very similar to mine and I assume suffering from the same issue. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by jberryman): My thought was that the issue (long compilation times) was not actually primarily due to the linear extra simplifying of each unoptimized callsite, but rather the bug here. At least this seems consistent with the test case phadej posted to me (runtime quadratic in occrrences of "char7 <>"). I don't have any other context for the issue though. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:31 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13379: Space leak / quadratic behavior when inlining -------------------------------------+------------------------------------- Reporter: jberryman | Owner: dfeuer Type: bug | Status: new Priority: normal | Milestone: 8.2.2 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compile/T13379 Blocked By: | Blocking: Related Tickets: #13586 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * owner: (none) => dfeuer -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13379#comment:33 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler