GHC: Ticket #3677: Optimizer creates stack overflow on filtered CAF
http://ghc.haskell.org/trac/ghc/ticket/3677
<p>
The following code creates a stack overflow at -O1 or -O2, when running with a moderately small stack (+RTS -K94k):
</p>
<pre class="wiki">import Data.Bits
hmm :: [Integer]
hmm = filter (\n -> (n .&. (n-1))==0) [1..]
main = mapM_ print hmm
</pre><p>
The lambda just picks out powers of two, so that filter will skip increasingly long subsequences. It's the filter causing the overflow.
</p>
<p>
Changing hmm to [Int], or to be let-bound, or compiling with -O0 makes the overflow go away. Using a 95k stack also makes the overflow go away. (Below 95k, stack usage is linear with the length of the filtered-out subsequence; then it seems to cap out.)
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/3677
Trac 1.0.1jpetFri, 20 Nov 2009 06:41:21 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/3677
http://ghc.haskell.org/trac/ghc/ticket/3677
<ul>
<li><strong>attachment</strong>
set to <em>bigbug2.hs</em>
</li>
</ul>
<p>
Possibly same bug but happens with any stack size
</p>
TicketjpetFri, 20 Nov 2009 06:50:22 GMT
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:1
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:1
<p>
An even simpler repro:
</p>
<pre class="wiki">x :: [Integer]
x = filter (\n -> n `mod` 10000000 == 0) [0..]
main = mapM_ print x
</pre><p>
Interestingly, 94k seems to be the magic stack threshold again, and in all the other simple variations I tried.
</p>
<p>
The reason I was using such a small stack in the first place was to try to narrow down the stack overflow in the attached program, which overflows even an 8M stack. I'm not sure if that program is crashing because of the same issue, but I notice that using a replacement 'filter' makes the overflow go away:
</p>
<pre class="wiki">filter' f (x:xs) = case (f x) of
True -> x : (filter' f xs)
False -> filter' f xs
</pre><p>
As does compiling with -O0. So I suspect it is a variation on the same problem.
</p>
TicketiglooFri, 20 Nov 2009 21:59:58 GMTdescription changed
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:2
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/trac/ghc/ticket/3677?action=diff&version=2">diff</a>)
</li>
</ul>
TicketiglooFri, 20 Nov 2009 22:01:30 GMTmilestone set
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:3
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:3
<ul>
<li><strong>milestone</strong>
set to <em>6.12 branch</em>
</li>
</ul>
<p>
Thanks for the report.
</p>
TicketsimonpjWed, 25 Nov 2009 09:54:52 GMT
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:4
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:4
<p>
Nice report, thanks. Here is a totally self-contained example:
</p>
<pre class="wiki">module Main(main) where
main = mapM_ print (edi 0)
edi :: Integer -> [Integer]
edi x | x `mod` 10000000 == 0 = x : edi (x+1)
| otherwise = edi (x+1)
edi2 :: Integer -> [Integer]
edi2 x | x `mod` 10000000 == 0 = x : y
| otherwise = y
where
y = edi2 (x+1)
</pre><p>
Works in a 1k stack with <tt>edi</tt>, but needs 95k for <tt>edi2</tt>.
</p>
<p>
Two bugs here:
</p>
<ul><li>Stack squeezing isn't working right (Simon M will investigate)
</li><li>The optimiser should probably convert one into the other anyway (Simon PJ will look)
</li></ul>
TicketsimonmarFri, 27 Nov 2009 10:39:59 GMTmilestone changed; owner set
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:5
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:5
<ul>
<li><strong>owner</strong>
set to <em>simonpj</em>
</li>
<li><strong>milestone</strong>
changed from <em>6.12 branch</em> to <em>6.12.2</em>
</li>
</ul>
<p>
Fixed the RTS bit:
</p>
<pre class="wiki">Wed Nov 25 04:59:17 PST 2009 Simon Marlow <marlowsd@gmail.com>
* threadStackOverflow: check whether stack squeezing released some stack (#3677)
In a stack overflow situation, stack squeezing may reduce the stack
size, but we don't know whether it has been reduced enough for the
stack check to succeed if we try again. Fortunately stack squeezing
is idempotent, so all we need to do is record whether *any* squeezing
happened. If we are at the stack's absolute -K limit, and stack
squeezing happened, then we try running the thread again.
We also want to avoid enlarging the stack if squeezing has already
released some of it. However, we don't want to get into a
pathalogical situation where a thread has a nearly full stack (near
its current limit, but not near the absolute -K limit), keeps
allocating a little bit, squeezing removes a little bit, and then it
runs again. So to avoid this, if we squeezed *and* there is still
less than BLOCK_SIZE_W words free, then we enlarge the stack anyway.
M ./includes/rts/Constants.h +7
M ./rts/Schedule.c -1 +31
M ./rts/ThreadPaused.c +5
</pre><p>
Ian: please merge.
</p>
<p>
Simon PJ will investigate whether any simplifier changes are needed here.
</p>
TicketiglooThu, 03 Dec 2009 16:16:29 GMT
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:6
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:6
<pre class="wiki">Mon Nov 30 03:25:08 PST 2009 Simon Marlow <marlowsd@gmail.com>
* add a test for #3677
</pre>
TicketiglooSat, 05 Dec 2009 17:54:16 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:7
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:7
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Merged.
</p>
TicketiglooSat, 05 Dec 2009 17:54:54 GMTstatus changed; resolution deleted
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:8
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:8
<ul>
<li><strong>status</strong>
changed from <em>closed</em> to <em>reopened</em>
</li>
<li><strong>resolution</strong>
<em>fixed</em> deleted
</li>
</ul>
TicketiglooSat, 05 Dec 2009 17:55:17 GMTstatus changed
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:9
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:9
<ul>
<li><strong>status</strong>
changed from <em>reopened</em> to <em>new</em>
</li>
</ul>
TicketsimonpjSat, 05 Dec 2009 18:35:14 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:10
http://ghc.haskell.org/trac/ghc/ticket/3677#comment:10
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
I think I checked and found that the optimiser was doing the right thing. It was only without -O that it didn't. So I'll close this.
</p>
<p>
Simon
</p>
Ticket