[Haskell-cafe] sequence causing stack overflow on pretty small lists

[Albert Y. C. Lai]

On 13-08-26 04:46 AM, Niklas Hambüchen wrote:
> Effectively, sequence is a partial function.
>
> (Note: We are not trying to obtain a lazy list of random numbers, use
> any kind of streaming or the likes. We want the list in memory and use it.)
>
> We noticed that this problem did not happen if sequence were implemented
> with a difference list.
>
> What do you think about this? Should we "fix" functions like this,
> probably trading off a small performance hit, or accept that idiomatic
> Haskell code can crash at any time?

1. Disputed: "sequence overflows stack, for all monads"
(Bonus: a demo of Control.Monad.ST.Lazy)
(Bonus: a secret of Control.Monad.State revealed)

import Control.Monad.ST.Lazy(runST)
import Control.Monad.State(evalState)

long :: Monad m => m [Int]
long = sequence (map return [1..1000000])

infinite :: Monad m => m [()]
infinite = sequence (repeat (return ()))

-- these take constant time
one_a = take 1 (runST long)
one_b = take 1 (evalState long ())
unit_a = take 1 (runST infinite)
unit_b = take 1 (evalState infinite ())

sequence is exactly right for Control.Monad.ST.Lazy and 
Control.Monad.State. If you fix sequence, you will cause idiomatic use 
of sequence and Control.Monad.State to use too much time (up to 
infinite) and too much memory (up to infinite).

Note: Control.Monad.State = Control.Monad.State.Lazy

For more demos of Control.Monad.ST.Lazy and Control.Monad.State(.Lazy), 
see my
http://lpaste.net/41790
http://lpaste.net/63925


2. What to do for IO, Control.Monad.ST, Control.Monad.State.Strict, etc

As you said, we can combine right recursion (foldM) and difference list 
(aka Hughes list). I will dispute its questionable benefit in the next 
section, but here it is first.

sequence_hughes ms = do
     h <- go id ms
     return (h [])
   where
     go h [] = return h
     go h (m:ms) = do
         x <- m
         go (h . (x :)) ms

equivalently,

sequence_hughes ms = do
     h <- foldM op id ms
     return (h [])
   where
     op h m = do
         x <- m
         return (h . (x :))

However, as I said, sequence_hughes is totally wrong for 
Control.Monad.State and Control.Monad.ST.Lazy. And this is not even my 
dispute of the questionable benefit.


3. Disputed: "stack is limited, heap is unlimited"

sequence_hughes consumes linear heap space in place of linear stack 
space. That's all it does. There is no free lunch.

Empirically: on linux i386 32-bit GHC 7.6.3 -O2:

xs <- sequence (replicate 2000000 (return 0 :: IO Int))
print (head xs)

8MB stack, 16MB heap

xs <- sequence_hughes (replicate 2000000 (return 0 :: IO Int))
print (head xs)

24MB heap

What has sequence_hughes saved?

Since a couple of years ago, GHC RTS has switched to growable stack, 
exactly like growable heap. It starts small, then grows and shrinks as 
needed. It does not need a cap. The only reason it is still capped is 
the petty:

"to stop the program eating up all the available memory in the machine 
if it gets into an infinite loop" (GHC User's Guide)

Asymmetrically, the heap is not capped by default to stop the program 
eating up all the available memory.

And the default stack cap 8MB is puny, compared to the hundreds of MB 
you will no doubt use in the heap. (Therefore, on 64-bit, you have to 
change 2000000 to 1000000 in the above.) (Recall: [Int] of length n 
entirely in memory takes at least 12n bytes: 4 for pointer to Int, 4 for 
the number itself, 4 for pointer to next, and possibly a few more bytes 
I forgot, and possibly a few more bytes if the Int is lazy e.g. randomIO 
as Bryan said. That's just on 32-bit. Multiply by 2 on 64-bit.)

The correct fix is to raise the stack cap, not to avoid using the stack.

Indeed, ghci raises the stack cap so high I still haven't fathomed where 
it is. This is why you haven't seen a stack overflow in ghci for a long 
time. See, ghci agrees: the correct thing to do is to raise the stack cap.