GHC: Ticket #947: ghc -O space leak: CSE between different CAFs
http://ghc.haskell.org/trac/ghc/ticket/947
<p>
Consider the following program for generating the 1,000,000th prime:
</p>
<pre class="wiki">module Main (main) where
sieve0 (n:ns) (p:ps)
| p*p == n = sieve0 (filter (\n -> n`mod`p /= 0) ns) ps
| otherwise = n:sieve0 ns (p:ps)
primes0 :: [Int]
primes0 = 3:sieve0 [5,7..] primes0
primes :: [Int]
primes = 2:3:sieve0 [5,7..] primes0
main = print $ primes !! 1000000
</pre><p>
The intention of the separate primes0 function is to limit the number of primes that need to be held in memory. Unfortunately, ghc -O combines the common subexpressions in primes0 and primes so this effort is wasted. The resulting program needs noticably more memory than required, as can be seen by replacing the definition of <code>primes</code> by
</p>
<pre class="wiki">primes = 2:3:sieve0 (iterate (2+) 5) primes0
</pre><p>
which prevents the CSE from happening.
</p>
<p>
Excerpt of <code>+RTS -s</code> output, original version:
</p>
<pre class="wiki">12,099,221,160 bytes allocated in the heap
279,720,116 bytes copied during GC
15,834,912 bytes maximum residency (6 sample(s))
</pre><p>
modified version that prevents CSE:
</p>
<pre class="wiki">127,736,408 bytes copied during GC (scavenged)
233,388 bytes copied during GC (not scavenged)
30,624 bytes maximum residency (1 sample(s))
</pre><p>
Tested with ghc 6.4.2 and a current (as of 2006-10-17) darcs ghc 6.5.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/947
Trac 1.2simonpjTue, 17 Oct 2006 07:56:11 GMTmilestone set
http://ghc.haskell.org/trac/ghc/ticket/947#comment:1
http://ghc.haskell.org/trac/ghc/ticket/947#comment:1
<ul>
<li><strong>milestone</strong>
set to <em>6.8</em>
</li>
</ul>
<p>
I don't know any way to solve this problem automatically. But I do think it should be under your control.
</p>
<p>
For now, you can say -fno-cse.
</p>
<p>
However, I recently changed GHC to do no CSE in functions marked INLINE or NOINLINE. However that does not work in this case, because the sub-expressions get floated out. I'll try to fix that when I next visit the simplifier. That would allow per-definition control of CSE, which is more what you want.
</p>
TicketsimonpjMon, 12 Nov 2007 15:47:55 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/947#comment:2
http://ghc.haskell.org/trac/ghc/ticket/947#comment:2
<ul>
<li><strong>milestone</strong>
changed from <em>6.8 branch</em> to <em>_|_</em>
</li>
</ul>
<p>
Actually, it turns out that you <strong>do</strong> get per-definition control using INLINE, because INLINE switches off all floating-out and floating-in on the enclosed expression. I'll document this behaviour. Meanwhile I won't close this bug, becuase we still have not Truly Glorious Solution, but I'll milestone it "bottom".
</p>
<p>
Simon
</p>
TicketmichaltMon, 23 Apr 2012 19:52:06 GMTfailure set
http://ghc.haskell.org/trac/ghc/ticket/947#comment:3
http://ghc.haskell.org/trac/ghc/ticket/947#comment:3
<ul>
<li><strong>failure</strong>
set to <em>None/Unknown</em>
</li>
</ul>
<p>
Unless I'm missing something, I think there is a simple way to avoid doing CSE
on recursive types (in the sense of <code></code><code>isRecursiveTyCon</code><code></code>) -- one can simply
avoid adding variables with such types to the CSE mapping (see attached patch).
The problem here is that, according to nofib, this limits CSE quite a bit and
hurts code size. Another possibility (although quite ugly) would be to limit the
above to lists -- they are probably the main source of space leaks cause by
CSE..
</p>
<p>
The patch "almost" validates -- the 5644 fails. Apparently the test is based on
the assumption that the program overflows heap, which does not happen with the
patch. I'm not sure what 5644 actually tests and so don't really know how to
fix it.
</p>
<p>
So all in all, I'm not sure if this patch is worth it. What do you think?
</p>
TicketmichaltMon, 23 Apr 2012 19:52:25 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/947
http://ghc.haskell.org/trac/ghc/ticket/947
<ul>
<li><strong>attachment</strong>
set to <em>0001-Don-t-CSE-things-with-recursive-type-constructors-94.patch</em>
</li>
</ul>
TicketmichaltMon, 23 Apr 2012 19:53:08 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/947
http://ghc.haskell.org/trac/ghc/ticket/947
<ul>
<li><strong>attachment</strong>
set to <em>nofib</em>
</li>
</ul>
TicketmichaltMon, 23 Apr 2012 19:53:37 GMTstatus changed
http://ghc.haskell.org/trac/ghc/ticket/947#comment:4
http://ghc.haskell.org/trac/ghc/ticket/947#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>patch</em>
</li>
</ul>
TicketsimonpjTue, 24 Apr 2012 14:21:35 GMT
http://ghc.haskell.org/trac/ghc/ticket/947#comment:5
http://ghc.haskell.org/trac/ghc/ticket/947#comment:5
<p>
I doubt it's worth it. What about a non-recursive type that contains a recursive one, such as <code>([Int], Bool)</code>. And sometimes you might WANT sharing.
</p>
<p>
I'm disinclined to fiddle with this at the moment, esp as there is a way to control it manually.
</p>
TicketsimonpjMon, 16 Jul 2012 09:47:01 GMTstatus changed
http://ghc.haskell.org/trac/ghc/ticket/947#comment:6
http://ghc.haskell.org/trac/ghc/ticket/947#comment:6
<ul>
<li><strong>status</strong>
changed from <em>patch</em> to <em>new</em>
</li>
</ul>
TicketliyangMon, 15 Oct 2012 05:50:49 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/947#comment:7
http://ghc.haskell.org/trac/ghc/ticket/947#comment:7
<ul>
<li><strong>cc</strong>
<em>hackage.haskell.org@…</em> added
</li>
</ul>
TicketjwlatoMon, 15 Oct 2012 06:12:17 GMTcc changed
http://ghc.haskell.org/trac/ghc/ticket/947#comment:8
http://ghc.haskell.org/trac/ghc/ticket/947#comment:8
<ul>
<li><strong>cc</strong>
<em>jwlato@…</em> added
</li>
</ul>
TicketsimonpjMon, 15 Oct 2012 08:54:23 GMT
http://ghc.haskell.org/trac/ghc/ticket/947#comment:9
http://ghc.haskell.org/trac/ghc/ticket/947#comment:9
<p>
John: presumably you've added yourself to the cc because this has bitten you?
</p>
<p>
I have one other very simple suggestion: <strong>do no CSE for top-level CAFs</strong>. Rationale:
</p>
<ul><li>It's not a good plan to rely on CSE for major sharing of really expensive expressions; if it really matters you'll want to do it yourself by let-binding the shared thing. CSE is really intended for picking up nickles and dimes in inner loops.
</li><li>Top-level things are evaluated at most once anyway, so the gain from sharing just dime's worth of work at top level is not worth having.
</li></ul><p>
I suspect that this simple change would deal with this ticket nicely. What do others think?
</p>
<p>
Simon
</p>
Ticketint-eMon, 15 Oct 2012 11:37:08 GMT
http://ghc.haskell.org/trac/ghc/ticket/947#comment:10
http://ghc.haskell.org/trac/ghc/ticket/947#comment:10
<p>
Replying to <a class="ticket" href="http://ghc.haskell.org/trac/ghc/ticket/947#comment:9" title="Comment 9">simonpj</a>:
</p>
<blockquote class="citation">
<p>
I have one other very simple suggestion: <strong>do no CSE for top-level CAFs</strong>.
</p>
</blockquote>
<p>
Sounds like a great idea to me. An added benefit is that it would lend more safety to constructing top-level mutable variables (like <code>IORef</code>s). The loss of sharing should be negligible for most purposes, but I can think of a few cases where giving names to shared parts would be awkward:
</p>
<ul><li>repeated string constants when doing text processing
</li><li>repeated numerical values, in particular large constants containing repetitions (the worst of this can probably be avoided by just doing CSE before floating stuff out so that <code>[0,1,0,1]</code> ends up with the zeros and ones shared).
</li></ul>
TicketjwlatoTue, 16 Oct 2012 00:13:34 GMT
http://ghc.haskell.org/trac/ghc/ticket/947#comment:11
http://ghc.haskell.org/trac/ghc/ticket/947#comment:11
<p>
simonpj: we do get better results with -fno-cse, but haven't looked into it much so I can't say if this is the exact issue.
</p>
<p>
No CSE for top-level CAFs sounds good to me too.
</p>
Ticket