Optimizer creates stack overflow on filtered CAF

[jpet]

The following code creates a stack overflow at -O1 or -O2, when running with a moderately small stack (+RTS -K94k):

import Data.Bits
hmm :: [Integer]
hmm = filter (\n -> (n .&. (n-1))==0) [1..]
main = mapM_ print hmm

The lambda just picks out powers of two, so that filter will skip increasingly long subsequences. It's the filter causing the overflow.

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.)

[jpet]

Possibly same bug but happens with any stack size

[jpet]

An even simpler repro:

x :: [Integer]
x = filter (\n -> n `mod` 10000000 == 0) [0..]
main = mapM_ print x

Interestingly, 94k seems to be the magic stack threshold again, and in all the other simple variations I tried.

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:

filter' f (x:xs) = case (f x) of
                    True -> x : (filter' f xs)
                    False -> filter' f xs

As does compiling with -O0. So I suspect it is a variation on the same problem.

[igloo]

Thanks for the report.

[simonpj]

Nice report, thanks. Here is a totally self-contained example:

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)

Works in a 1k stack with edi, but needs 95k for edi2.

Two bugs here:

• Stack squeezing isn't working right (Simon M will investigate)
• The optimiser should probably convert one into the other anyway (Simon PJ will look)

[simonmar]

Fixed the RTS bit:

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

Ian: please merge.

Simon PJ will investigate whether any simplifier changes are needed here.

[igloo]

Mon Nov 30 03:25:08 PST 2009  Simon Marlow <marlowsd@gmail.com>
  * add a test for #3677

[igloo]

Merged.

[simonpj]

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.

Simon