GHC: Ticket #7428: GHC compile times are seriously non-linear in program size
http://ghc.haskell.org/trac/ghc/ticket/7428
<p>
When compiling the attached code with -O2 GHC runs out of memory. Experimenting with different monad stacks shows exponential memory usage.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/7428
Trac 1.0.7nuddedMon, 19 Nov 2012 08:50:02 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>cont-state8.hs</em>
</li>
</ul>
TicketnuddedMon, 19 Nov 2012 08:52:37 GMTfailure changed
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:1
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:1
<ul>
<li><strong>failure</strong>
changed from <em>Compile-time performance bug</em> to <em>Compile-time crash</em>
</li>
</ul>
TicketsimonpjMon, 19 Nov 2012 08:59:38 GMTdifficulty set
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:2
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:2
<ul>
<li><strong>difficulty</strong>
set to <em>Unknown</em>
</li>
</ul>
<p>
Thank you. We know there's a performance bug in the occurrence analyser (see <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/7258" title="bug: Compiling DynFlags is jolly slow (new)">#7258</a>), but it's very helpful to have a small case that tickles it. Two questions
</p>
<ul><li>How do you know it's the occurrence analyser at fault?
</li><li>Can you be specific about the changes you made to the test program that showed you the memory behaviour was exponential (ugh).
</li></ul><p>
Thanks
</p>
<p>
Simon
</p>
TicketnuddedMon, 19 Nov 2012 09:04:47 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:3
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:3
<p>
I used several debug flags. The output of dump-occur-anal seems to increase in size when adjusting the size of the LargeState transformer stack. So, in the attached code LargeState consists of 10 StateT transformers.
</p>
<p>
When compiling with 7 it will still work. When compiling with 8 it will try to allocate > 4 gigs of memory.
</p>
<p>
Those are some of the observations I ran into when trying to figure out what is going on.
</p>
<p>
Sidenote: when compiling without optimisation there is no problem at all.
</p>
TicketnuddedMon, 19 Nov 2012 09:08:08 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>cont-state.hs</em>
</li>
</ul>
TicketnuddedMon, 19 Nov 2012 09:08:23 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>cont-state2.hs</em>
</li>
</ul>
TicketnuddedMon, 19 Nov 2012 09:09:06 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:4
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:4
<p>
I added 2 files with stack size 1 and stack size 2.
</p>
TicketnuddedMon, 19 Nov 2012 11:11:54 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>ghc-stage2.prof</em>
</li>
</ul>
TicketnuddedMon, 19 Nov 2012 11:12:41 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:5
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:5
<p>
Profiling output when compiling with 7 StateT transformers.
</p>
TicketnuddedMon, 26 Nov 2012 09:24:57 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:6
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>invalid</em>
</li>
</ul>
<p>
Since after more analysis this doesn't seem to be related to the occurrence analyzer I'm closing this as invalid.
</p>
TicketsimonpjMon, 26 Nov 2012 22:00:56 GMTstatus, summary changed; resolution deleted
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:7
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:7
<ul>
<li><strong>status</strong>
changed from <em>closed</em> to <em>new</em>
</li>
<li><strong>resolution</strong>
<em>invalid</em> deleted
</li>
<li><strong>summary</strong>
changed from <em>Occurrence analyzer out of memory</em> to <em>GHC compile times are seriously non-linear in program size</em>
</li>
</ul>
<p>
I'm re-opening becuase I believe <tt>nudded</tt> is telling us that compilation times are seriously non-linear in program size. That should not happen. Moreover you were kind enough to profile the compiler and in the profile you gave it seems that 64% of all allocation is in <tt>MkIface.addFingerprints</tt> which is not supposed to be an expensive function.
</p>
<p>
Could you help us some more?
</p>
<ul><li>Give a table of compile times against program size (or number of state transformers)
</li><li>Explain exactly how to reproduce (what flags, what changes to make to the code to make N=1, N=2, N=4, etc
</li><li>Use <tt>-dshow-passes</tt> to see if the size of the simplified program is blowing up
</li><li>If you feel up to it, drill down into <tt>addFingerprints</tt> to see where the time is going.
</li></ul><p>
Thanks!
</p>
<p>
Simon
</p>
TicketparcsFri, 08 Mar 2013 01:06:13 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>output.log</em>
</li>
</ul>
<p>
output of <tt>ghc-stage2 -O2 cont-state8.hs -fforce-recomp -Wall -v +RTS -M1G -RTS</tt>
</p>
TicketparcsFri, 08 Mar 2013 01:06:42 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>cont-state8-cleaned-up.hs</em>
</li>
</ul>
TicketparcsFri, 08 Mar 2013 01:08:52 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:8
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:8
<p>
I've attached a cleaned-up version of <tt>cont-state8.hs</tt> and an output log of <tt>ghc-stage2 -O2 cont-state8.hs -fforce-recomp -Wall -v +RTS -M1G -RTS</tt> to help move this ticket forward.
</p>
TicketiglooFri, 12 Apr 2013 19:00:43 GMTmilestone set
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:9
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:9
<ul>
<li><strong>milestone</strong>
set to <em>7.8.1</em>
</li>
</ul>
TicketsimonmarFri, 27 Sep 2013 00:51:44 GMTpriority changed
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:10
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:10
<ul>
<li><strong>priority</strong>
changed from <em>normal</em> to <em>high</em>
</li>
</ul>
<p>
Simon - this looks like a real issue. The types blow up during successive simplification stages, look at this:
</p>
<pre class="wiki">*** Float inwards:
Result size of Float inwards
= {terms: 985, types: 6,189, coercions: 267}
*** Simplifier:
Result size of Simplifier iteration=1
= {terms: 4,502, types: 100,514, coercions: 35,229}
Result size of Simplifier iteration=2
= {terms: 3,022, types: 335,649, coercions: 137,994}
Result size of Simplifier iteration=3
= {terms: 2,659, types: 766,643, coercions: 324,940}
Result size of Simplifier iteration=4
= {terms: 2,461, types: 2,556,807, coercions: 1,206,055}
Result size of Simplifier
= {terms: 2,461, types: 2,556,807, coercions: 1,206,055}
*** Simplifier:
Result size of Simplifier iteration=1
= {terms: 2,396, types: 9,160,050, coercions: 4,470,133}
Result size of Simplifier iteration=2
= {terms: 2,341, types: 30,948,777, coercions: 15,796,211}
ghc-stage2: out of memory (requested 1048576 bytes)
</pre>
TicketcarterWed, 15 Jan 2014 04:09:44 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:11
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:11
<p>
I just tested this issue with a copy of HEAD I built today, ghc -O2 still blows up on the cleaned up file.
</p>
TicketthoughtpoliceMon, 28 Apr 2014 13:00:07 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:12
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>7.8.3</em> to <em>7.10.1</em>
</li>
</ul>
<p>
Bumping priority down (these tickets haven't been closely followed or fixed in 7.4), and moving out to 7.10 and out of 7.8.3.
</p>
TicketthoughtpoliceMon, 28 Apr 2014 13:01:16 GMTpriority changed
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:13
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:13
<ul>
<li><strong>priority</strong>
changed from <em>high</em> to <em>normal</em>
</li>
</ul>
<p>
Actually dropping priority. :)
</p>
TicketthomieFri, 28 Nov 2014 01:13:46 GMTos, architecture changed
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:14
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:14
<ul>
<li><strong>os</strong>
changed from <em>MacOS X</em> to <em>Unknown/Multiple</em>
</li>
<li><strong>architecture</strong>
changed from <em>x86_64 (amd64)</em> to <em>Unknown/Multiple</em>
</li>
</ul>
<p>
The file <tt>cont-state8-cleaned-up.hs</tt> from <a class="ticket" href="http://ghc.haskell.org/trac/ghc/ticket/7428#comment:8" title="Comment 8">comment:8</a> is not AMP compatible.
</p>
TicketthoughtpoliceTue, 23 Dec 2014 13:34:10 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:15
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:15
<ul>
<li><strong>milestone</strong>
changed from <em>7.10.1</em> to <em>7.12.1</em>
</li>
</ul>
<p>
Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.
</p>
TicketthoughtpoliceTue, 09 Jun 2015 13:22:14 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>Cont8.hs</em>
</li>
</ul>
<p>
AMP compatible test case
</p>
TicketthoughtpoliceTue, 09 Jun 2015 13:22:16 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>Cont8.2.hs</em>
</li>
</ul>
<p>
AMP compatible test case
</p>
TicketthoughtpoliceTue, 09 Jun 2015 13:23:08 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:16
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:16
<p>
I've updated the test case. By default, even on my monster build machine, it looks like the compilation of this test is literally never going to finish, so it needs to be toned down to look at it.
</p>
TicketthoughtpoliceTue, 09 Jun 2015 13:42:35 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>Cont8-smaller.hs</em>
</li>
</ul>
TicketthoughtpoliceTue, 09 Jun 2015 13:44:00 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7428
http://ghc.haskell.org/trac/ghc/ticket/7428
<ul>
<li><strong>attachment</strong>
set to <em>cont8-hc.png</em>
</li>
</ul>
TicketthoughtpoliceTue, 09 Jun 2015 13:44:46 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:17
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:17
<p>
Here's a smaller version (that actually completes in a reasonable amount of time), along with a profile. Something is definitely quadratic or something around <tt>CorePrep</tt>/<tt>TidyCore</tt>; when run with <tt>-v3</tt>, I estimate <tt>CorePrep</tt> alone takes about 20 seconds.
</p>
TicketthoughtpoliceTue, 09 Jun 2015 13:47:02 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:18
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:18
<p>
(For a build that's about 1 minute, FWIW)
</p>
TicketgidynWed, 10 Jun 2015 07:19:46 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:19
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:19
<ul>
<li><strong>cc</strong>
<em>gidyn</em> added
</li>
</ul>
TicketbgamariMon, 15 Jun 2015 23:29:56 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:20
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:20
<p>
I may be missing something obvious here but I'm not convinced that the problem is in <tt>CorePrep</tt> or <tt>TidyCore</tt>. If one looks at the <tt>hi</tt> file or <tt>-ddump-simpl</tt> output from even a relatively shallow four-layer transformer stack one finds quite large types that appear to be growing quadratically in the depth. This is supported by the fact that <tt>Type</tt> and <tt>IfaceType</tt> show up strongly in the compiler's heap profiles as well as the fact that, in my runs, <tt>core2core</tt> shows up about as strongly in the profiles as <tt>addFingerprints</tt>.
</p>
<p>
Looking at the types in the Core, it seems that the inliner may be over-zealous in its work. Due to the CPS style of the example, the types snowball extremely quickly. Most of the damage comes in the first two simplifier iterations after <tt>FloatOut</tt>. The larger of these types are coercions and their signatures.
</p>
<p>
Compare, for instance, the Core produced by the,
</p>
<ul><li><tt>StateT Int IO</tt> testcase: <a class="ext-link" href="https://gist.github.com/bgamari/026e3670cd6a50a07790"><span class="icon"></span>https://gist.github.com/bgamari/026e3670cd6a50a07790</a>
</li><li><tt>StateT Int (StateT Int IO)</tt> case: <a class="ext-link" href="https://gist.github.com/bgamari/9e31d7a5f40d99751b0d"><span class="icon"></span>https://gist.github.com/bgamari/9e31d7a5f40d99751b0d</a>
</li><li>three-<tt>StateT</tt> case: <a class="ext-link" href="https://gist.github.com/bgamari/baf33b1f31aa5960c9c7"><span class="icon"></span>https://gist.github.com/bgamari/baf33b1f31aa5960c9c7</a>
</li><li>four-<tt>StateT</tt> case: <a class="ext-link" href="https://gist.github.com/bgamari/856d4954b488c03bf5e9"><span class="icon"></span>https://gist.github.com/bgamari/856d4954b488c03bf5e9</a>
</li></ul><p>
I'm not sure I see what is failing here. The question then is what measure is supposed to prevent this snow-balling and why is it not working? I'll have another look tomorrow.
</p>
TicketsimonpjTue, 16 Jun 2015 14:37:33 GMT
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:21
http://ghc.haskell.org/trac/ghc/ticket/7428#comment:21
<p>
See <a class="ext-link" href="http://research.microsoft.com/en-us/um/people/simonpj/papers/variant-f/index.htm"><span class="icon"></span>Scrap your type applications</a> Section 2.3, for why types can (legitimately I fear) blow up. I'm not say that is what is happening here, but it might be similar.
</p>
<p>
Simon
</p>
Ticket