Niklas Hambüchen | 26 Aug 10:46 2013

sequence causing stack overflow on pretty small lists

On #haskell we recently had a discussion about the following:

   import System.Random

   list <- replicateM 1000000 randomIO :: IO [Int]

I would think that this gives us a list of a million random Ints. In
fact, this is what happens in ghci. But with ghc we get:

   Stack space overflow: current size 8388608 bytes.
   Use `+RTS -Ksize -RTS' to increase it.

This is because sequence is implemented as

     sequence (m:ms) = do x <- m
                          xs <- sequence ms
                          return (x:xs)

and uses stack space when used on some [IO a].

From a theoretical side, this is an implementation detail. From the
software engineering side this disastrous because the code is

  * obviously correct by itself
  * the first thing people would come up with
  * not exaggerating: a million elements is not much
  * used a lot of places: mapM, replicateM are *everywhere*

and yet it will kill our programs, crash our airplanes, and give no
helpful information where the problem occurred.
(Continue reading)

Niklas Hambüchen | 26 Aug 11:16 2013

Re: sequence causing stack overflow on pretty small lists

As an example that this actually makes problems in production code, I
found this in the wildlife:

https://github.com/ndmitchell/shake/blob/e0e0a43/Development/Shake/Database.hs#L394

    -- Do not use a forM here as you use too much stack space
    bad <- (\f -> foldM f [] (Map.toList status)) $ \seen (i,v) -> ...

I could bet that there is a lot of code around on which we rely, which
has the same problem but does not go that far in customisation.
Gabriel Gonzalez | 26 Aug 17:08 2013
Picon

Re: sequence causing stack overflow on pretty small lists

The `mwc-random` package solves this specific problem by providing a 
function that creates a vector of random integers.

The `vector` package solves this in general by letting you use mutation 
to store intermediate results in order to avoid a space leak.

On 08/26/2013 01:46 AM, Niklas Hambüchen wrote:
> On #haskell we recently had a discussion about the following:
>
>     import System.Random
>
>     list <- replicateM 1000000 randomIO :: IO [Int]
>
> I would think that this gives us a list of a million random Ints. In
> fact, this is what happens in ghci. But with ghc we get:
>
>     Stack space overflow: current size 8388608 bytes.
>     Use `+RTS -Ksize -RTS' to increase it.
>
> This is because sequence is implemented as
>
>       sequence (m:ms) = do x <- m
>                            xs <- sequence ms
>                            return (x:xs)
>
> and uses stack space when used on some [IO a].
>
>  From a theoretical side, this is an implementation detail. From the
> software engineering side this disastrous because the code is
>
(Continue reading)

Bryan O'Sullivan | 26 Aug 21:05 2013

Re: sequence causing stack overflow on pretty small lists

On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen <mail <at> nh2.me> wrote:
This is because sequence is implemented as

     sequence (m:ms) = do x <- m
                          xs <- sequence ms
                          return (x:xs)

and uses stack space when used on some [IO a].

This problem is not due to sequence, which doesn't need to add any strictness here. It occurs because the functions in System.Random are excessively lazy. In particular, randomIO returns an unevaluated thunk.
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Reid Barton | 26 Aug 21:33 2013
Picon

Re: sequence causing stack overflow on pretty small lists

On Mon, Aug 26, 2013 at 3:05 PM, Bryan O'Sullivan <bos <at> serpentine.com> wrote:
On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen <mail <at> nh2.me> wrote:
This is because sequence is implemented as

     sequence (m:ms) = do x <- m
                          xs <- sequence ms
                          return (x:xs)

and uses stack space when used on some [IO a].

This problem is not due to sequence, which doesn't need to add any strictness here. It occurs because the functions in System.Random are excessively lazy. In particular, randomIO returns an unevaluated thunk.

It doesn't have to do with System.Random.

import Control.Monad

