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.1nuddedMon, 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 <a class="missing wiki">LargeState?</a> transformer stack. So, in the attached code <a class="missing wiki">LargeState?</a> 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>
Ticket