{-# NOINLINE a #-}
a :: IO Int
a = return 1

main = do
  list <- replicateM 1000000 a :: IO [Int]
  return ()

will produce a stack overflow, regardless of optimization level.

sequence tends to be tail-recursive for monads like Reader and (lazy) State, but not for monads like Maybe or IO where (>>=) must pattern-match on its first argument.

Regards,
Reid Barton
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Niklas Hambüchen | 27 Aug 05:51 2013

Re: sequence causing stack overflow on pretty small lists

Maybe an unlimited stack size should be the default?

As far as I understand, the only negative effect would be that some
programming mistakes would not result in a stack overflow. However, I
doubt the usefulness of that:

* It already depends a lot on the optimisation level
* If you do the same thing in a slightly different way, and you allocate
on the heap instead of on the stack you will not get it either
Tom Ellis | 27 Aug 16:24 2013
Picon

Re: sequence causing stack overflow on pretty small lists

On Mon, Aug 26, 2013 at 12:05:14PM -0700, Bryan O'Sullivan wrote:
> On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen <mail <at> nh2.me> wrote:
> > This is because sequence is implemented as
> >
> >      sequence (m:ms) = do x <- m
> >                           xs <- sequence ms
> >                           return (x:xs)
> >
> > and uses stack space when used on some [IO a].
> >
> 
> This problem is not due to sequence, which doesn't need to add any
> strictness here. It occurs because the functions in System.Random are
> excessively lazy. In particular, randomIO returns an unevaluated thunk.

I don't understand this.  The same stack overflow occurs with

    tenmil :: Int
    tenmil = 10 * 1000 * 1000

    main :: IO ()
    main = do  
            list <- replicateM tenmil (return ()) :: IO [()] 
            list `seq` return ()

"return ()" is not excessiely lazy, is it?  Could you explain further?

Tom
Albert Y. C. Lai | 27 Aug 06:59 2013
Picon

Re: sequence causing stack overflow on pretty small lists

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.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Niklas Hambüchen | 27 Aug 08:08 2013

Re: sequence causing stack overflow on pretty small lists

Thanks for your examples.

On 27/08/13 13:59, Albert Y. C. Lai wrote:
> 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.

If I understand this correctly, you agree that the stack size should be
unlimited by default?
Patrick Palka | 27 Aug 13:37 2013

Re: sequence causing stack overflow on pretty small lists

On Mon, Aug 26, 2013 at 4:46 AM, Niklas Hambüchen <mail <at> nh2.me> wrote:
On #haskell we recently had a discussion about the following:

   import System.Random

   list <- replicateM 1000000 randomIO :: IO [Int]

I would think that this gives us a list of a million random Ints. In
fact, this is what happens in ghci. But with ghc we get:

   Stack space overflow: current size 8388608 bytes.
   Use `+RTS -Ksize -RTS' to increase it.


You can use ContT to force the function to use heap instead of stack space, e.g. runContT (replicateM 1000000 (lift randomIO)) return
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Niklas Hambüchen | 27 Aug 15:07 2013

Re: sequence causing stack overflow on pretty small lists

On 27/08/13 20:37, Patrick Palka wrote:
> You can use ContT to force the function to use heap instead of stack
> space, e.g. runContT (replicateM 1000000 (lift randomIO)) return

That is interesting, and works.

Unfortunately its pure existence will not fix sequence, mapM etc. in base.
John Alfred Nathanael Chee | 28 Aug 04:19 2013
Picon

Re: sequence causing stack overflow on pretty small lists

This is somewhat related: http://ghc.haskell.org/trac/ghc/ticket/4219

This also solves the concrete problem you gave in your original post
(in reverse order):

import Control.Monad
import System.Random

sequencel :: Monad m => [m a] -> m [a]
sequencel = foldM (\tail m -> (\x -> return $ x : tail) =<< m) []

main :: IO ()
main = print =<< sequencel (replicate 1000000 (randomIO :: IO Integer))

Following on Reid's point, maybe it's worth noting in the
documentation that replicateM, mapM, and sequence are not tail
recursive for Monads that define (>>=) as strict in the first
argument?

On Tue, Aug 27, 2013 at 6:07 AM, Niklas Hambüchen <mail <at> nh2.me> wrote:
> On 27/08/13 20:37, Patrick Palka wrote:
>> You can use ContT to force the function to use heap instead of stack
>> space, e.g. runContT (replicateM 1000000 (lift randomIO)) return
>
> That is interesting, and works.
>
> Unfortunately its pure existence will not fix sequence, mapM etc. in base.
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries

--

-- 
Love in Jesus Christ, John Alfred Nathanael Chee
http://www.biblegateway.com/
http://web.cecs.pdx.edu/~chee/
John Lato | 28 Aug 05:26 2013
Picon

Re: sequence causing stack overflow on pretty small lists

IMHO it's perfectly reasonable to expect sequence/replicateM/mapM to be able to handle a list of ~1e6 elements in the Unescapable Monad (i.e. IO).  All the alternate implementations in the world won't be as handy as Prelude.sequence, and no amount of documentation will prevent people from running into this headlong*.  So unless there's a downside to upping the stack size limitation I'm unaware of, +1 to that suggestion from me.

John
[1] Most people are physically incapable of reading documents that explain why what they want to do won't work.  Even if people did read the documentation, I suspect that the people most in need of the information would be the least likely to understand how it applies to their situation.



On Tue, Aug 27, 2013 at 9:19 PM, John Alfred Nathanael Chee <cheecheeo <at> gmail.com> wrote:
This is somewhat related: http://ghc.haskell.org/trac/ghc/ticket/4219

This also solves the concrete problem you gave in your original post
(in reverse order):

import Control.Monad
import System.Random

sequencel :: Monad m => [m a] -> m [a]
sequencel = foldM (\tail m -> (\x -> return $ x : tail) =<< m) []

main :: IO ()
main = print =<< sequencel (replicate 1000000 (randomIO :: IO Integer))

Following on Reid's point, maybe it's worth noting in the
documentation that replicateM, mapM, and sequence are not tail
recursive for Monads that define (>>=) as strict in the first
argument?

On Tue, Aug 27, 2013 at 6:07 AM, Niklas Hambüchen <mail <at> nh2.me> wrote:
> On 27/08/13 20:37, Patrick Palka wrote:
>> You can use ContT to force the function to use heap instead of stack
>> space, e.g. runContT (replicateM 1000000 (lift randomIO)) return
>
> That is interesting, and works.
>
> Unfortunately its pure existence will not fix sequence, mapM etc. in base.
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries



--
Love in Jesus Christ, John Alfred Nathanael Chee
http://www.biblegateway.com/
http://web.cecs.pdx.edu/~chee/

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Henning Thielemann | 28 Aug 10:16 2013
Picon

Re: sequence causing stack overflow on pretty small lists


On Tue, 27 Aug 2013, John Lato wrote:

> [1] Most people are physically incapable of reading documents that explain why what they want to do won't
> work.  Even if people did read the documentation, I suspect that the people most in need of the information
> would be the least likely to understand how it applies to their situation.

Plus: I don't expect that programmers read the documentation of 'sequence' 
and 'mapM' again every time they use the function.
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Tom Ellis | 4 Sep 17:35 2013
Picon

Strange IO sequence behaviour (Was: sequence causing stack overflow on pretty small lists)

As an addendum to the recent discussion, can anyone explain why main crashes
quickly with a stack overflow, whereas main' is happy to print "Hi" for ages
(eventually crashing due to an out of memory condition)?

    bignum = 100 * 1000 * 1000
    main   = replicateM bignum (return ())
    main'  = replicateM bignum (putStrLn "Hi")

Tom
Joe Q | 4 Sep 22:11 2013
Picon

Re: Strange IO sequence behaviour (Was: sequence causing stack overflow on pretty small lists)

To give a very casual explanation, both mains are of the form "do this a bunch of times and return the results". Your first is "do nothing and return the ()s", but importantly, it has to execute all those nothings.

Your second is "print hello a bunch and return the ()s". The list it wants to eventually return gets bigger and bigger as more prints happen, until poof!

You should look at how replicateM works again, and hopefully it will make more sense with that in mind.

On Sep 4, 2013 11:35 AM, "Tom Ellis" <tom-lists-haskell-cafe-2013 <at> jaguarpaw.co.uk> wrote:
As an addendum to the recent discussion, can anyone explain why main crashes
quickly with a stack overflow, whereas main' is happy to print "Hi" for ages
(eventually crashing due to an out of memory condition)?

    bignum = 100 * 1000 * 1000
    main   = replicateM bignum (return ())
    main'  = replicateM bignum (putStrLn "Hi")

Tom

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Joe Q | 4 Sep 22:15 2013
Picon

Re: Strange IO sequence behaviour (Was: sequence causing stack overflow on pretty small lists)

Er, I seem to have misread and thought you were doing infinite replicateM, so that explanation doesn't completely address your question. That's what I get for reading on a phone!

On Sep 4, 2013 4:11 PM, "Joe Q" <headprogrammingczar <at> gmail.com> wrote:

To give a very casual explanation, both mains are of the form "do this a bunch of times and return the results". Your first is "do nothing and return the ()s", but importantly, it has to execute all those nothings.

Your second is "print hello a bunch and return the ()s". The list it wants to eventually return gets bigger and bigger as more prints happen, until poof!

You should look at how replicateM works again, and hopefully it will make more sense with that in mind.

On Sep 4, 2013 11:35 AM, "Tom Ellis" <tom-lists-haskell-cafe-2013 <at> jaguarpaw.co.uk> wrote:
As an addendum to the recent discussion, can anyone explain why main crashes
quickly with a stack overflow, whereas main' is happy to print "Hi" for ages
(eventually crashing due to an out of memory condition)?

    bignum = 100 * 1000 * 1000
    main   = replicateM bignum (return ())
    main'  = replicateM bignum (putStrLn "Hi")

Tom

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Tom Ellis | 6 Sep 21:31 2013
Picon

Re: Strange IO sequence behaviour (Was: sequence causing stack overflow on pretty small lists)

On Wed, Sep 04, 2013 at 04:35:17PM +0100, Tom Ellis wrote:
> As an addendum to the recent discussion, can anyone explain why main crashes
> quickly with a stack overflow, whereas main' is happy to print "Hi" for ages
> (eventually crashing due to an out of memory condition)?
> 
>     bignum = 100 * 1000 * 1000
>     main   = replicateM bignum (return ())
>     main'  = replicateM bignum (putStrLn "Hi")

FYI, rwbarton on Reddit produced a nice answer:

    http://www.reddit.com/r/haskell/comments/1luan1/strange_io_sequence_behaviour/cc32ec4
Niklas Hambüchen | 6 Sep 21:52 2013

Re: Strange IO sequence behaviour (Was: sequence causing stack overflow on pretty small lists)

Ah, that's enlightening, and a good addition to 
http://ghc.haskell.org/trac/ghc/ticket/8189

On Sat 07 Sep 2013 04:31:31 JST, Tom Ellis wrote:
> FYI, rwbarton on Reddit produced a nice answer:
>
>     http://www.reddit.com/r/haskell/comments/1luan1/strange_io_sequence_behaviour/cc32ec4

Gmane